TY - JOUR
T1 - Exact Solution of Large Asymmetric Traveling Salesman Problems
JF - Science
JO - Science
SP - 754
LP - 761
DO - 10.1126/science.251.4995.754
VL - 251
IS - 4995
AU - MILLER, DONALD L.
AU - PEKNY, JOSEPH F.
Y1 - 1991/02/15
UR - http://science.sciencemag.org/content/251/4995/754.abstract
N2 - 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.
ER -