Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP

DOI10.1007/978-3-540-77294-1_10zbMath1136.90462OpenAlexW2101785533MaRDI QIDQ5458509

Dirk Richter, Paul Molitor, Gerold Jäger, Boris I. Goldengorin

Publication date: 15 April 2008

Published in: Combinatorial and Algorithmic Aspects of Networking (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77294-1_10

zbMATH Keywords

Traveling Salesman ProblemTolerancesBackbonesDouble Bridge TechniqueLin-Kernighan Heuristic

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (3)

The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Extending single tolerances to set tolerances ⋮ IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem

Uses Software

• LKH
• BG-WalkSAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Match twice and stitch: a new TSP tour construction heuristic.
• Configuration landscape analysis and backbone guided local search. I: Satisfiability and maximum satisfiability
• On common edges in optimal solutions to traveling salesman and other optimization problems
• Large-step Markov chains for the TSP incorporating local search heuristics
• Exponential neighbourhood local search for the traveling salesman problem
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Extended neighborhood: Definition and characterization
• Data structures and ejection chains for solving large-scale traveling salesman problems
• Tolerance-based branch and bound algorithms for the ATSP
• Further extension of the TSP assign neighborhood
• Implementation analysis of efficient heuristic algorithms for the traveling salesman problem
• Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
• Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
• Chained Lin-Kernighan for Large Traveling Salesman Problems
• Tour Merging via Branch-Decomposition
• A Multilevel Approach to the Travelling Salesman Problem
• Tolerance Based Contract-or-Patch Heuristic for the Asymmetric TSP
• Some Basics on Tolerances
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP