Эффективный по времени точный комбинированный алгоритм для асимметричной задачи коммивояжера

Бизнес-информатика. 2018. Т. 45. № 3. С. 20–28.

Zhukova G., Ulyanov M., Fomichev M.

For practical, important tasks in the fi elds of economics and logistics, as well as in a number of technical applications, it becomes necessary to solve the traveling salesman problem (TSP). Quite often, the features of these problems lead to the traveling salesman problem in asymmetric formulation (asymmetric traveling salesman problem, ATSP). Moreover, in some practical applications it is desirable to obtain an exact solution. One of the known exact algorithms for solving the ATSP is an algorithm that implements the well-known branch and bound method. The known experimental estimates of its complexity on the average are exponential. However, this does not mean that for small dimensions of the problem (currently, no more than 70–75), the expected time for solving the individual problem is unacceptably high. The need to reduce the time for solving individual problems dictated by practice is associated with the use of various modifi cations of this algorithm, of which a modifi cation that involves storing truncated matrices in the search decision tree is one of the most eff ective. In this article, the authors rely on this modifi cation. Other possible improvements in the time effi ciency of the software implementation of the branch and bound method are related, among other things, to obtaining the initial approximation by heuristic algorithms. As a result, we get a combined algorithm, in which, at the fi rst stage, some heuristics works to obtain the initial solution, from which the branch and bound method starts. This idea has been discussed for a long time, but the problem is that to reduce time, such a heuristic algorithm is needed that delivers a solution close to optimal which will be found quite fast. One of the possible solutions to this problem is the subject of this article.

Keywords: экспериментальное исследование, метод ветвей и границ, experimental research, travelling salesman problem, combined algorithm, time efficiency, задача коммивояжера, комбинированный алгоритм, временная эффективность