A Natural Approach to Solving the Traveling Salesman Problem

Abstract

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