A Hybrid Exact Algorithm for the Asymmetric Traveling Salesman Problem: Construction and a Statistical Study of Computational Efficiency

Abstract

We present the results of a comparative statistical analysis of the time for solving the asymmetric traveling salesman problem (ATSP) with the branch-and-bound method (without precalculation of the tour) and with a hybrid method. The hybrid method consists of the Lin–Kernighan–Helsgaun approximate algorithm used to calculate the initial tour and the branch-and-bound method. We show that using an approximate solution found with the Lin–Kernighan–Helsgaun algorithm can significantly reduce the search time for the exact solution to the traveling salesman problem using the branch-and-bound method for problems from a certain class. We construct a prediction of the search time for the exact solution by the branchand- bound method and by the hybrid algorithm. A computational experiment has shown that the proportion of tasks solved faster by the hybrid algorithm than by the branch-and-bound method grows with increasing problem dimension.