2023, issue 4, p. 43-52
Received 21.11.2023; Revised 27.11.2023; Accepted 28.11.2023
Published 04.12.2023; First Online 05.12.2023
https://doi.org/10.34229/2707-451X.23.4.6
A Natural Approach to Solving the Traveling Salesman Problem
Dmitri Terzi 
Moldova State University, Chisinau, Moldova
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. The traveling salesman problem is a transport-type problem. It is natural to use a method based on the technology for solving transport problems to solve it. The cyclicity and degeneracy of the solution to the traveling salesman problem requires significant modification of the corresponding stages of solving the transport problem (drawing up an initial feasible solution; checking the plan for optimality; obtaining a new feasible solution).
Purpose. Development of a natural approach to solving the traveling salesman problem. Description of the structure of a set of traveling salesman problems that have a predetermined optimal solution. Algorithmic formation of such problems for the purpose of conducting mass computing experiments.
Results. The paper presents new results and computational experiments with a developed natural algorithm for solving the traveling salesman problem, based on the technology for solving transport problems, including a new effective method for generating an initial cyclic solution, an algorithm for transitioning from the initial cyclic to another, also cyclic, solution. An algorithm has been developed for constructing the traveling salesman problem with an optimal solution given in advance, which allows for a better understanding of the structure of traveling salesman problems.
Conclusions. The results of computational experiments show that the use of potentials method technology for solving the traveling salesman problem, as a special transport problem, is a promising direction for searching for a high-quality solution. The developed algorithms and programs expand the possibilities of solving the traveling salesman problem. The time it takes to solve a problem depends significantly on the size of the problem. In this regard, it is essential to automatically generate the traveling salesman problem with a given optimal solution, which allows you to conduct mass experiments and draw conclusions.
Keywords: travelling salesman problem, method of potentials, optimality criterion, cyclic substitution, route, algorithm.
Cite as: Terzi D. A Natural Approach to Solving the Traveling Salesman Problem. Cybernetics and Computer Technologies. 2023. 4. P. 43–52. https://doi.org/10.34229/2707-451X.23.4.6
References
1. Grötschel M. The Travelling Salesman Problem and its Applications. Combinatorial Optimization at Work. Block Course at TU Berlin, October 4 – 15, 2005. https://co-at-work.zib.de/berlin/download/CD/Talks/02M1-TSP.pdf
2. Taillard E.D. Design of Heuristic Algorithms for Hard Optimization, With Python Codes for the Travelling Salesman Problem. Springer, 2023. https://doi.org/10.1007/978-3-031-13714-3
3. Roberti R., Toth P. Models and algorithms for the Asymmetric Traveling Salesman Problem: An experimental comparison. EURO Journal on Transportation and Logistics. 2012. 1 (1–2). P. 113–133. https://doi.org/10.1007/s13676-012-0010-0
4. Hasan-Shawopn M.F., Raval N. Operations research: Traveling Salesman Problem. Technical Report. Wernigerode, Germany, 2023. 57 p. https://www.researchgate.net/publication/369973661
5. Golstein E.G., Yudin D.B. Problems of linear programming of transport type. M.: Nauka, 1969. 382 p. (in Russian)
6. Sharma J.K. Operations Research: Theory and Applications. Macmillan Publishers India Limited, 2009. 976 p. https://books.google.com.ua/books?id=1EZxJHO32swC
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)