General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic

DOI10.1007/s12532-009-0004-6zbMath1180.90269OpenAlexW2139059344MaRDI QIDQ1043852

Keld Helsgaun

Publication date: 9 December 2009

Published in: Mathematical Programming Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s12532-009-0004-6

zbMATH Keywords

TSPtraveling salesman problemLin-Kernighan\(k\)-opt

Mathematics Subject Classification ID

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

Related Items (33)

An algorithm for the one commodity pickup and delivery traveling salesman problem with restricted depot ⋮ Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem ⋮ Quantum bridge analytics. II: QUBO-plus, network optimization and combinatorial chaining for asset exchange ⋮ An iterative matheuristic for the inventory routing problem ⋮ Capping methods for the automatic configuration of optimization algorithms ⋮ Edge Elimination in TSP Instances ⋮ A branch-and-cut algorithm for the generalized traveling salesman problem with time windows ⋮ Rearrangement events on circular genomes ⋮ Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem ⋮ A reinforced hybrid genetic algorithm for the traveling salesman problem ⋮ A branch-and-cut algorithm for the balanced traveling salesman problem ⋮ Applying topological data analysis to local search problems ⋮ On the generation of metric TSP instances with a large integrality gap by branch-and-cut ⋮ Coordinating Particle Swarm Optimization, Ant Colony Optimization and K-Opt Algorithm for Traveling Salesman Problem ⋮ \texttt{Procrustes}: a python library to find transformations that maximize the similarity between matrices ⋮ Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem ⋮ A study on the effects of normalized TSP features for automated algorithm selection ⋮ Certifying algorithms ⋮ Improved filtering for weighted circuit constraints ⋮ On the empirical time complexity of finding optimal solutions vs proving optimality for Euclidean TSP instances ⋮ Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm ⋮ A linearithmic heuristic for the travelling salesman problem ⋮ POPMUSIC for the travelling salesman problem ⋮ A tolerance-based heuristic approach for the weighted independent set problem ⋮ Computing compatible tours for the symmetric traveling salesman problem ⋮ Quantum bridge analytics II: QUBO-plus, network optimization and combinatorial chaining for asset exchange ⋮ Routing automated lane-guided transport vehicles in a warehouse handling returns ⋮ The split delivery vehicle routing problem with three-dimensional loading constraints ⋮ Global versus local search: the impact of population sizes on evolutionary algorithm performance ⋮ Certification of an optimal TSP tour through 85,900 cities ⋮ Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP ⋮ Continuous relaxations for the traveling salesman problem ⋮ An integrated local-search/set-partitioning refinement heuristic for the capacitated vehicle routing problem

Uses Software

• LKH
• Concorde
• BG-WalkSAT
• OEIS
• DIMACS

Cites Work

• Large-step Markov chains for the TSP incorporating local search heuristics
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• The traveling salesman problem and its variations
• Analysis of random restart and iterated improvement for global optimization with application to the traveling salesman problem
• Distances between traveling salesman tours
• Fast local search algorithms for the handicapped persons transportation problem
• Chained Lin-Kernighan for Large Traveling Salesman Problems
• Data Structures for Traveling Salesmen
• A Faster and Simpler Algorithm for Sorting Signed Permutations by Reversals
• Combinatorial Pattern Matching
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Algorithms for Large-scale Travelling Salesman Problems
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic