An Extension of the Lin-Kernighan-Helsgaun TSP Solver for Constrained Traveling Salesman and Vehicle Routing Problems: Technical report

By Keld Helsgaun. 2017

481 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/0f450869083f8c285b62e5e8ce18af35068686a1

How researchers see this paper

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

1. Xinyun Chen
2. Quoc V. Le
3. Hanxiao Liu
4. Zhiqing Sun
5. Yi Tay
6. Yoshua Bengio
7. Yiming Yang
8. Xuezhi Wang

Citations in the corpus

• Attention, Learn to Solve Routing Problems! (2018, unknown): “…Problem (TSP) For the TSP, we report optimal results by Gurobi, as well as by Concorde (Applegate et al., 2006) (faster than Gurobi as it is specialized for TSP) and LKH3 (Helsgaun, 2017), a state-of-the-art heuristic solver that empirically also finds optimal solutions in time comparable to Gurobi.”
• Learning Improvement Heuristics for Solving Routing Problems (2019, methodology): “We compare our method with a variety of baselines, including: 1) Concorde [36], an efficient exact solver specialized for TSP; 2) LKH3 [21], a well-known heuristic solver that achieves state-of-the-art performance on various routing problems; 3) OR-Tools, a mature and widely used solver for routing…”
• Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood (2020, background): “…academic state-of-the-art: • the hybrid iterated local search (HILS) of Subramanian et al. (2013); • the Lin-Kernighan-Helsgaun (LKH-3) heuristic of Helsgaun (2017); • the knowledge guided local search (KGLS) of Arnold and S¨orensen (2018); • the slack induction by string removals (SISR) of…”
• Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model (2024, methodology): “In contrast to using the complicated local search in SOTA solvers (Helsgaun, 2017), we only adopt the two basic local search operators.”
• DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization (2023, methodology): “• Traditional OR methods include Concorde [3] and Gurobi [35], which are exact solvers, and LKH-3 [39], which is a strong heuristic solver.”
• Large Language Models as Optimizers (2023, background): “…including heuristic algorithms and solvers (Rosenkrantz et al., 1977; Golden et al., 1980; Optimization et al., 2020; Applegate et al., 2006; Helsgaun, 2017), and approaches based on training deep neural networks (Kool et al., 2019; Deudon et al., 2018; Chen & Tian, 2019; Nazari et al.,…”