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

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

Gilbert Laporte

Publication date: 11 October 1992

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

Full work available at URL: https://doi.org/10.1016/0377-2217(92)90138-y

zbMATH Keywords

surveytraveling salesmanheuristic algorithmscomplexity analysisexact algorithms

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items

Generation of the exact Pareto set in multi-objective traveling salesman and set covering problems, Multiple phase neighborhood search---GRASP based on Lagrangean relaxation, random backtracking Lin-Kernighan and path relinking for the TSP, A new heuristic for the period traveling salesman problem, A two-phase algorithm for the cyclic inventory routing problem, Integration of equipment planning and project scheduling, An integration of Lagrangian split and VNS: the case of the capacitated vehicle routing problem, A (0-1) goal programming model for scheduling the tour of a marketing executive, Approximation Algorithms for Generalized MST and TSP in Grid Clusters, Routing problems: A bibliography, Workload planning in small lot printed circuit board assembly, Reducing the size of combinatorial optimization problems using the operator vaccine by fuzzy selector with adaptive heuristics, Solving large-scale TSP using a fast wedging insertion partitioning approach, Divide and conquer strategies for parallel TSP heuristics, Genetic algorithms for the traveling salesman problem, Incremental SAT-Based Method with Native Boolean Cardinality Handling for the Hamiltonian Cycle Problem, A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings, A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem, Deterministic optimizational problems of transportation logistics, A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem, A cutoff time strategy based on the coupon collector's problem, Strategies for Generating Well Centered Tetrahedral Meshes on Industrial Geometries, The profit-oriented hub line location problem with elastic demand, Multiple \(k\)-opt evaluation multiple \(k\)-opt moves with GPU high performance local search to large-scale traveling salesman problems, Trucks and drones cooperation in the last‐mile delivery process, The intermittent travelling salesman problem, Heuristic algorithms for the 2-period balanced travelling salesman problem in Euclidean graphs, Community logistics and dynamic community partitioning: a new approach for solving e-commerce last mile delivery, Tool switching problems in the context of overlay printing with multiple colours, The road train optimization problem with load assignment, Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing, Introduction to routing problems with mandatory transitions, Research on improved ant colony optimization for traveling salesman problem, Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times, Optimization of blood sample collection with timing and quality constraints, Synchronized routing of seasonal products through a production/distribution network, The Vehicle Routing Problem with Floating Targets: Formulation and Solution Approaches, Evolutionary algorithms for solving multi-objective travelling salesman problem, Application of imperialist competitive algorithm on solving the traveling salesman problem, Real-time split-delivery pickup and delivery time window problems with transfers, Combinação de abordagens GLSP e ATSP para o problema de dimensionamento e sequenciamento de lotes de produção de suplementos para nutrição animal, An interactive approach for biobjective integer programs under quasiconvex preference functions, On the vehicle routing problem, Bee-inspired algorithms applied to vehicle routing problems: a survey and a proposal, The vehicle routing problem: An overview of exact and approximate algorithms, Inventory rebalancing and vehicle routing in bike sharing systems, Ordered weighted average optimization in multiobjective spanning tree problem, Clustering data that are graph connected, Curvature-constrained traveling salesman tours for aerial surveillance in scenarios with obstacles, Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming, Solving the traveling repairman problem with profits: a novel variable neighborhood search approach, Gossip algorithms for heterogeneous multi-vehicle routing problems, Physarum-energy optimization algorithm, Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching, An exact method for scheduling a yard crane, Capacitated lot-sizing and scheduling with sequence-dependent, period-overlapping and non-triangular setups, Expanding neighborhood GRASP for the traveling salesman problem, The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times, Mixed integer formulations for a routing problem with information collection in wireless networks, A cutting plane method for risk-constrained traveling salesman problem with random arc costs, Home service routing and appointment scheduling with stochastic service times, Algorithms for Euclidean Degree Bounded Spanning Tree Problems, Hamiltonian properties of polyhedra with few 3-cuts. A survey, The Rural Postman Problem on mixed graphs with turn penalties, A review on cost allocation methods in collaborative transportation, 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, Genetic algorithms and traveling salesman problems, An asymptotically tight online algorithm for \(m\)-steiner traveling salesman problem, A branch-and-price procedure for clustering data that are graph connected, A new subtour elimination constraint for the vehicle routing problem, Planning models for freight transportation, Straddle carrier routing at seaport container terminals in the presence of short term quay crane buffer areas, An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs, 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, Performance characteristics of alternative genetic algorithmic approaches to the traveling salesman problem using path representation: An empirical study, Circular Jaccard distance based multi-solution optimization for traveling salesman problems, The influence of problem specific neighborhood structures in metaheuristics performance, A sweep-based algorithm for the fleet size and mix vehicle routing problem, IntraClusTSP -- an incremental intra-cluster refinement heuristic algorithm for symmetric travelling salesman problem, Current modeling practices in bank courier scheduling, A Memetic Random Key Algorithm for the Balanced Travelling Salesman Problem, A Variable Neighborhood Search Algorithm for Cost-Balanced Travelling 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, Towards fully automated inspection of large components with UAVs: offline path planning and view angle dependent optimization strategies, Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation, Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems

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