Approximate Traveling Salesman Algorithms

B. Golden, L. Bodin, T. Doyle and W. Stewart
Additional contact information
B. Golden: University of Maryland, College Park, Maryland
L. Bodin: University of Maryland, College Park, Maryland
T. Doyle: University of Maryland, College Park, Maryland
W. Stewart: University of Maryland, College Park, Maryland

Operations Research, 1980, vol. 28, issue 3-part-ii, 694-711

Abstract: There have been a multitude of heuristic algorithms proposed for the solution of large scale traveling salesman problems. Our intent in this paper is to examine some of these well known heuristics, to introduce some new heuristics, and to compare these approximate techniques on the basis of efficiency and accuracy. We emphasize the strengths and weaknesses of each algorithm tested. One of our major conclusions is that it is not difficult to get within 2–3% of optimality using a composite heuristic which requires on the order of n 3 computations where n is the number of nodes in the network.

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

Downloads: (external link)
http://dx.doi.org/10.1287/opre.28.3.694 (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:oropre:v:28:y:1980:i:3-part-ii:p:694-711

Access Statistics for this article

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