The Solutions to Traveling Salesman Problem
DOI:
https://doi.org/10.54097/hset.v47i.8182Keywords:
Symmetric Traveling Salesman Problem, asymmetric Traveling Salesman Problem, Multiple Traveling Salesman Problem, branch and bound, Python.Abstract
This paper presents solutions to symmetric, asymmetric, and multiple traveling salesman problems. In the symmetric traveling salesman problem, one salesperson must go to five cities, making precisely one stop at each location. A matrix with the distances between each city is provided. Using the branch and bound algorithm and expressing it in Python, the final result is obtained. The formulations of the asymmetric traveling salesman problem and the multiple traveling salesman problem are demonstrated in the paper. The asymmetric problem in the paper is solved by transforming the asymmetric traveling salesman problem into a symmetric traveling salesman problem; then, the branch and bound algorithm has been applied to solve the problem. In the multiple traveling salesman problem, three salesmen are required to visit seven cities in total, each of which is only visited by one salesperson once. Each city is a point in an x-y plane, and the coordinates of all points are given in a graph. By formulating the MTSP problem with an assignment-based double-index integer programming and applying the constraints, the outcome is derived from Python code within a few seconds.
Downloads
References
Padberg, M. and Rinaldi, G., “Optimization of a 532-City Symmetric Traveling Salesman Problem by Branch and Cut.” Operations Research Letters, vol. 6, no. 1, 1–7 (1087).
Knox, J. “Tabu Search Performance on the Symmetric Traveling Salesman Problem.” Computers & Operations Research, vol. 21, no. 8, 867–876 (1984).
Lim, Y. F., Hong, P. Y., Ramli, R., and Khalid, R., "An improved tabu search for solving symmetric traveling salesman problems," 2011 IEEE Colloquium on Humanities, Science and Engineering, 851-854 (2011).
Carpaneto, G., et al. “Exact Solution of Large-Scale, Asymmetric Traveling Salesman Problems.” ACM Transactions on Mathematical Software, vol. 21, no. 4, 394–409 (1995).
Ascheuer, N., Jünger, M. and Reinelt, G. “A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints.” Computational Optimization and Applications 17, 61–84 (2000).
Jonker, R., and Volgenant. T., “Transforming Asymmetric into Symmetric Traveling Salesman Problems.” Operations Research Letters, vol. 2, no. 4, 161–163 (1983).
Gavish, B., and Srikanth, T., "An optimal solution method for large-scale multiple traveling salesmen problems." Operations Research 34.5 (1986).
Gromicho, J., Paixão, J. and Bronco, I., "Exact solution of multiple traveling salesman problems." Combinatorial optimization. Springer, Berlin, Heidelberg, 291-292 (1992).
Held, M. and Karp, R.M., “The travelingsalesmanproblem and minimum spanning trees: part ZI.” Mathematical Programming 1, 6-25 (1971).
Volgenant, T., Jonker, R., “Nonoptimal Edges for the Symmetric Traveling Salesman Problem. Operations Research” vol, 32, no. 4, 65-74 (1984).
Matai, R., Singh, S. P., and Mittal, M. L., "Traveling salesman problem: an overview of applications, formulations, and solution approaches." Traveling salesman problem, theory and applications 1 (2010).
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
