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 83 articles )

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

1 2 3 4 5 next

  1. Sundar, Kaarthik; Rathinam, Sivakumar: Multiple depot ring star problem: a polyhedral study and an exact algorithm (2017)
  2. Chassein, André; Goerigk, Marc: On the recoverable robust traveling salesman problem (2016)
  3. Fages, Jean-Guillaume; Lorca, Xavier; Rousseau, Louis-Martin: The salesman and the tree: the importance of search in CP (2016)
  4. Farasat, Alireza; Nikolaev, Alexander G.: Social structure optimization in team formation (2016)
  5. Gendreau, Michel; Manerba, Daniele; Mansini, Renata: The multi-vehicle traveling purchaser problem with pairwise incompatibility constraints and unitary demands: a branch-and-price approach (2016)
  6. Vidal, Thibaut: Technical note: split algorithm in $O(n)$ for the capacitated vehicle routing problem (2016)
  7. Wang, Xingyin; Golden, Bruce; Wasil, Edward; Zhang, Rui: The min-max split delivery multi-depot vehicle routing problem with minimum service time requirement (2016)
  8. Wang, Yong; Remmel, Jeffrey B.: A binomial distribution model for the traveling salesman problem based on frequency quadrilaterals (2016)
  9. Weise, Thomas; Wu, Yuezhong; Chiong, Raymond; Tang, Ke; Lässig, Jörg: Global versus local search: the impact of population sizes on evolutionary algorithm performance (2016)
  10. Çavdar, Bahar; Sokol, Joel: A distribution-free TSP tour length estimation model for random graphs (2015)
  11. Cordeau, Jean-François; Laganà, Demetrio; Musmanno, Roberto; Vocaturo, Francesca: A decomposition-based heuristic for the multiple-product inventory-routing problem (2015)
  12. Goldengorin, B.I.; Malyshev, D.S.; Pardalos, P.M.; Zamaraev, V.A.: A tolerance-based heuristic approach for the weighted independent set problem (2015)
  13. Henke, Tino; Speranza, M.Grazia; Wäscher, Gerhard: The multi-compartment vehicle routing problem with flexible compartment sizes (2015)
  14. Hoos, Holger H.; Stützle, Thomas: On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances (2015)
  15. Talarico, L.; Sörensen, K.; Springael, J.: The $k$-dissimilar vehicle routing problem (2015)
  16. Talarico, Luca; Meisel, Frank; Sörensen, Kenneth: Ambulance routing for disaster response with patient groups (2015)
  17. Talarico, Luca; Sörensen, Kenneth; Springael, Johan: Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem (2015)
  18. Yong, Wang: Hybrid MAX-MIN ant system with four vertices and three lines inequality for traveling salesman problem (2015) ioport
  19. Yu, Vincent F.; Lin, Shin-Yu: A simulated annealing heuristic for the open location-routing problem (2015)
  20. Baniasadi, Pouya; Ejov, Vladimir; Filar, Jerzy A.; Haythorpe, Michael; Rossomakhine, Serguei: Deterministic “snakes and ladders” heuristic for the Hamiltonian cycle problem (2014)

1 2 3 4 5 next