Study of the Brand and Bound Algorithm Performance on Traveling Salesman Problem Variants

DOI

10.2991/assehr.k.210508.066How to use a DOI?

Keywords

the branch and bound algorithm, ATSPTW, TSPTW, TSPPC and MTSP

Abstract

Traveling salesman problem (TSP) can be applied to distribution problems, namely determining the minimum route from the depot to all customers exactly once and back to the depot. Some constraints can be added to the problem such as time constraints, additional salesmen on the route that is passed, the need for an order of delivery, and passing one-way road. This article will discuss TSP variants developed from basic TSP, namely TSPTW, MTSP, TSPPC, and ATSPTW. The differences in formulations of these variants are described and the branch and bound algorithm is used to solve them. There are three main steps to the branch and bound algorithm namely the initialization stage to obtain the initial solution, the process stage and solution improvement, and the determination of the optimum solution. Identification of the similarities and differences in the application of the branch and bound algorithm steps on these variants are discussed in this article. An example is given of the application of the branch and bound algorithm to the four variants of 8 customers and one depot. The results of the application examples are depicted on a graph in order of the minimum total distance, namely ATSPTW, TSPTW, TSPPC, and MTSP.

Copyright

© 2021, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Sapti Wahyuningsih
AU  - Dwi Retno Sari
PY  - 2021
DA  - 2021/05/11
TI  - Study of the Brand and Bound Algorithm Performance on Traveling Salesman Problem Variants
BT  - Proceedings of the 1st International Conference on Mathematics and Mathematics Education (ICMMEd 2020)
PB  - Atlantis Press
SP  - 204
EP  - 211
SN  - 2352-5398
UR  - https://doi.org/10.2991/assehr.k.210508.066
DO  - 10.2991/assehr.k.210508.066
ID  - Wahyuningsih2021
ER  -