PT - JOURNAL ARTICLE
AU - MILLER, DONALD L.
AU - PEKNY, JOSEPH F.
TI - Exact Solution of Large Asymmetric Traveling Salesman Problems
AID - 10.1126/science.251.4995.754
DP - 1991 Feb 15
TA - Science
PG - 754--761
VI - 251
IP - 4995
4099 - http://science.sciencemag.org/content/251/4995/754.short
4100 - http://science.sciencemag.org/content/251/4995/754.full
SO - Science1991 Feb 15; 251
AB - 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.