Exact Solution of Large Asymmetric Traveling Salesman Problems
Abstract
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.
References
Balas, E., Journal of the Association for Computing Machinery 38: 985 (1991).
BELLMORE, M, PATHOLOGY OF TRAVELING-SALESMAN SUBTOUR-ELIMINATION ALGORITHMS, OPERATIONS RESEARCH 19: 278 (1971).
BLAND, R.G., LARGE TRAVELING SALESMAN PROBLEMS ARISING FROM EXPERIMENTS IN X-RAY CRYSTALLOGRAPHY - A PRELIMINARY-REPORT ON COMPUTATION, OPERATIONS RESEARCH LETTERS 8: 125 (1989).
BOHR, H, A Travelling Salesman Approach to Protein Conformation, COMPLEX SYSTEMS 3: 9 (1989).
CHAN, D, IC INSERTION - AN APPLICATION OF THE TRAVELING SALESMAN PROBLEM, INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 27: 1837 (1989).
Fischetti, M., An additive bounding procedure for the asymmetric traveling salesman problem (1989).
Garey, M. R., Computers and Intractability: A Guide to the Theory ofNP-Completeness (1979).
Grotschel, M., Universitat Augsburg Institut fur Mathematik Report 73 (1988).
GUPTA, JND, OPTIMAL FLOWSHOP SCHEDULES WITH NO INTERMEDIATE STORAGE SPACE, NAVAL RESEARCH LOGISTICS 23: 235 (1976).
HELD, M, TRAVELING-SALESMAN PROBLEM AND MINIMUM SPANNING TREES, OPERATIONS RESEARCH 18: 1138 (1970).
Johnson, D., Nature 330: 525 (1987).
Johnson, D. S., Proceedings of the 17th Colloquium on Automata, Languages and Programming: 446 (1990).
KANELLAKIS, P, LOCAL SEARCH FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM, OPERATIONS RESEARCH 28: 1086 (1980).
KARP, R.M., PATCHING ALGORITHM FOR THE NONSYMMETRIC TRAVELING-SALESMAN PROBLEM, SIAM JOURNAL ON COMPUTING 8: 561 (1979).
KIRKPATRICK, S, OPTIMIZATION BY SIMULATED ANNEALING, SCIENCE 220: 671 (1983).
Korte, B., paper presented at the 13th International Mathematical Programming Symposium, Tokyo, (1988).
Lawler, E. L., The Traveling Salesman Problem: A Guided Tour ofCombinatorial Optimization (1985).
LIN, S, EFFECTIVE HEURISTIC ALGORITHM FOR TRAVELING-SALESMAN PROBLEM, OPERATIONS RESEARCH 21: 498 (1973).
LITKE, J.D., AN IMPROVED SOLUTION TO THE TRAVELING SALESMAN PROBLEM WITH THOUSANDS OF NODES, COMMUNICATIONS OF THE ACM 27: 1227 (1984).
MADSEN, OBG, AN APPLICATION OF TRAVELLING-SALESMAN ROUTINES TO SOLVE PATTERN-ALLOCATION PROBLEMS IN THE GLASS INDUSTRY, JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 39: 249 (1988).
MILLER, D.L., RESULTS FROM A PARALLEL BRANCH AND BOUND ALGORITHM FOR THE ASYMMETRIC TRAVELING SALESMAN PROBLEM, OPERATIONS RESEARCH LETTERS 8: 129 (1989).
Padberg, M., Instituto di Analisi Dei Sistimi ed Informatica del CNR Report R. 247 (1988).
PADBERG, M, OPTIMIZATION OF A 532-CITY SYMMETRICAL TRAVELING SALESMAN PROBLEM BY BRANCH AND CUT, OPERATIONS RESEARCH LETTERS 6: 1 (1987).
PAPADIMITRIOU, C.H., FLOWSHOP SCHEDULING WITH LIMITED TEMPORARY-STORAGE, JOURNAL OF THE ACM 27: 533 (1980).
PAPADIMITRIOU, C.H., SOME EXAMPLES OF DIFFICULT TRAVELING SALESMAN PROBLEMS, OPERATIONS RESEARCH 26: 434 (1978).
Pekny, J. F., Math. Program 55: 17 (1992).
Pekny, J. F., Operations Research Letters 10: 173 (1991).
PLANTE, R.D., THE PRODUCT MATRIX TRAVELING SALESMAN PROBLEM - AN APPLICATION AND SOLUTION HEURISTIC, OPERATIONS RESEARCH 35: 772 (1987).
Stodolsky, D., Carnegie Mellon University Engineering Design Research Center Report 05-25-88 (1988).
Tarjan, R. E., Data Structures and Network Algorithms (1983).
WISMER, D.A., SOLUTION OF FLOWSHOP-SCHEDULING PROBLEM WITH NO INTERMEDIATE QUEUES, OPERATIONS RESEARCH 20: 689 (1972).
Get full access to this article
View all available purchase options and get full access to this article.
Already a Subscriber?Sign In
Information & Authors
Information
Published In
Science
Volume 251 | Issue 4995
15 February 1991
15 February 1991
Copyright
1990 by the American Association for the Advancement of Science.
Submission history
Published in print: 15 February 1991
Authors
Metrics & Citations
Metrics
Article Usage
Altmetrics
Citations
Export citation
Select the format you want to export the citation of this publication.
View Options
Get Access
Log in to view the full text
AAAS login provides access to Science for AAAS Members, and access to other journals in the Science family to users who have purchased individual subscriptions.
- Become a AAAS Member
- Activate your AAAS ID
- Purchase Access to Other Journals in the Science Family
- Account Help
Log in via OpenAthens.
Log in via Shibboleth.
More options
Purchase digital access to this article
Download and print this article for your personal scholarly, research, and educational use.
Buy a single issue of Science for just $15 USD.
View options
PDF format
Download this article as a PDF file
Download PDF