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

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

1 2 3 4 5 next

  1. Matusiak, Marek; de Koster, René; Saarinen, Jari: Utilizing individual picker skills to improve order batching in a warehouse (2017)
  2. 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)
  3. Pferschy, Ulrich; Staněk, Rostislav: Generating subtour elimination constraints for the TSP from pure integer solutions (2017)
  4. Schneider, Michael; Drexl, Michael: A survey of the standard location-routing problem (2017)
  5. 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)
  6. Sundar, Kaarthik; Rathinam, Sivakumar: Multiple depot ring star problem: a polyhedral study and an exact algorithm (2017)
  7. Chassein, André; Goerigk, Marc: On the recoverable robust traveling salesman problem (2016)
  8. Fages, Jean-Guillaume; Lorca, Xavier; Rousseau, Louis-Martin: The salesman and the tree: the importance of search in CP (2016)
  9. Farasat, Alireza; Nikolaev, Alexander G.: Social structure optimization in team formation (2016)
  10. 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)
  11. Han, Lanshan; Luong, Binh T.; Ukkusuri, Satish: An algorithm for the one commodity pickup and delivery traveling salesman problem with restricted depot (2016)
  12. Haythorpe, Michael: Reducing the generalised Sudoku problem to the Hamiltonian cycle problem (2016)
  13. Vidal, Thibaut: Technical note: Split algorithm in $O(n)$ for the capacitated vehicle routing problem (2016)
  14. Wang, Xingyin; Golden, Bruce; Wasil, Edward; Zhang, Rui: The min-max split delivery multi-depot vehicle routing problem with minimum service time requirement (2016)
  15. Wang, Yong; Remmel, Jeffrey B.: A binomial distribution model for the traveling salesman problem based on frequency quadrilaterals (2016)
  16. 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)
  17. Çavdar, Bahar; Sokol, Joel: A distribution-free TSP tour length estimation model for random graphs (2015)
  18. Cordeau, Jean-François; Laganà, Demetrio; Musmanno, Roberto; Vocaturo, Francesca: A decomposition-based heuristic for the multiple-product inventory-routing problem (2015)
  19. Goldengorin, B.I.; Malyshev, D.S.; Pardalos, P.M.; Zamaraev, V.A.: A tolerance-based heuristic approach for the weighted independent set problem (2015)
  20. Henke, Tino; Speranza, M.Grazia; Wäscher, Gerhard: The multi-compartment vehicle routing problem with flexible compartment sizes (2015)

1 2 3 4 5 next