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

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

1 2 3 4 next

  1. Fages, Jean-Guillaume; Lorca, Xavier; Rousseau, Louis-Martin: The salesman and the tree: the importance of search in CP (2016)
  2. Wang, Yong; Remmel, Jeffrey B.: A binomial distribution model for the traveling salesman problem based on frequency quadrilaterals (2016)
  3. Goldengorin, B.I.; Malyshev, D.S.; Pardalos, P.M.; Zamaraev, V.A.: A tolerance-based heuristic approach for the weighted independent set problem (2015)
  4. Hoos, Holger H.; Stützle, Thomas: On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances (2015)
  5. Baniasadi, Pouya; Ejov, Vladimir; Filar, Jerzy A.; Haythorpe, Michael; Rossomakhine, Serguei: Deterministic “snakes and ladders” heuristic for the Hamiltonian cycle problem (2014)
  6. Dowlatshahi, Mohammad Bagher; Nezamabadi-pour, Hossein; Mashinchi, Mashaallah: A discrete gravitational search algorithm for solving combinatorial optimization problems (2014)
  7. Fischer, A.; Fischer, F.; Jäger, G.; Keilwagen, J.; Molitor, P.; Grosse, I.: Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics (2014)
  8. Florios, Kostas; Mavrotas, George: Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems (2014)
  9. Hutter, Frank; Xu, Lin; Hoos, Holger H.; Leyton-Brown, Kevin: Algorithm runtime prediction: methods & evaluation (2014)
  10. Matusiak, Marek; de Koster, René; Kroon, Leo; Saarinen, Jari: A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse (2014)
  11. Feng, Xiang; Lau, Francis C.M.; Yu, Huiqun: A novel bio-inspired approach based on the behavior of mosquitoes (2013)
  12. Benchimol, Pascal; van Hoeve, Willem-Jan; Régin, Jean-Charles; Rousseau, Louis-Martin; Rueher, Michel: Improved filtering for weighted circuit constraints (2012)
  13. Chistyakov, Vyacheslav V.; Goldengorin, Boris I.; Pardalos, Panos M.: Extremal values of global tolerances in combinatorial optimization with an additive objective function (2012)
  14. Créput, Jean-Charles; Hajjam, Amir; Koukam, Abderrafiaa; Kuhn, Olivier: Self-organizing maps in population based metaheuristic to the dynamic vehicle routing problem (2012)
  15. Germs, Remco; Goldengorin, Boris; Turkensteen, Marcel: Lower tolerance-based branch and bound algorithms for the ATSP (2012)
  16. Golden, Bruce; Naji-Azimi, Zahra; Raghavan, S.; Salari, Majid; Toth, Paolo: The generalized covering salesman problem (2012)
  17. Karapetyan, Daniel; Gutin, Gregory: Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem (2012)
  18. Rodríguez, Alejandro; Ruiz, Rubén: A study on the effect of the asymmetry on real capacitated vehicle routing problems (2012)
  19. Doshi, Riddhi; Yadlapalli, Sai; Rathinam, Sivakumar; Darbha, Swaroop: Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem (2011)
  20. Fortini, Matteo; Letchford, Adam N.; Lodi, Andrea; Wenger, Klaus M.: Computing compatible tours for the symmetric traveling salesman problem (2011)

1 2 3 4 next