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).


References in zbMATH (referenced in 147 articles , 1 standard article )

Showing results 101 to 120 of 147.
Sorted by year (citations)
  1. Jackson, Justin; Faied, M.; Girard, Anouck R.: Comparison of tabu/2-opt heuristic and optimal tree search method for assignment problems (2011)
  2. Lang, Jan Christian; Shen, Zuo-Jun Max: Fix-and-optimize heuristics for capacitated lot-sizing with sequence-dependent setups and substitutions (2011)
  3. Mete, Huseyin Onur; Shen, Yanfang; Zabinsky, Zelda B.; Kiatsupaibul, Seksan; Smith, Robert L.: Pattern discrete and mixed hit-and-run for global optimization (2011)
  4. Nikolaev, Alexander G.; Jacobson, Sheldon H.: Using Markov chains to analyze the effectiveness of local search algorithms (2011)
  5. Nikolaev, Alexander G.; Jacobson, Sheldon H.; Hall, Shane N.; Henderson, Darrall: A framework for analyzing sub-optimal performance of local search algorithms (2011)
  6. Groër, Chris; Golden, Bruce; Wasil, Edward: A library of local search heuristics for the vehicle routing problem (2010)
  7. Laporte, G.: A concise guide to the traveling salesman problem (2010)
  8. Lust, Thibaut; Teghem, Jacques: Two-phase Pareto local search for the biobjective traveling salesman problem (2010)
  9. Rego, César; Glover, Fred: Ejection chain and filter-and-fan methods in combinatorial optimization (2010)
  10. Zamani, Reza; Lau, Sim Kim: Embedding learning capability in Lagrangean relaxation: an application to the travelling salesman problem (2010)
  11. Affenzeller, Michael; Winkler, Stephan; Wagner, Stefan; Beham, Andreas: Genetic algorithms and genetic programming. Modern concepts and practical applications. (2009)
  12. Agarwal, Anurag: Theoretical insights into the augmented-neural-network approach for combinatorial optimization (2009)
  13. Bieding, Thomas; Görtz, Simon; Klose, Andreas: On line routing per mobile phone a case on subsequent deliveries of newspapers (2009)
  14. Cornillier, Fabien; Laporte, Gilbert; Boctor, Fayez F.; Renaud, Jacques: The petrol station replenishment problem with time windows (2009)
  15. Duchenne, Éric; Laporte, Gilbert; Semet, Frédéric: Heuristics for the (m)-peripatetic salesman problem (2009)
  16. Helsgaun, Keld: General (k)-opt submoves for the Lin-Kernighan TSP heuristic (2009)
  17. Marinakis, Yannis; Migdalas, Athanasios; Pardalos, Panos M.: Multiple phase neighborhood search---GRASP based on Lagrangean relaxation, random backtracking Lin-Kernighan and path relinking for the TSP (2009)
  18. Paquete, Luís; Stützle, Thomas: Design and analysis of stochastic local search for the multiobjective traveling salesman problem (2009)
  19. Ramakrishnan, Ravi; Sharma, Prabha; Punnen, Abraham P.: An efficient heuristic algorithm for the bottleneck traveling salesman problem (2009)
  20. Valkonen, Tuomo; Kärkkäinen, Tommi: Continuous reformulations and heuristics for the Euclidean travelling salesperson problem (2009)