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/).
Cite this article
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 -