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 1 to 20 of 148.
Sorted by year (citations)

1 2 3 ... 6 7 8 next

  1. Accorsi, Luca; Lodi, Andrea; Vigo, Daniele: Guidelines for the computational testing of machine learning approaches to vehicle routing problems (2022)
  2. de Souza, Marcelo; Ritt, Marcus; López-Ibáñez, Manuel: Capping methods for the automatic configuration of optimization algorithms (2022)
  3. Haythorpe, Michael; Murray, Walter: Finding a Hamiltonian cycle by finding the global minimizer of a linearly constrained problem (2022)
  4. Jiang, Li; Zang, Xiaoning; Dong, Junfeng; Liang, Changyong; Mladenovic, Nenad: A variable neighborhood search for the last-mile delivery problem during major infectious disease outbreak (2022)
  5. Mbiadou Saleu, Raïssa G.; Deroussi, Laurent; Feillet, Dominique; Grangeon, Nathalie; Quilliot, Alain: The parallel drone scheduling problem with multiple drones and vehicles (2022)
  6. Taillard, Éric D.: A linearithmic heuristic for the travelling salesman problem (2022)
  7. Vidal, Thibaut: Hybrid genetic search for the CVRP: open-source implementation and SWAP* neighborhood (2022)
  8. Cohen, Eldan; Beck, J. Christopher: Heavy-tails and randomized restarting beam search in goal-oriented neural sequence decoding (2021)
  9. Emde, Simon; Tahirov, Nail; Gendreau, Michel; Glock, Christoph H.: Routing automated lane-guided transport vehicles in a warehouse handling returns (2021)
  10. Fitzpatrick, James; Ajwani, Deepak; Carroll, Paula: Learning to sparsify travelling salesman problem instances (2021)
  11. Gmira, Maha; Gendreau, Michel; Lodi, Andrea; Potvin, Jean-Yves: Tabu search for the time-dependent vehicle routing problem with time windows on a road network (2021)
  12. Mazyavkina, Nina; Sviridov, Sergey; Ivanov, Sergei; Burnaev, Evgeny: Reinforcement learning for combinatorial optimization: a survey (2021)
  13. Ozden, S. G.; Smith, A. E.; Gue, K. R.: A computational software system to design order picking warehouses (2021)
  14. Sun, Yuan; Ernst, Andreas; Li, Xiaodong; Weiner, Jake: Generalization of machine learning for problem reduction: a case study on travelling salesman problems (2021)
  15. Archetti, C.; Feillet, D.; Mor, A.; Speranza, M. G.: Dynamic traveling salesman problem with stochastic release dates (2020)
  16. Bertagnon, Alessandro: Constraint programming algorithms for route planning exploiting geometrical information (2020)
  17. Bortfeldt, Andreas; Yi, Junmin: The split delivery vehicle routing problem with three-dimensional loading constraints (2020)
  18. Cho, Doo-Hyun; Jang, Dae-Sung; Choi, Han-Lim: Memetic algorithm-based path generation for multiple Dubins vehicles performing remote tasks (2020)
  19. Glover, Fred; Kochenberger, Gary; Ma, Moses; Du, Yu: Quantum bridge analytics II: QUBO-plus, network optimization and combinatorial chaining for asset exchange (2020)
  20. Sahai, Tuhin: Dynamical systems theory and algorithms for NP-hard problems (2020)

1 2 3 ... 6 7 8 next