An effective implementation of the Lin-Kernighan traveling salesman heuristic

By Keld Helsgaun. 2000

1,782 citations recorded by the source corpus.

Subfields: Automotive Engineering, Industrial and Manufacturing Engineering, Transportation

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Industrial and Manufacturing Engineering

In Transportation

Citations in the corpus

Neural Combinatorial Optimization with Reinforcement Learning (2016, methodology): “Similarly, the Lin-Kernighan-Helsgaun heuristic (Helsgaun, 2000), inspired from the Lin-Kernighan heuristic (Lin & Kernighan, 1973), is a state of the art approximate search heuristic for the symmetric TSP and has been shown to solve instances with hundreds of nodes to optimality.”
An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report (2017, methodology): “The Lin-Kernighan-Helsgaun TSP solver, LKH [1, 2], is a state-of-the-art heuristic solver for the traveling salesman problem.”
Automated Algorithm Selection: Survey and Perspectives (2018, background): “Further modiﬁcations of these algorithms – e.g., based on the alternative crossover operator proposed by Sanches et al. (2017a,b), which recently was integrated into LKH (Tin´os et al., 2018) – might achieve even better performance; however, to this date, we are not aware of conclusive evidence to t”
Algorithm runtime prediction: Methods & evaluation (2012, methodology): “On these instance sets, we ran the state-of-the-art systematic and local search algorithms, Concorde [2] and LK-H [40].”
Designing efficient order picking systems by combining planning problems: State-of-the-art classification and review (2017, methodology): “The Lin-Kernighan-Helsaun routing heuristic (Helsgaun, 2000) has shown to provide excellent results to approximate the optimal route of order pickers for multiple warehouse blocks as well.”
FUEL: Fast UAV Exploration Using Incremental Frontier Structure and Hierarchical Planning (2020, methodology): “In global tour planning, the ATSP is solved using a Lin-Kernighan-Helsgaun heuristic solver [33].”
Diffusion models as plug-and-play priors (2022, methodology): “However, the optimization algorithms in common use for solving the TSP do not use a vision inductive bias, instead falling into two broad categories: • Discrete combinatorial optimization algorithms and efficient integer programming solvers, studied for decades in the optimization literature [22, 12”
Towards interactive Machine Learning (iML): Applying Ant Colony Algorithms to Solve the Traveling Salesman Problem with the Human-in-the-Loop Approach (2016, positive): “After the inner rule the Lin-Kernighan 2-opt and 3-opt [39] are used to improve the local solution.”
Traveling Salesman Problem (2008, background): “[5] Essentially, the Lin-Kernighan algorithm considers ascending values for k for each iteration, given that a specific k is being studied, the algorithm checks to see if the next value should even be deliberated.”
General k-opt submoves for the Lin–Kernighan TSP heuristic (2009, methodology): “The new implementation, called LKH-2, eliminates many of the limitations and shortcomings of LKH-1.”
MatrixExplorer: a Dual-Representation System to Explore Social Networks (2006, methodology): “To solve TSP, we use a fast heuristic described in [ 21 ].”
An improvement heuristic framework for the laser cutting tool path problem (2015, methodology): “The resulting ATSP can be efficiently solved to near-optimality in a limited time span using a newer version of the Lin Kernighan heuristic (LKH) proposed by Helsgaun (2000, 2009).”