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 148 articles , 1 standard article )

Showing results 41 to 60 of 148.
Sorted by year (citations)
  1. Seeja, K. R.: HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle (2018)
  2. van Gils, Teun; Ramaekers, Katrien; Caris, An; de Koster, René B. M.: Designing efficient order picking systems by combining planning problems: state-of-the-art classification and review (2018)
  3. Khan, Indadul; Maiti, Manas Kumar; Maiti, Manoranjan: Coordinating particle swarm optimization, ant colony optimization and (K)-Opt algorithm for traveling salesman problem (2017)
  4. Kulich, Miroslav; Miranda-Bront, Juan José; Přeučil, Libor: A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment (2017)
  5. Lozano, Leonardo; Smith, J. Cole; Kurz, Mary E.: Solving the traveling salesman problem with interdiction and fortification (2017)
  6. Manerba, Daniele; Mansini, Renata; Riera-Ledesma, Jorge: The traveling purchaser problem and its variants (2017)
  7. Matusiak, Marek; de Koster, René; Saarinen, Jari: Utilizing individual picker skills to improve order batching in a warehouse (2017)
  8. Montero, Agustín; Miranda-Bront, Juan José; Méndez-Díaz, Isabel: An ILP-based local search procedure for the VRP with pickups and deliveries (2017)
  9. Ozden, S. G.; Smith, A. E.; Gue, K. R.: Solving large batches of traveling salesman problems with parallel and distributed computing (2017)
  10. Pferschy, Ulrich; Staněk, Rostislav: Generating subtour elimination constraints for the TSP from pure integer solutions (2017)
  11. Schneider, Michael; Drexl, Michael: A survey of the standard location-routing problem (2017)
  12. Scholz, André; Schubert, Daniel; Wäscher, Gerhard: Order picking with multiple pickers and due dates -- simultaneous solution of order batching, batch assignment and sequencing, and picker routing problems (2017)
  13. Scholz, A.; Wäscher, G.: Order Batching and Picker Routing in manual order picking systems: the benefits of integrated routing (2017)
  14. Smith, Stephen L.; Imeson, Frank: GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem (2017)
  15. Sundar, Kaarthik; Rathinam, Sivakumar: Multiple depot ring star problem: a polyhedral study and an exact algorithm (2017)
  16. Talarico, Luca; Springael, Johan; Sörensen, Kenneth; Talarico, Fabio: A large neighbourhood metaheuristic for the risk-constrained cash-in-transit vehicle routing problem (2017)
  17. Turkensteen, Marcel; Malyshev, Dmitry; Goldengorin, Boris; Pardalos, Panos M.: The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems (2017)
  18. Chassein, André; Goerigk, Marc: On the recoverable robust traveling salesman problem (2016)
  19. Fages, Jean-Guillaume; Lorca, Xavier; Rousseau, Louis-Martin: The salesman and the tree: the importance of search in CP (2016)
  20. Farasat, Alireza; Nikolaev, Alexander G.: Social structure optimization in team formation (2016)