Chained Lin-Kernighan for Large Traveling Salesman Problems
From MaRDI portal
Publication:2884550
DOI10.1287/ijoc.15.1.82.15157zbMath1238.90125OpenAlexW2140425706MaRDI QIDQ2884550
André Rohe, David L. Applegate, William Cook
Publication date: 30 May 2012
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/2de975652951a58e004a11c5041ad7a36f9fc91b
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)
Related Items (39)
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 ⋮ TSP race: minimizing completion time in time-sensitive applications ⋮ Genetic operators for combinatorial optimization in TSP and microarray gene ordering ⋮ Perturbed decomposition algorithm applied to the multi-objective traveling salesman problem ⋮ Proper balance between search towards and along Pareto front: biobjective TSP case study ⋮ Solving large-scale TSP using a fast wedging insertion partitioning approach ⋮ A weighted-sum method for solving the bi-objective traveling thief problem ⋮ A transformation technique for the clustered generalized traveling salesman problem with applications to logistics ⋮ Exponential neighborhood search for consecutive block minimization ⋮ An ILP-refined tabu search for the directed profitable rural postman problem ⋮ Discovering the suitability of optimisation algorithms by learning from evolved instances ⋮ Traveling salesman problem heuristics: leading methods, implementations and latest advances ⋮ Knowledge-guided local search for the vehicle routing problem ⋮ Memetic algorithm based on improved inver-over operator and Lin-Kernighan local search for the Euclidean traveling salesman problem ⋮ Dubins traveling salesman problem with neighborhoods: a graph-based approach ⋮ An efficient local search for the feedback vertex set problem ⋮ An improvement heuristic based on variable neighborhood search for a dynamic orienteering problem ⋮ A Genetic Algorithm for Multi-component Optimization Problems: The Case of the Travelling Thief Problem ⋮ Efficiently solving very large-scale routing problems ⋮ A discrete gravitational search algorithm for solving combinatorial optimization problems ⋮ Generalization of machine learning for problem reduction: a case study on travelling salesman problems ⋮ A linearithmic heuristic for the travelling salesman problem ⋮ Ejection chain and filter-and-fan methods in combinatorial optimization ⋮ Ejection chain and filter-and-fan methods in combinatorial optimization ⋮ POPMUSIC for the travelling salesman problem ⋮ The packing while traveling problem ⋮ A location-routing problem in glass recycling ⋮ Two-phase Pareto local search for the biobjective traveling salesman problem ⋮ Exact algorithms for the order picking problem ⋮ Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP ⋮ A polynomial matrix processing heuristic algorithm for finding high quality feasible solutions for the TSP ⋮ Speed-up techniques for solving large-scale biobjective TSP ⋮ An effective local search for the maximum clique problem ⋮ General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic ⋮ Efficiently solving the traveling thief problem using hill climbing and simulated annealing ⋮ Implementation analysis of efficient heuristic algorithms for the traveling salesman problem ⋮ A note on single alternating cycle neighborhoods for the TSP ⋮ An integrated local-search/set-partitioning refinement heuristic for the capacitated vehicle routing problem
Uses Software
This page was built for publication: Chained Lin-Kernighan for Large Traveling Salesman Problems
