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

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

1 2 3 4 5 next

  1. Burger, M.; Su, Z.; De Schutter, B.: A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem (2018)
  2. de Oliveira da Costa, Paulo Roberto; Mauceri, Stefano; Carroll, Paula; Pallonetto, Fabiano: A genetic algorithm for a green vehicle routing problem (2018)
  3. Rais, Abdur; Alvelos, Filipe; Figueiredo, João; Nobre, Ana: Optimization of logistics services in hospitals (2018)
  4. 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)
  5. Manerba, Daniele; Mansini, Renata; Riera-Ledesma, Jorge: The traveling purchaser problem and its variants (2017)
  6. Matusiak, Marek; de Koster, René; Saarinen, Jari: Utilizing individual picker skills to improve order batching in a warehouse (2017)
  7. 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)
  8. Pferschy, Ulrich; Staněk, Rostislav: Generating subtour elimination constraints for the TSP from pure integer solutions (2017)
  9. Schneider, Michael; Drexl, Michael: A survey of the standard location-routing problem (2017)
  10. 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)
  11. Sundar, Kaarthik; Rathinam, Sivakumar: Multiple depot ring star problem: a polyhedral study and an exact algorithm (2017)
  12. Chassein, André; Goerigk, Marc: On the recoverable robust traveling salesman problem (2016)
  13. Fages, Jean-Guillaume; Lorca, Xavier; Rousseau, Louis-Martin: The salesman and the tree: the importance of search in CP (2016)
  14. Farasat, Alireza; Nikolaev, Alexander G.: Social structure optimization in team formation (2016)
  15. 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)
  16. Han, Lanshan; Luong, Binh T.; Ukkusuri, Satish: An algorithm for the one commodity pickup and delivery traveling salesman problem with restricted depot (2016)
  17. Haythorpe, Michael: Reducing the generalised Sudoku problem to the Hamiltonian cycle problem (2016)
  18. Vidal, Thibaut: Technical note: Split algorithm in $O(n)$ for the capacitated vehicle routing problem (2016)
  19. Wang, Xingyin; Golden, Bruce; Wasil, Edward; Zhang, Rui: The min-max split delivery multi-depot vehicle routing problem with minimum service time requirement (2016)
  20. Wang, Yong; Remmel, Jeffrey B.: A binomial distribution model for the traveling salesman problem based on frequency quadrilaterals (2016)

1 2 3 4 5 next