Сравнительный анализ комбинаций метода ветвей и границ с метаэвристическими алгоритмами для решения асимметричной задачи коммивояжёра
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.