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.
Keywords
Travelling salesman problemHeuristicsMathematical optimizationHeuristicLin–Kernighan heuristicTraveling purchaser problem2-optCombinatorial optimizationBottleneck traveling salesman problemComputer scienceExtremal optimizationMathematicsAlgorithmOptimization problem
Affiliated Institutions
Related Publications
New spectral methods for ratio cut partitioning and clustering
Partitioning of circuit netlists in VLSI design is considered. It is shown that the second smallest eigenvalue of a matrix derived from the netlist gives a provably good approxi...
Handbook of Genetic Algorithms
This book sets out to explain what genetic algorithms are and how they can be used to solve real-world problems. The first objective is tackled by the editor, Lawrence Davis. Th...
Publication Info
- Year
- 1973
- Type
- article
- Volume
- 21
- Issue
- 2
- Pages
- 498-516
- Citations
- 3741
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
3741
OpenAlex
Cite This
Simon Lin,
Brian W. Kernighan
(1973).
An Effective Heuristic Algorithm for the Traveling-Salesman Problem.
Operations Research
, 21
(2)
, 498-516.
https://doi.org/10.1287/opre.21.2.498
Identifiers
- DOI
- 10.1287/opre.21.2.498