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; Gurobi; Scatter Search; SCIP; TSPTW; GTSP Instances Library; VRPH; HGS-CVRP; GitHub; CPU Benchmarks; Python; NetworkX; VRPSolver; Cvrplib; POPMUSIC Cited in: 167 Publications Standard Articles 1 Publication describing the Software, including 1 Publication in zbMATH Year An effective implementation of the Lin-Kernighan traveling salesman heuristic. Zbl 0969.90073Helsgaun, Keld 2000 all top 5 Cited by 351 Authors 7 Golden, Bruce L. 7 Goldengorin, Boris I. 7 Haythorpe, Michael 6 Pardalos, Panos M. 6 Sörensen, Kenneth 5 Glover, Fred W. 5 Jäger, Gerold 5 Laporte, Gilbert 4 Archetti, Claudia 4 Gendreau, Michel 4 Jacobson, Sheldon H. 4 Talarico, Luca 4 Turkensteen, Marcel 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 Poikonen, Stefan 3 Punnen, Abraham P. 3 Rathinam, Sivakumar 3 Renaud, Jacques 3 Springael, Johan 3 Wäscher, Gerhard 3 Wasil, Edward A. 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 Kou, Shuhan 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 Régin, Jean-Charles 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 Vigo, Daniele 2 Wang, Yong 2 Zhang, Rui 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 Avci, Mualla Gonca 1 Avci, Mustafa 1 Bandyopadhyay, Sanghamitra 1 Baniasadi, Pouya 1 Basu, Sumanta 1 Beasley, John E. 1 Beck, J. Christopher 1 Beham, Andreas 1 Benchimol, Pascal 1 Bendotti, Emilio 1 Bertagnon, Alessandro 1 Bieding, Thomas J. 1 Bixby, Robert E. 1 Bolduc, Marie-Claude 1 Bonnet, Edouard 1 Bortfeldt, Andreas 1 Bossek, Jakob 1 Braekers, Kris 1 Burnaev, Evgeny 1 Cambazard, Hadrien 1 Cattaruzza, Diego 1 Catusse, Nicolas ...and 251 more Authors all top 5 Cited in 46 Serials 34 Computers & Operations Research 24 European Journal of Operational Research 7 Optimization Letters 6 Annals of Operations Research 6 Mathematical Programming Computation 5 Journal of Global Optimization 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 Artificial Intelligence 2 Discrete Applied Mathematics 2 Applied Mathematics and Computation 2 Information Sciences 2 Opsearch 2 Theoretical Computer Science 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 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 Mathematical Biosciences and Engineering 1 Discrete Optimization 1 Engineering Optimization 1 Journal of Optimization 1 International Journal of Systems Science. Principles and Applications of Systems and Integration 1 INFOR: Information Systems and Operational Research all top 5 Cited in 9 Fields 156 Operations research, mathematical programming (90-XX) 27 Computer science (68-XX) 10 Combinatorics (05-XX) 3 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 2 Dynamical systems and ergodic theory (37-XX) 2 Numerical analysis (65-XX) 2 Biology and other natural sciences (92-XX) 2 Systems theory; control (93-XX) 1 Statistics (62-XX) Citations by Year