An Effective Heuristic Algorithm for the Traveling-Salesman Problem

S. Lin and B. W. Kernighan
Additional contact information
S. Lin: Bell Telephone Laboratories, Incorporated, Murray Hill, New Jersey
B. W. Kernighan: Bell Telephone Laboratories, Incorporated, Murray Hill, New Jersey

Operations Research, 1973, vol. 21, issue 2, 498-516

Abstract: This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem. The procedure is based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems. The procedure produces optimum solutions for all problems tested, “classical” problems appearing in the literature, as well as randomly generated test problems, up to 110 cities. Run times grow approximately as n 2 ; in absolute terms, a typical 100-city problem requires less than 25 seconds for one case (GE635), and about three minutes to obtain the optimum with above 95 per cent confidence.

Date: 1973
References: Add references at CitEc
Citations: View citations in EconPapers (230)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.21.2.498 (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:21:y:1973:i:2:p:498-516

Access Statistics for this article

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