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

Showing results 1 to 20 of 119.
Sorted by year (citations)

1 2 3 4 5 6 next

  1. Archetti, C.; Feillet, D.; Mor, A.; Speranza, M. G.: Dynamic traveling salesman problem with stochastic release dates (2020)
  2. Arnold, Florian; Gendreau, Michel; Sörensen, Kenneth: Efficiently solving very large-scale routing problems (2019)
  3. Arnold, Florian; Sörensen, Kenneth: Knowledge-guided local search for the vehicle routing problem (2019)
  4. 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)
  5. 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)
  6. Archetti, Claudia; Fernández, Elena; Huerta-Muñoz, Diana L.: A two-phase solution algorithm for the flexible periodic vehicle routing problem (2018)
  7. Burger, M.; Su, Z.; De Schutter, B.: A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem (2018)
  8. de Oliveira da Costa, Paulo Roberto; Mauceri, Stefano; Carroll, Paula; Pallonetto, Fabiano: A genetic algorithm for a green vehicle routing problem (2018)
  9. 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)
  10. Glynn, David; Haythorpe, Michael; Moeini, Asghar: Directed in-out graphs of optimal size (2018)
  11. Jäger, Gerold; Turkensteen, Marcel: Extending single tolerances to set tolerances (2018)
  12. Pansart, Lucie; Catusse, Nicolas; Cambazard, Hadrien: Exact algorithms for the order picking problem (2018)
  13. Rais, Abdur; Alvelos, Filipe; Figueiredo, João; Nobre, Ana: Optimization of logistics services in hospitals (2018)
  14. Seeja, K. R.: HybridHAM: a novel hybrid heuristic for finding Hamiltonian cycle (2018)
  15. 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)
  16. 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)
  17. Lozano, Leonardo; Smith, J. Cole; Kurz, Mary E.: Solving the traveling salesman problem with interdiction and fortification (2017)
  18. Manerba, Daniele; Mansini, Renata; Riera-Ledesma, Jorge: The traveling purchaser problem and its variants (2017)
  19. Matusiak, Marek; de Koster, René; Saarinen, Jari: Utilizing individual picker skills to improve order batching in a warehouse (2017)
  20. 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)

1 2 3 4 5 6 next