ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 1. Vol. 27. 2021

DOI: 10.17587/it.27.3-8

M. V. Ulyanov, Leading Researcher, V. A. Trapeznikov Institute of Control Sciences of the Russian Academy of Sciences, M. V. Lomonosov Moscow State University
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

Research of Features of the Combined Algorithm for Solving the Asymmetric Traveling Salesman Problem

The exact algorithm that implements the Branch and Boimd method with precomputed tour which is calculated by Lin-Kernighan-Helsgaun metaheuristic algorithm for solving the Traveling Salesman Problem is concerned here. Reducing the number of decision tree nodes, which are created by the Branches and Bound method, due to a "good" precomputed tour leads to the classical balancing dilemma of time costs. A tour that is close to optimal one takes time, even when the Lin-Kernighan-Helsgaun algorithm is used, however it reduces the working time of the Branch and Bound method. The problem of determining the scope of such a combined algorithm arises. In this article it is solved by using a special characteristic of the individual Traveling Salesman Problem — the number of changes tracing direction in the search decision tree generated by the Branch and Bound Method. The use of this characteristic allowed to divide individual tasks into three categories, for which, based on experimental data, recommendations of the combined algorithm usage are formulated. Based on the data obtained in a computational experiment (in range from 30 to 45), it is recommended to use a combined algorithm for category III problems starting with n = 36, and for category II problems starting with n = 42.
Keywords: Traveling Salesman Problem, branch and bound method, precomputed tour, combined algorithm, Lin-Kernighan-Helsgaun algorithm

P. 3–8

To the contents