Exact Solution of Large Asymmetric Traveling Salesman Problems

See allHide authors and affiliations

Science  15 Feb 1991:
Vol. 251, Issue 4995, pp. 754-761
DOI: 10.1126/science.251.4995.754

This article has corrections. Please see:


The traveling salesman problem is one of a class of difficult problems in combinatorial optimization that is representative of a large number of important scientific and engineering problems. A survey is given of recent applications and methods for solving large problems. In addition, an algorithm for the exact solution of the asymmetric traveling salesman problem is presented along with computational results for several classes of problems. The results show that the algorithm performs remarkably well for some classes of problems, determining an optimal solution even for problems with large numbers of cities, yet for other classes, even small problems thwart determination of a provably optimal solution.