An effective implementation of the Lin-Kernighan traveling salesman heuristic

Keywords

Travelling salesman problem, Heuristic, Mathematical optimization, Computer science, Traveling purchaser problem

References

• Computational experiments with some approximation algorithms for the travelling salesman problemA. Adrabiński, Maciej M. Sysło — 1983
• Large-Step Markov Chains for the Traveling Salesman ProblemOlivier Martin — 1991
• Finding Cuts in the TSP (A preliminary report)David Applegate, Robert E. Bixby, Vašek Chvátal — 1995
• Der Saccus endolymphaticus bei EntzündungsprozessenJ.P. Secrétan — 1944
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problemKeld Helbig Hansen, Jakob Krarup — 1974
• Fast Heuristics for Large Geometric Traveling Salesman ProblemsGerhard Reinelt — 1992
• The traveling salesman problem: An overview of exact and approximate algorithmsGilbert Laporte — 1992
• Exact Solution of Large Asymmetric Traveling Salesman ProblemsDonald L. Miller, Joseph F. Pekny — 1991
• Algorithms for Large-scale Travelling Salesman ProblemsNicos Christofides, Samuel Eilon — 1972
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxationTon Volgenant, Roy Jonker — 1982
• Accelerated branch exchange heuristics for symmetric traveling salesman problemsWilliam R. Stewart — 1987
• The Traveling-Salesman Problem and Minimum Spanning TreesMichael Held, Richard M. Karp — 1970
• The shortest path through many pointsJillian Beardwood, John H. Halton, J. M. Hammersley — 1959
• On the Significance of the Initial Solution in Travelling Salesman HeuristicsJukka Perttunen — 1994
• Validation of subgradient optimizationMichael Held, Philip Wolfe, Harlan Crowder — 1974
• Shortest connection networks and some generalizationsR. C. Prim — 1957
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman ProblemsManfred Padberg, Giovanni Rinaldi — 1991
• The symmetric traveling salesman problem and edge exchanges in minimal 1-treesTon Volgenant, Roy Jonker — 1983
• Quick updates for p-opt TSP heuristicsF. Margot — 1992
• An Effective Heuristic Algorithm for the Traveling-Salesman ProblemSimon Lin, Brian W. Kernighan — 1973

Cited by

• Visibility problems for sensor networks and unmanned air vehiclesKarl J. Obermeyer — 2010
• GENERATING SIMILARITY-BASED PLAYLISTS USING TRAVELING SALESMAN ALGORITHMSTim Pohle, Elias Pampalk, Gerhard Widmer — 2005
• A Variable Depth Sequential Search Heuristic for the Quadratic Assignment ProblemGerald Paul — 2009
• Multi-Goal Path Optimization for Robotic Systems with Redundancy based on the Traveling Salesman Problem with NeighborhoodsIacopo Gentilini — 2012
• A Study of Four Network Problems in Transportation, Telecommunications, and Supply Chain ManagementSi Chen — 2007
• Recherche locale pour l'optimisation en variables mixtes : méthodologie et applications industrielles. (Local search for mixed-integer optimization : methodology and industrial applications)Antoine Jeanjean — 2011
• A Decomposition Algorithm for Uniform Traveling Salesman ProblemRoman Bazylevych, Bhanu Prasad, Roman Kutelmakh — 2009
• Assessing the Finite-Time Performance of Local Search AlgorithmsDarrall Henderson, Lieutenant Colonel, Sheldon H. Jacobson — 2001
• A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits BackbonesWeixiong Zhang, Moshe Looks — 2005
• Improving the Bees Algorithm for Complex Optimisation ProblemsSameh Otri — 2016
• A Theoretical Framework to Solve the TSPs as Classification Problems and Shortest Hamiltonian Path ProblemsAkihiko Kawashima, Yasuo Sugai — 2014
• Procedimientos exactos y heurísticos para resolver problemas de rutas con recogida y entrega de mercancíaHipólito Hernández Pérez — 2004
• A Computational Analysis on a Hybrid Approach: Quick-and-dirty ant colony optimizationPaola Pellegrini, E. Moretti — 2009
• Improving the performance of greedy heuristics for TSPs using tolerancesDiptesh Ghosh, Boris Goldengorin, Gregory Gutin — 2007
• Formulations and Algorithms for Routing ProblemsM. Salari — 2010
• Recherche locale haute performance pour la planification des interventions à France TélécomBertrand Estellon, Frédéric Gardi, Karim Nouioua — 2008
• Constrained Task Assignment and Scheduling On Networks of Arbitrary TopologyJustin Jackson — 2012
• Differential evolution optimisation of a two echelon inventory system.Fergus Haverty — 2011
• Algorithms for Combinatorial Optimization ProblemsZahra Naji Azimi — 2010
• Software framework for vehicle routing problem with hybrid metaheuristic algorithmsSuraya Masrom, A. M. Nasir, Siti Z. Z. Abidin — 2011

Related papers

• The Solutions to Traveling Salesman ProblemShuran Liao — 2023
• An empirical investigation into randomly generated Euclidean symmetric traveling salesman problemsMegha Sharma, Diptesh Ghosh — 2006
• The travelling salesman problemKaja Zupanc — 2012
• Combined Algorithm for Solving the Asymmetric Traveling Salesman Problem as Applied to Transport Logistics ProblemsMichael Ulyanov, Michael Fomichev — 2022
• Cellular Competitive Decision Algorithm for Traveling Salesman ProblemXiaohua Xiong, Aibing Ning — 2014
• A New Multiperiod Multiple Traveling Salesman Problem with Heuristic and Application to a Scheduling ProblemKenneth Gilbert, Ruth B. Hofstra — 1992
• Computation and Simulation Analysis of a Kind of Multiple Traveling Salesman problemYan Yang — 2009
• Dynasearch algorithms for solving time dependent traveling salesman problemDa Jun Zhao — 2008
• An Approximation Algorithm for the Maximum Traveling Salesman ProblemA.Yu. Evnin, N.I. Yusova — 2017
• A Review of the Optimization Algorithms on Traveling Salesman ProblemN. Sathya, A. Muthukumaravel — 2015