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 128 articles , 1 standard article )
Showing results 1 to 20 of 128.
Sorted by year (- 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)
- 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)
- 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)
- Ejov, Vladimir; Filar, J. A.; Haythorpe, Michael; Roddick, John F.; Rossomakhine, S.: A note on using the resistance-distance matrix to solve Hamiltonian cycle problem (2018)
- Glynn, David; Haythorpe, Michael; Moeini, Asghar: Directed in-out graphs of optimal size (2018)
- Jäger, Gerold; Turkensteen, Marcel: Extending single tolerances to set tolerances (2018)
- Mihić, Krešimir; Ryan, Kevin; Wood, Alan: Randomized decomposition solver with the quadratic assignment problem as a case study (2018)
- Pansart, Lucie; Catusse, Nicolas; Cambazard, Hadrien: Exact algorithms for the order picking problem (2018)