ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 10. Vol. 25. 2019

DOI: 10.17587/it.25.590-595

M. V. Ulyanov, Leading Researcher, Professor, e-mail: muljanov@mail.ru, 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, e-mail: michan94@yandex.ru

Comparative Analysis of the Branch and Bound Method Combinations with Metaheuristic Algorithms for Solving the Asymmetric Traveling Salesman Problem

The algorithm that implements the Branch and Bound method for solving the Traveling Salesman Problem is one of the common exact algorithms for solving it. Metaheuristic algorithms for solving this problem do not guarantee obtaining an exact solution, however they work "quickly". In order to reduce the nodes number of the generated decision tree in the Branch and Bo und method, you can use the solution obtained by the metaheuristic algorithm. By choosing a metaheuristic algorithm and its combination with the Branch and Bound method, it is possible to gain time for obtaining an exact solution. Such a choice must be confirmed by experimental data on the time efficiency of the software implementation of such a combined algorithm. This article discusses some metaheuristic algorithms and a combination of such algorithms with the classical implementation of the Branch and Bound method for solving the asymmetric Traveling Salesman Problem. The data of an experimental study of the average time of obtaining an exact solution for the range of the dimension of the problem from 30 to 45 are given, and recommendations are given on the choice of a metaheuristic algorithm.
Keywords: asymmetric Traveling Salesman Problem, branch and bound method, precomputed tour, complexity of the individual problem, combined algorithm, metaheuristic algorithm

P. 590–595

To the contents