Implementation analysis of efficient heuristic algorithms for the traveling salesman problem

DOI10.1016/j.cor.2005.06.014zbMath1079.90110OpenAlexW2123095470MaRDI QIDQ2571201

Fred Glover, Dorabela Gamboa, César Rego

Publication date: 1 November 2005

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2005.06.014

zbMATH Keywords

traveling salesmanlocal searchdata structuresejection chains

Mathematics Subject Classification ID

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

Related Items

Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem, Data structures and ejection chains for solving large-scale traveling salesman problems, Genetic operators for combinatorial optimization in TSP and microarray gene ordering, A survey on the linear ordering problem for weighted or unweighted tournaments, A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem, Traveling salesman problem heuristics: leading methods, implementations and latest advances, Ejection chain and filter-and-fan methods in combinatorial optimization, A \(k\)-level data structure for large-scale traveling salesman problems, Ejection chain and filter-and-fan methods in combinatorial optimization, An updated survey on the linear ordering problem for weighted or unweighted tournaments, 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, Mathematical model for dynamic case-based planning

Uses Software

• TSPLIB
• Concorde
• DIMACS

Cites Work

• Unnamed Item
• A data structure useful for finding Hamiltonian cycles
• An effective implementation of the Lin-Kernighan traveling salesman heuristic
• Relaxed tours and path ejections for the traveling salesman problem
• Data structures and ejection chains for solving large-scale traveling salesman problems
• Chained Lin-Kernighan for Large Traveling Salesman Problems
• A Multilevel Approach to the Travelling Salesman Problem
• TSPLIB—A Traveling Salesman Problem Library
• Fast Heuristics for Large Geometric Traveling Salesman Problems
• Data Structures for Traveling Salesmen
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem