A Heuristic Approach to Solving Travelling Salesman Problems

Robert L. Karg and Gerald L. Thompson
Additional contact information
Robert L. Karg: National Tube Division, U.S. Steel and Duquesne University
Gerald L. Thompson: Graduate School of Industrial Administration, Carnegie Institute of Technology

Management Science, 1964, vol. 10, issue 2, 225-248

Abstract: A code for solving travelling salesman problem employing heuristic ideas is described. Acyclic permutations of the cities are constructed by first choosing two cities at random for a permutation of length two, putting the remaining cities in a random list and then inserting cities from the list in the partially constructed permutations so that they add least to the length of the partial tour. A second heuristic idea used in the code is that of breaking up the problem into convex, or almost convex sub-problems and employing the above-mentioned heuristic on these subproblems. Numerical experience with the code is described as well as weaknesses and strengths of the method.

Date: 1964
References: Add references at CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.10.2.225 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:10:y:1964:i:2:p:225-248

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().