In optimization, the Lin-Kernighan algorithm is one of the best heuristics for 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.

See also

References

  • S. Lin and B. W. Kernighan (1973). An Effective Heuristic Algorithm for the Traveling-Salesman Problem. Operations Res. 21, 498-516. 
  • K. Helsgaun. "An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic". 

External links

This applied mathematics-related article is a stub. You can help Wikipedia by expanding it.
Retrieved from "http://en.wikipedia.org/wiki/Lin-Kernighan"

No comments have been added.



Your name:

City:

Country:

Your comments:

Security check *
(Please enter the number into adjoining box)