This Article Full Text (PDF) Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Golden, B. Articles by Stewart, W. Search for Related Content

Approximate Traveling Salesman Algorithms

University of Maryland, College Park, Maryland
University of Maryland, College Park, Maryland
University of Maryland, College Park, Maryland
University of Maryland, College Park, Maryland

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³ computations where n is the number of nodes in the network.

This article has been cited by other articles:

				J. M. WIENER, M. LAFON, and A. BERTHOZ Path planning under spatial uncertainty Mem Cognit, April 1, 2008; 36(3): 495 - 504. [Abstract] [PDF]

				P. Schermerhorn and M. Scheutz Investigating the Adaptiveness of Communication in Multi-Agent Behavior Coordination Adaptive Behavior, December 1, 2007; 15(4): 423 - 445. [Abstract] [PDF]