Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности
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 signi cantly 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 branch-and-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.