• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Exact time-efficient combined algorithm for solving the asymmetric traveling salesman problem

Business Informatics. 2018. Vol. 45. No. 3. P. 20-28.

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.
The subject of the research in this article is the choice of the best heuristic algorithm which, when
applied, leads to an increase in temporal effi ciency in combination with the algorithm of the branch and
bound method, and an experimental study of its software implementation in order to obtain an average time
for solving individual problems. On the basis of the results obtained, recommendations are given on the
limiting dimensions of the problem that allow for an acceptable solution time, something which is of interest
in the practical application of this combined algorithm in the tasks of business informatics and logistics.