An effective implementation of the Lin-Kernighan traveling salesman heuristic

DOI10.1016/S0377-2217(99)00284-2zbMath0969.90073OpenAlexW2017708378WikidataQ57406544 ScholiaQ57406544MaRDI QIDQ1584821

Keld Helsgaun

Publication date: 4 October 2001

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0377-2217(99)00284-2

zbMATH Keywords

heuristicstraveling salesman problemLin-Kernighan

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (only showing first 100 items - show all)

An algorithm for the one commodity pickup and delivery traveling salesman problem with restricted depot ⋮ Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem ⋮ Comparison of Tabu/2-opt heuristic and optimal tree search method for assignment problems ⋮ Approximation algorithms and heuristics for a 2-depot, heterogeneous Hamiltonian path problem ⋮ A two-stage flow-shop scheduling problem with incompatible job families and limited waiting time ⋮ Exact algorithms and heuristics for the quadratic traveling salesman problem with an application in bioinformatics ⋮ Genetic operators for combinatorial optimization in TSP and microarray gene ordering ⋮ Quantum bridge analytics. II: QUBO-plus, network optimization and combinatorial chaining for asset exchange ⋮ Efficient optimization of the Held-Karp lower bound ⋮ The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems ⋮ Order Batching and Picker Routing in manual order picking systems: the benefits of integrated routing ⋮ Improving the robustness of EPS to solve the TSP ⋮ Bifactor approximation for location routing with vehicle and facility capacities ⋮ Discrete heat transfer search for solving travelling salesman problem ⋮ A computational software system to design order picking warehouses ⋮ Reinforcement learning for combinatorial optimization: a survey ⋮ Capping methods for the automatic configuration of optimization algorithms ⋮ A transformation technique for the clustered generalized traveling salesman problem with applications to logistics ⋮ An approximation algorithm for graph partitioning via deterministic annealing neural network ⋮ Crowdsourced humanitarian relief vehicle routing problem ⋮ Optimal TSP tour length estimation using standard deviation as a predictor ⋮ A branch-and-cut approach for the distributed no-wait flowshop scheduling problem ⋮ 2-Opt Moves and Flips for Area-optimal Polygonizations ⋮ The rendezvous vehicle routing problem ⋮ Crowdsourced logistics: The pickup and delivery problem with transshipments and occasional drivers ⋮ Exact models for the flying sidekick traveling salesman problem ⋮ Optimal TSP tour length estimation using Sammon maps ⋮ A branch-and-cut algorithm for the generalized traveling salesman problem with time windows ⋮ Effective metaheuristics for the latency location routing problem ⋮ Comparison of four mechanisms for request exchange in collaborative transportation ⋮ Heuristic sequencing methods for time optimal tracking of nested, open and closed paths ⋮ A branch‐and‐dive heuristic for single vehicle snow removal ⋮ A reinforced hybrid genetic algorithm for the traveling salesman problem ⋮ An adaptive memory matheuristic for the set orienteering problem ⋮ New neighborhoods and an iterated local search algorithm for the generalized traveling salesman problem ⋮ Partition Crossover can Linearize Local Optima Lattices of k-bounded Pseudo-Boolean Functions ⋮ To improve the performance of genetic algorithms by using a novel selection operator ⋮ An efficient branch-and-cut algorithm for the parallel drone scheduling traveling salesman problem ⋮ Inter-depot moves and dynamic-radius search for multi-depot vehicle routing problems ⋮ Memetic search for the minmax multiple traveling salesman problem with single and multiple depots ⋮ On the generation of metric TSP instances with a large integrality gap by branch-and-cut ⋮ The single robot line coverage problem: Theory, algorithms, and experiments ⋮ Solving large-scale routing optimization problems with networks and only networks ⋮ Optimization of logistics services in hospitals ⋮ Cayley graphs of order kp are hamiltonian for k < 48 ⋮ Unnamed Item ⋮ Dynamical Systems Theory and Algorithms for NP-hard Problems ⋮ Randomized Decomposition Solver with the Quadratic Assignment Problem as a Case Study ⋮ A novel bio-inspired approach based on the behavior of mosquitoes ⋮ A Local-Search Algorithm for Steiner Forest ⋮ Visiting near-optimal solutions using local search algorithms ⋮ A new selection operator for genetic algorithms that balances between premature convergence and population diversity ⋮ On estimating the distribution of optimal traveling salesman tour lengths using heuristics ⋮ Special Frequency Quadrilaterals and an Application ⋮ Generalization of machine learning for problem reduction: a case study on travelling salesman problems ⋮ Ejection chain and filter-and-fan methods in combinatorial optimization ⋮ Ejection chain and filter-and-fan methods in combinatorial optimization ⋮ A tolerance-based heuristic approach for the weighted independent set problem ⋮ Tolerance-based branch and bound algorithms for the ATSP ⋮ Determination of the candidate arc set for the asymmetric traveling salesman problem ⋮ Expanding neighborhood GRASP for the traveling salesman problem ⋮ An efficient heuristic algorithm for the bottleneck traveling salesman problem ⋮ A Neural-Network-Based Approach to the Double Traveling Salesman Problem ⋮ Theoretical insights into the augmented-neural-network approach for combinatorial optimization ⋮ Estimating optimal objective values for the TSP, VRP, and other combinatorial problems using randomization ⋮ Toward solving the Steiner travelling salesman problem on urban road maps using the branch decomposition of graphs ⋮ A Sensitive Metaheuristic for Solving a Large Optimization Problem ⋮ A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse ⋮ Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP ⋮ Heuristiques pour le Problème du Vendeurm-Péripatétique ⋮ Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP ⋮ Mathematical foundation of quantum annealing ⋮ Continuous relaxations for the traveling salesman problem ⋮ The Generalized Covering Salesman Problem ⋮ The snake for visualizing and for counting clusters in multivariate data ⋮ A construction for directed in-out subgraphs of optimal size ⋮ A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP ⋮ Continuous reformulations and heuristics for the Euclidean travelling salesperson problem ⋮ Dynamic traveling salesman problem with stochastic release dates ⋮ Improving TSP Tours Using Dynamic Programming over Tree Decompositions. ⋮ On line Routing per Mobile Phone A Case on Subsequent Deliveries of Newspapers ⋮ Implementation analysis of efficient heuristic algorithms for the traveling salesman problem ⋮ Algorithms and Experimental Study for the Traveling Salesman Problem of Second Order ⋮ Constructing arbitrarily large graphs with a specified number of Hamiltonian cycles ⋮ Change ringing and Hamiltonian cycles: The search for Erin and Stedman triples ⋮ A hybrid genetic-GRASP algorithm using Lagrangean relaxation for the traveling salesman problem ⋮ Memetic algorithm-based path generation for multiple Dubins vehicles performing remote tasks ⋮ An efficient evolutionary algorithm for the ring star problem ⋮ The salesman and the tree: the importance of search in CP ⋮ Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems ⋮ Traveling salesman problems with PageRank distance on complex networks reveal community structure ⋮ Total distance approximations for routing solutions ⋮ Embedded local search approaches for routing optimization ⋮ Multiple phase neighborhood search---GRASP based on Lagrangean relaxation, random backtracking Lin-Kernighan and path relinking for the TSP ⋮ A distribution-free TSP tour length estimation model for random graphs ⋮ The \(k\)-dissimilar vehicle routing problem ⋮ Metaheuristics for the risk-constrained cash-in-transit vehicle routing problem ⋮ The multi-compartment vehicle routing problem with flexible compartment sizes ⋮ Hybrid search with neighborhood reduction for the multiple traveling salesman problem ⋮ A fresh look at the traveling salesman problem with a center

Uses Software

• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A modified Lin--Kernighan traveling-salesman heuristic
• Transforming asymmetric into symmetric traveling salesman problems
• Solution of large-scale symmetric travelling salesman problems
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• On the choice of step size in subgradient optimization
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• Quick updates for \(p\)-opt TSP heuristics
• The traveling salesman. Computational solutions for RSP applications
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Distances between traveling salesman tours
• New lower bounds for the symmetric travelling salesman problem
• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• Generating Travelling-Salesman Problems with Known Optimal Tours
• Accelerated branch exchange heuristics for symmetric traveling salesman problems
• TSPLIB—A Traveling Salesman Problem Library
• Fast Algorithms for Geometric Traveling Salesman Problems
• Fast Heuristics for Large Geometric Traveling Salesman Problems
• P-Complete Approximation Problems
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Some Examples of Difficult Traveling Salesman Problems
• On the Significance of the Initial Solution in Travelling Salesman Heuristics
• Validation of subgradient optimization
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• Data Structures for Traveling Salesmen
• Computer Solutions of the Traveling Salesman Problem
• 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

This page was built for publication: An effective implementation of the Lin-Kernighan traveling salesman heuristic