The traveling salesman problem: An overview of exact and approximate algorithms

DOI10.1016/0377-2217(92)90138-YzbMath0760.90089WikidataQ115202544 ScholiaQ115202544MaRDI QIDQ1194761

Gilbert Laporte

Publication date: 11 October 1992

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

zbMATH Keywords

survey; traveling salesman; heuristic algorithms; complexity analysis; exact algorithms

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming

Related Items

On the vehicle routing problem, The Rural Postman Problem on mixed graphs with turn penalties, The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times, Multiple phase neighborhood search---GRASP based on Lagrangean relaxation, random backtracking Lin-Kernighan and path relinking for the TSP, A (0-1) goal programming model for scheduling the tour of a marketing executive, Synchronized routing of seasonal products through a production/distribution network, Real-time split-delivery pickup and delivery time window problems with transfers, Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming, Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching, The vehicle routing problem: An overview of exact and approximate algorithms, Genetic algorithms and traveling salesman problems, A new subtour elimination constraint for the vehicle routing problem, Planning models for freight transportation, An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs, Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: An empirical study, Workload planning in small lot printed circuit board assembly, A multiple traveling salesman problem model for hot rolling scheduling in Shanghai Baoshan Iron \& Steel Complex, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Vehicle routing-scheduling for waste collection in Hanoi, Current modeling practices in bank courier scheduling, Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems, Extensions to the generalised assignment heuristic for vehicle routing, Guided local search and its application to the traveling salesman problem, Designing multi-vehicle delivery tours in a grid-cell format, A sweep-based algorithm for the fleet size and mix vehicle routing problem, A new heuristic for the period traveling salesman problem, Routing problems: A bibliography, Divide and conquer strategies for parallel TSP heuristics, Genetic algorithms for the traveling salesman problem, Integration of equipment planning and project scheduling, Expanding neighborhood GRASP for the traveling salesman problem, Searching the components of the solution: The factor-based random search algorithm for ETSP, Efficient operation of a surface mounting machine with a multihead turret

Uses Software

• VRP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Solution of large-scale symmetric travelling salesman problems
• Classification of travelling salesman problem formulations
• Facet identification for the symmetric traveling salesman polytope
• Probabilistic exchange algorithms and Euclidean traveling salesman problems
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Results from a parallel branch-and-bound algorithm for the asymmetric traveling salesman problem
• Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation
• A branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
• The vehicle routing problem: An overview of exact and approximate algorithms
• A parallel tabu search algorithm for large traveling salesman problems
• Asymptotic expected performance of some TSP heuristics: An empirical evaluation
• New lower bounds for the symmetric travelling salesman problem
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Integer Programming Formulation of Traveling Salesman Problems
• The N-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
• Using simulated annealing to solve routing and location problems
• An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
• Multi-Terminal Network Flows
• A Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
• On the symmetric travelling salesman problem: A computational study
• Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
• Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
• Local Search for the Asymmetric Traveling Salesman Problem
• A restricted Lagrangean approach to the traveling salesman problem
• Tabu Search—Part I
• Tabu Search—Part II
• Fast Heuristics for Large Geometric Traveling Salesman Problems
• New Insertion and Postoptimization Procedures for the Traveling Salesman Problem
• Some Simple Applications of the Travelling Salesman Problem
• Integer programming approaches to the travelling salesman problem
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Geometric Approaches to Solving the Traveling Salesman Problem
• Finding optimum branchings
• Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems
• Using cutting planes to solve the symmetric Travelling Salesman problem
• Heuristic for the Hamiltonian Path Problem in Euclidian Two Space
• Design of linear quadratic regulators with assigned eigenstructure
• Improvements of the Held—Karp algorithm for the symmetric traveling-salesman problem
• Equation of State Calculations by Fast Computing Machines
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem
• The Traveling-Salesman Problem
• On a Linear-Programming, Combinatorial Approach to the Traveling-Salesman Problem
• Computer Solutions of the Traveling Salesman Problem
• An Algorithm for the Traveling Salesman Problem
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
• The Shortest Hamiltonian Chain of a Graph
• Pathology of Traveling-Salesman Subtour-Elimination Algorithms
• 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
• Technical Note—On Partitioning the Feasible Set in a Branch-and-Bound Algorithm for the Asymmetric Traveling-Salesman Problem