53950

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

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

DOI: 

10.1134/S0005117919110092

Наименование источника: 

  • Automation and Remote Control

Обозначение и номер тома: 

Vol. 80. No. 11

Город: 

  • Москва

Издательство: 

  • Pleiades Publishing, Springer

Год издания: 

2019

Страницы: 

2054-2067
Аннотация
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

Библиографическая ссылка: 

Жукова Г.Н., Ульянов М.В., Фомичев М.И. A Hybrid Exact Algorithm for the Asymmetric Traveling Salesman Problem: Construction and a Statistical Study of Computational Efficiency // Automation and Remote Control. 2019. Vol. 80. No. 11. С. 2054-2067.