An Effective Heuristic Algorithm for the Traveling-Salesman Problem
By Shen Lin, B. Kernighan. 1973
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Frank Hutter
- Holger H. Hoos
- Thomas Stützle
- Yoshua Bengio
- Keld Helsgaun
- Kevin Leyton-Brown
- Marco Dorigo
- Quoc V. Le
Citations in the corpus
- The multiple traveling salesman problem: an overview of formulations and solution procedures (2006, methodology): “The algorithm is an extended version of the Lin and Kernighan [45] heuristic originally developed for the TSP.”
- General k-opt submoves for the Lin–Kernighan TSP heuristic (2009, methodology): “The Lin–Kernighan algorithm [25] belongs to the class of so-called local search algorithms [17,18,20].”
- In search of simple structures in climate: simplifying EOFs (2006, background): “Simulated annealing (Metropolis et al., 1953; Lin and Kernighan, 1973; Kirkpatrick et al., 1983) makes use of the fact that when a crystal is heated and then slowly cooled, thermal mobility of the atoms is gradually lost and the crystal gets to the state of its minimum absolute energy.”
- A Novel Set-Based Particle Swarm Optimization Method for Discrete Optimization Problems (2010, background): “According to [18], many COPs can be formulated in the abstract as “find from a set E a subset X that satisfies some constraints Ω and optimizes the objective function f”.”
- Static pickup and delivery problems: a classification scheme and survey (2007, methodology): “Their local search method, which is similar to the Lin and Kernighan (1973) algorithm for the TSP, consists of two phases.”
- Chained Lin-Kernighan for Large Traveling Salesman Problems (2003, methodology): “This kick was discussed in the original Lin and Kernighan (1973) paper in a different context.”
- A simulated annealing heuristic for the capacitated location routing problem (2010, methodology): “Construct a TSP route which starts from and ends at the depot using the Lin and Kernighan’s heuristic (1973), which is a fast and effective heuristic for TSP problems.”
- Ship Scheduling and Network Design for Cargo Routing in Liner Shipping (2008, methodology): “In essence, the algorithm utilizes Lemma (1) due to Lin and Kernighan (1973) to prune the search tree by ignoring paths with non-negative costs.”
- Guided Local Search (2010, background): “Local search for the TSP is synonymous to the k-opt moves [15].”