Lin–Kernighan heuristic
From Wikipedia, the free encyclopedia
(Redirected from Lin-Kernighan)
- This article is about the heuristic for the traveling salesman problem. For a heuristic algorithm for the graph partitioning problem, see Kernighan–Lin algorithm.
In combinatorial optimization, Lin–Kernighan is one of the best heuristics for solving the Euclidean traveling salesman problem. It briefly involves swapping pairs of sub-tours to make a new tour. It is a generalization of 2-opt and 3-opt. 2-opt and 3-opt work by switching two or three paths to make the tour shorter. Lin–Kernighan is adaptive and at each step decides how many paths between cities need to be switched to find a shorter tour.
[edit] See also
[edit] References
- Lin, Shen; Kernighan, B. W. (1973). "An Effective Heuristic Algorithm for the Traveling-Salesman Problem". Operations Research 21: 498-516.
- K. Helsgaun. "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic".
- Johnson, David S.; McGeoch, Lyle A. (1997). "The Traveling Salesman Problem: A Case Study in Local Optimization". in E. H. L. Aarts and J. K. Lenstra. Local Search in Combinatorial Optimization. London: John Wiley and Sons. pp. 215-310. http://www.research.att.com/~dsj/papers/TSPchapter.pdf.
 |
This computer science article is a stub. You can help Wikipedia by expanding it. |
