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 147 articles , 1 standard article )

Showing results 121 to 140 of 147.
Sorted by year (citations)

previous 1 2 3 ... 5 6 7 8 next

  1. Jozefowiez, Nicolas; Glover, Fred; Laguna, Manuel: Multi-objective meta-heuristics for the traveling salesman problem with profits (2008)
  2. Julstrom, Bryant A.: A permutation coding with heuristics for the uncapacitated facility location problem (2008)
  3. Marinakis, Yannis; Migdalas, Athanasios; Pardalos, Panos M.: Expanding neighborhood search-GRASP for the probabilistic traveling salesman problem (2008)
  4. Gutin, Gregory; Goldengorin, Boris; Huang, Jing: Worst case analysis of max-regret, greedy and other heuristics for multidimensional assignment and traveling salesman problems (2007)
  5. Laporte, Gilbert; Rodríguez Martín, Inmaculada: Locating a cycle in a transportation or a telecommunications network (2007)
  6. Ray, Shubhra Sankar; Bandyopadhyay, Sanghamitra; Pal, Sankar K.: Genetic operators for combinatorial optimization in TSP and microarray gene ordering (2007)
  7. Richter, Dirk; Goldengorin, Boris; Jäger, Gerold; Molitor, Paul: Improving the efficiency of Helsgaun’s Lin-Kernighan heuristic for the symmetric TSP (2007)
  8. Vogt, L.; Poojari, C. A.; Beasley, J. E.: A tabu search algorithm for the single vehicle routing allocation problem (2007)
  9. Xing, Li-Ning; Chen, Ying-Wu; Shen, Xue-Shi: Multiprogramming genetic algorithm for optimization problems with permutation property (2007)
  10. Bolduc, Marie-Claude; Renaud, Jacques; Montreuil, Benoit: Synchronized routing of seasonal products through a production/distribution network (2006)
  11. Glover, Fred; Rego, César: Ejection chain and filter-and-fan methods in combinatorial optimization (2006)
  12. Goldengorin, Boris; Jäger, Gerold; Molitor, Paul: Tolerance based contract-or-patch heuristic for the asymmetric TSP (2006)
  13. Jacobson, Sheldon H.; Hall, Shane N.; McLay, Laura A.: Visiting near-optimal solutions using local search algorithms (2006)
  14. Cowling, P. I.; Keuthen, R.: Embedded local search approaches for routing optimization (2005)
  15. Kwon, Sang-Ho; Kim, Hun-Tae; Kang, Maing-Kyu: Determination of the candidate arc set for the asymmetric traveling salesman problem (2005)
  16. Marinakis, Yannis; Migdalas, Athanasios; Pardalos, Panos M.: Expanding neighborhood GRASP for the traveling salesman problem (2005)
  17. Nieberg, Tim; Hurink, Johann; Kern, Walter: A robust PTAS for maximum weight independent sets in unit disk graphs (2004)
  18. Renaud, J.; Boctor, F. F.; Laporte, G.: Efficient heuristics for median cycle problems (2004)
  19. Applegate, David; Bixby, Robert; Chvátal, Vašek; Cook, William: Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems (2003)
  20. Applegate, David; Cook, William; Rohe, André: Chained Lin-Kernighan for large traveling salesman problems (2003)

previous 1 2 3 ... 5 6 7 8 next