Фомичёв Михаил Игоревич
A Study of the Impact of Precomputed Tour Cost on Resource Characteristics of Branch and Bound Method for Solving the Travelling Salesman Problem
Системная и программная инженерия
In spite of the fact that the classical Branch and Bound algorithm for solving asymmetric Traveling Salesman Problem was presented in 1963 by J.D.C. Little, K.G. Murty, D.W. Sweeney, and C. Karel, it is one of the most applied accurate algorithms used to solve it. However, its time complexity is exponential. There are on the other hand, a number of algorithms which are not guaranteed to find the optimal solution. Those algorithms commonly referred to as “metaheuristic algorithms“, can find a close solution to optimal one for problems with large input size in a reasonable time frame. In this paper, the analysis of the combination of the Branch and Bound method with metaheuristic algorithms for solving Traveling Salesman problem is presented.