×

LKH

swMATH ID: 4735
Software Authors: Helsgaun, Keld
Description: 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).
Homepage: http://www.akira.ruc.dk/~keld/research/LKH/
Keywords: Lin-Kernighan heuristic; traveling salesman problem; TSP
Related Software: TSPLIB; Concorde; VRP; Tabu search; CPLEX; DIMACS; SCIP; TSPTW; GTSP Instances Library; VRPH; Scatter Search; CPU Benchmarks; Gurobi; irace; HGS-CVRP; OR-tools; SMAC; GitHub; GLPK; GTSP-LIB
Referenced in: 150 Publications
all top 5

Referenced by 310 Authors

7 Goldengorin, Boris I.
7 Haythorpe, Michael
6 Pardalos, Panos M.
6 Sörensen, Kenneth
5 Glover, Fred W.
5 Laporte, Gilbert
4 Gendreau, Michel
4 Golden, Bruce L.
4 Jacobson, Sheldon H.
4 Jäger, Gerold
4 Talarico, Luca
3 Archetti, Claudia
3 Feillet, Dominique
3 Gutin, Gregory Z.
3 Helsgaun, Keld
3 Lodi, Andrea
3 Marinakis, Yannis
3 Migdalas, Athanasios
3 Molitor, Paul
3 Nikolaev, Alexander G.
3 Punnen, Abraham P.
3 Rathinam, Sivakumar
3 Renaud, Jacques
3 Springael, Johan
3 Turkensteen, Marcel
3 Wäscher, Gerhard
2 Applegate, David L.
2 Arnold, Florian
2 Boctor, Fayez Fouad
2 Caris, An
2 Carroll, Paula
2 Cook, William John
2 Du, Yu
2 Ezhov, Vladimir Vladimirovich
2 Filar, Jerzy A.
2 Gue, Kevin R.
2 Hall, Shane N.
2 Hoos, Holger H.
2 Johnson, David Stifler
2 Kochenberger, Gary A.
2 Larusic, John
2 Ma, Moses
2 Malyshev, Dmitriĭ Sergeevich
2 Manerba, Daniele
2 Mansini, Renata
2 Matusiak, Marek
2 McGeoch, Lyle A.
2 Miranda-Bront, Juan José
2 Mor, Andrea
2 Ozden, S. G.
2 Ramaekers, Katrien M.
2 Rego, César
2 Rossomakhine, Serguei
2 Rousseau, Louis-Martin
2 Saarinen, Jari
2 Sahai, Tuhin
2 Scholz, André
2 Semet, Frédéric
2 Smith, Alice E.
2 Stützle, Thomas G.
2 Sundar, Kaarthik
2 van Gils, Teun
2 Vidal, Thibaut
2 Wang, Yong
2 Wasil, Edward A.
1 Accorsi, Luca
1 Affenzeller, Michael
1 Agarwal, Anurag
1 Ajwani, Deepak
1 Albert, Laura A.
1 Alvelos, Filipe
1 Anile, Angelo Marcello
1 Aubanel, Eric
1 Bandyopadhyay, Sanghamitra
1 Baniasadi, Pouya
1 Beasley, John E.
1 Beck, J. Christopher
1 Beham, Andreas
1 Benchimol, Pascal
1 Bertagnon, Alessandro
1 Bieding, Thomas J.
1 Bixby, Robert E.
1 Bolduc, Marie-Claude
1 Bonnet, Edouard
1 Bortfeldt, Andreas
1 Braekers, Kris
1 Burnaev, Evgeny
1 Cambazard, Hadrien
1 Cattaruzza, Diego
1 Catusse, Nicolas
1 Çavdar, Bahar
1 Chassein, André B.
1 Chen, Yingwu
1 Chen, Yongfu
1 Chen, Zhenyu
1 Chiong, Raymond
1 Chistyakov, Vyacheslav V.
1 Cho, Doo-Hyun
1 Choi, Han-Lim
1 Chvátal, Vašek
...and 210 more Authors
all top 5

Referenced in 42 Serials

30 Computers & Operations Research
23 European Journal of Operational Research
6 Annals of Operations Research
5 Journal of Global Optimization
5 Optimization Letters
5 Mathematical Programming Computation
4 Journal of the Operational Research Society
4 Computational Optimization and Applications
3 Journal of Heuristics
3 INFORMS Journal on Computing
3 Journal of Combinatorial Optimization
3 CEJOR. Central European Journal of Operations Research
2 Discrete Applied Mathematics
2 Applied Mathematics and Computation
2 Information Sciences
2 Opsearch
2 Operations Research Letters
2 International Journal of Robust and Nonlinear Control
2 Constraints
2 4OR
2 Electronic Journal of Graph Theory and Applications
1 Artificial Intelligence
1 Physica A
1 Networks
1 Neural Networks
1 Neural Computation
1 Applied Intelligence
1 Mathematical Programming. Series A. Series B
1 The Australasian Journal of Combinatorics
1 International Transactions in Operational Research
1 Mathematical Problems in Engineering
1 European Series in Applied and Industrial Mathematics (ESAIM): Control, Optimization and Calculus of Variations
1 Nonlinear Dynamics
1 Journal of Graph Algorithms and Applications
1 RAIRO. Operations Research
1 OR Spectrum
1 JMMA. Journal of Mathematical Modelling and Algorithms
1 AKCE International Journal of Graphs and Combinatorics
1 Networks and Spatial Economics
1 Discrete Optimization
1 Journal of Optimization
1 International Journal of Systems Science. Principles and Applications of Systems and Integration

Referencing Publications by Year