LKH
LKH is an effective implementation of the Lin-Kernighan heuristic for solving the traveling salesman problem. Computational experiments have shown that LKH is highly effective. Even though the algorithm is approximate, optimal solutions are produced with an impressively high frequency. LKH has produced optimal solutions for all solved problems we have been able to obtain; including a 85,900-city instance (at the time of writing, the largest nontrivial instance solved to optimality). Furthermore, the algorithm has improved the best known solutions for a series of large-scale instances with unknown optima, among these a 1,904,711-city instance (World TSP).
Keywords for this software
References in zbMATH (referenced in 134 articles , 1 standard article )
Showing results 1 to 20 of 134.
Sorted by year (- Taillard, Éric D.: A linearithmic heuristic for the travelling salesman problem (2022)
- Emde, Simon; Tahirov, Nail; Gendreau, Michel; Glock, Christoph H.: Routing automated lane-guided transport vehicles in a warehouse handling returns (2021)
- Sun, Yuan; Ernst, Andreas; Li, Xiaodong; Weiner, Jake: Generalization of machine learning for problem reduction: a case study on travelling salesman problems (2021)
- Archetti, C.; Feillet, D.; Mor, A.; Speranza, M. G.: Dynamic traveling salesman problem with stochastic release dates (2020)
- Bortfeldt, Andreas; Yi, Junmin: The split delivery vehicle routing problem with three-dimensional loading constraints (2020)
- Glover, Fred; Kochenberger, Gary; Ma, Moses; Du, Yu: Quantum bridge analytics II: QUBO-plus, network optimization and combinatorial chaining for asset exchange (2020)
- Sahai, Tuhin: Dynamical systems theory and algorithms for NP-hard problems (2020)
- Waissi, Gary R.; Kaushal, Pragya: A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP (2020)
- Yuan, Yuan; Cattaruzza, Diego; Ogier, Maxime; Semet, Frédéric: A branch-and-cut algorithm for the generalized traveling salesman problem with time windows (2020)
- Arnold, Florian; Gendreau, Michel; Sörensen, Kenneth: Efficiently solving very large-scale routing problems (2019)
- Arnold, Florian; Sörensen, Kenneth: Knowledge-guided local search for the vehicle routing problem (2019)
- Haythorpe, Michael; Johnson, Andrew: Change ringing and Hamiltonian cycles: the search for Erin and Stedman triples (2019)
- Sahai, Tuhin; Ziessler, Adrian; Klus, Stefan; Dellnitz, Michael: Continuous relaxations for the traveling salesman problem (2019)
- van Gils, Teun; Caris, An; Ramaekers, Katrien; Braekers, Kris: Formulating and solving the integrated batching, routing, and picker scheduling problem in a real-life spare parts warehouse (2019)
- Wang, Yong: Special frequency quadrilaterals and an application (2019)
- Wu, Zhengtian; Karimi, Hamid Reza; Dang, Chuangyin: An approximation algorithm for graph partitioning via deterministic annealing neural network (2019)
- Archetti, Claudia; Feillet, Dominique; Mor, Andrea; Speranza, M. Grazia: An iterated local search for the traveling salesman problem with release dates and completion time minimization (2018)
- Archetti, Claudia; Fernández, Elena; Huerta-Muñoz, Diana L.: A two-phase solution algorithm for the flexible periodic vehicle routing problem (2018)
- Burger, M.; Su, Z.; De Schutter, B.: A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem (2018)
- de Oliveira da Costa, Paulo Roberto; Mauceri, Stefano; Carroll, Paula; Pallonetto, Fabiano: A genetic algorithm for a green vehicle routing problem (2018)