Note to users. If you're seeing this message, it means that your browser cannot find this page's style/presentation instructions -- or possibly that you are using a browser that does not support current Web standards. Find out more about why this message is appearing, and what you can do to make your experience of our site the best it can be.

Science 15 February 1991:
Vol. 251. no. 4995, pp. 754 - 761
DOI: 10.1126/science.251.4995.754
Prev | Table of Contents | Next

Articles

Exact Solution of Large Asymmetric Traveling Salesman Problems

DONALD L. MILLER 1 and JOSEPH F. PEKNY 2

1 Central Research & Development Department, E. I. du Pont de Nemours and Company, Wilmington, DE 19880
2 School of Chemical Engineering, Purdue University, West Lafayette, IN 47907

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.


THIS ARTICLE HAS BEEN CITED BY OTHER ARTICLES:
On the Application of Explanation-Based Learning to Acquire Control Knowledge for Branch and Bound Algorithms.
M. J. Realff and G. Stephanopoulos (1998)
INFORMS Journal on Computing 10, 56-71
   Abstract »    PDF »


To Advertise     Find Products

Science. ISSN 0036-8075 (print), 1095-9203 (online)