ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 3. Vol. 28. 2022

DOI: 10.17587/it.28.141-147

M. V. Ulyanov, Leading Researcher, V. A. Trapeznikov Institute of Control Sciences of the Russian Academy of Sciences, M. V. Lomonosov Moscow State University, Moscow, Russian Federation, M. I. Fomichev, Doctoral Student, Nizhny Novgorod State Technical University n.a. R. E. Alekseev, Lecturer of Faculty of Computer Science, School of Software Engineering National Research University Higher School of Economics, Moscow, Russian Federation

Combined Algorithm for Solving the Asymmetric Traveling Salesman Problem as Applied to Transport Logistics Problems

The traveling salesman problem is to find a Hamiltonian cycle with the minimum sum of the weights of arcs in a complete oriented asymmetric graph. Despite its simple formulation, the traveling salesman problem is NP-hard. The Branch and Bound method is the basis of the most time efficient algorithm for solving the traveling salesman problem, delivering the exact solution. However, for a number of applied problems, the time to obtain a solution using this algorithm is practically unacceptable. Despite the majority of heuristic algorithms developed for the traveling salesman problem, for some applied problems in business informatics and logistics, it is important to obtain accurate solutions in the range of small dimensions. The article presents the results on the development and statistical study of a combined algorithm for solving the traveling salesman problem, which obtains exact solutions, under conditions of limitation on the average solution time for dimensions not exceeding 55 that arise when solving transport logistics problems (data presented by LLC "Group KIT"). The implementation of the Branch and Bound method in combination with the Lin-Kernighan-Helsgaun metaheuristic algorithm is considered. Approaches are described that allowed, when developing this combined algorithm, to significantly reduce the time for solving individual traveling salesman problems, and to satisfy the company's requirement for time efficiency.
Keywords: Traveling Salesman Problem, Branch and Bound method, combined algorithm, Lin-Kernighan-Helsgaun metaheuristic algorithm, time efficiency, transport logistics

P. 141–147

Acknowledgements: This work was supported by the Russian Foundation for Basic Research and the Ministry of Science and Technology of Taiwan in the framework of the scientific project No. 20-58-S52006.

To the contents