The traveling salesman problem: An overview of exact and approximate algorithms
European Journal of Operational ResearchPublished 1 June 1992
Gilbert Laporte
Citations938
SJR quartileQ1
SJR score2.24
SNIP2.62
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
Some of the main known algorithms for the traveling salesman problem are surveyed and the definition and applications of these algorithms are explained.
Abstract
In this paper, some of the main known algorithms for the traveling salesman problem are surveyed. The paper is organized as follows: 1) definition; 2) applications; 3) complexity analysis; 4) exact algorithms; 5) heuristic algorithms; 6) conclusion.
Keywords
Computer ScienceEngineering
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
The Journal of Chemical PhysicsEquation of State Calculations by Fast Computing Machines
37,074 Citations1953N. Metropolis, Arianna W. Rosenbluth +3 more
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
American Mathematical MonthlyCombinatorial Optimization: Algorithms and Complexity.
6,028 Citations1984David Johnson, Christos H. Papadimitriou +1 more
Tabu Search
5,702 Citations1997Fred Glover, Manuel Laguna
INFORMS Journal on ComputingTabu Search—Part II
5,643 Citations1990Fred Glover
The elements of staged search and structured move sets are characterized, which bear on the issue of finiteness, and new dynamic strategies for managing tabu lists are introduced, allowing fuller exploitation of underlying evaluation functions.
INFORMS Journal on ComputingTabu Search—Part I
4,974 Citations1989Fred Glover
The fundamental principles underlying tabu search as a strategy for combinatorial optimization problems are presented and more advanced considerations are examined, applying the basic ideas to special settings and outlining a dynamic move structure to insure finiteness.
Operations ResearchAn Effective Heuristic Algorithm for the Traveling-Salesman Problem
3,797 Citations1973Simon Lin, Brian W. Kernighan
This paper discusses a highly effective heuristic procedure for generating optimum and near-optimum solutions for the symmetric traveling-salesman problem based on a general approach to heuristics that is believed to have wide applicability in combinatorial optimization problems.
Journal of the ACMInteger Programming Formulation of Traveling Salesman Problems
1,994 Citations1960Casey Miller, A. W. Tucker +1 more
The present paper provides yet another example of the versatility of integer programming as a mathematical modeling device by representing a generalization of the well-known “Travelling Salesman Problem” in integer programming terms.
Operations ResearchBranch-and-Bound Methods: A Survey
1,982 Citations1966Eugene L. Lawler, Derek Wood
The essential features of the branch-and-bound approach to constrained optimization are described, and several specific applications are reviewed, including integer linear programming Land-Doig and Balas methods, nonlinear programming minimization of nonconvex objective functions, and the quadratic assignment problem Gilmore and Lawler methods.
Bell System Technical JournalComputer Solutions of the Traveling Salesman Problem
1,960 Citations1965Shen Lin
Two algorithms for solving the (symmetric distance) traveling salesman problem have been programmed for a high-speed digital computer and are based on a general heuristic approach believed to be of general applicability to various optimization problems.
European Journal of Operational ResearchThe vehicle routing problem: An overview of exact and approximate algorithms
1,701 Citations1992Gilbert Laporte
In this paper, some of the main known results relative to the Vehicle Routing Problem are surveyed.
Journal of the Operational Research SocietyThe Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization
1,701 Citations1986
The Traveling Salesman Problem
1,622 Citations2019Lawrence Snyder, Zuo‐Jun Max Shen
Operations ResearchThe Traveling-Salesman Problem and Minimum Spanning Trees
1,443 Citations1970Michael Held, Richard M. Karp
It is shown that maxπwπ = C* precisely when a certain well-known linear program has an optimal solution in integers.
Decision SciencesHEURISTICS FOR INTEGER PROGRAMMING USING SURROGATE CONSTRAINTS
1,352 Citations1977Fred Glover
Bulletin of the American Mathematical SocietyOutline of an algorithm for integer solutions to linear programs
1,352 Citations1958Ralph E. Gomory
Journal of the Operations Research Society of AmericaSolution of a Large-Scale Traveling-Salesman Problem
1,314 Citations1954George B. Dantzig, R. Fulkerson +1 more
Solution of a Large-Scale Traveling-Salesman Problem
1,273 Citations2009Vašek Chvátal, William J. Cook +3 more
The RAND Corporation in the early 1950s contained “what may have been the most remarkable group of mathematicians working on optimization ever assembled”: Arrow, Bellman, Dantzig, Flood, Ford, Fulkerson, Gale, Johnson, Nash, Orchard-Hays, Robinson, Shapley, Simon, Wagner, and other household names.
Operations Research ForumWorst-Case Analysis of a New Heuristic for the Travelling Salesman Problem
1,142 Citations2022Nicos Christofides
An O(n3) heuristic algorithm is described for solving d-city travelling salesman problems (TSP) whose cost matrix satisfies the triangularity condition and a worst-case analysis of this heuristic shows that the ratio of the answer obtained to the optimum TSP solution is strictly less than 3/2.
Operations ResearchAn Algorithm for the Traveling Salesman Problem
1,049 Citations1963John D. C. Little, Katta G. Murty +2 more
A “branch and bound” algorithm is presented for solving the traveling salesman problem, where the set of all tours feasible solutions is broken up into increasingly small subsets by a procedure called branching.
Mathematical ProgrammingThe traveling-salesman problem and minimum spanning trees: Part II
1,017 Citations1971Michael Held, Richard M. Karp
An efficient iterative method for approximating this bound closely from below is presented, and a branch-and-bound procedure based upon these considerations has easily produced proven optimum solutions to all traveling-salesman problems presented to it.
Journal of the Society for Industrial and Applied MathematicsMulti-Terminal Network Flows
940 Citations1961Ralph E. Gomory, T. C. Hu
SIAM Journal on ComputingAn Analysis of Several Heuristics for the Traveling Salesman Problem
806 Citations1977Daniel J. Rosenkrantz, Richard E. Stearns +1 more
Several polynomial time algorithms finding “good,” but not necessarily optimal, tours for the traveling salesman problem are considered, and the closeness of a tour is measured by the ratio of the obtained tour length to the minimal tour length.
An analysis of several heuristics for the traveling salesman problem
784 Citations2009Daniel J. Rosenkrantz, Richard E. Stearns +1 more
Operations ResearchThe Traveling-Salesman Problem
670 Citations1956Merrill M. Flood
The traveling-salesman problem is that of finding a permutation P of the integers from 1 through n that minimizes the quantity A where the aαβ are a given set of real numbers.
Operations ResearchSequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
551 Citations1964Paul C. Gilmore, Ralph E. Gomory
Operations ResearchLetter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
549 Citations1968Katta G. Murty
An efficient algorithm for a ranking of all the assignments so that the maximum computational effort required to generate an additional assignment in the sequence is that of solving at most (n − 1) different assignment problems.
Operations Research LettersOptimization of a 532-city symmetric traveling salesman problem by branch and cut
392 Citations1987Manfred Padberg, Giovanni Rinaldi
Lecture notes in computer scienceLocal optimization and the Traveling Salesman Problem
376 Citations2005David S. Johnson
This paper surveys the state of the art with respect to the TSP, with emphasis on the performance of traditional local optimization algorithms and their new competitors, and on what insights complexity theory does, or does not, provide.
NetworksFinding optimum branchings
371 Citations1977Robert E. Tarjan
An implementation of the algorithm which runs in 0(m logn) time if the problem graph has n vertices and m edges is given, and a modification for dense graphs gives a running time of 0(n2).
Management ScienceSolving Large-Scale Symmetric Travelling Salesman Problems to Optimality
298 Citations1980Harlan Crowder, Manfred Padberg
The present study convincingly establishes the usefulness of mathematically proven good cutting-planes as an invaluable algorithmic tool for difficult combinatorial optimization problems.
Computers & Operations ResearchThe general employee scheduling problem. An integration of MS and AI
295 Citations1986Fred Glover, Claude McMillan
This work describes the relationship between the general employee scheduling problem and related problems, and reports computational results for a procedure that solves these more complex problems within 98–99% optimality and runs on a microcomputer.
Journal of the Operational Research SocietyRecent Advances in Mathematical Programming
292 Citations1964S. Vajda
Mathematical ProgrammingSolution of large-scale symmetric travelling salesman problems
273 Citations1991Martin Grötschel, Olaf Holland
The implementation is based on a fast LP-solver (IBM's MPSX) and makes effective use of polyhedral results on the symmetric travelling salesman polytope and describes the important ingredients of the code.
Journal of the Operational Research SocietySome Simple Applications of the Travelling Salesman Problem
268 Citations1975Jan Karel Lenstra, A. H. G. Rinnooy Kan
This paper reports on typical applications in computer wiring, vehicle routing, clustering and job-shop scheduling that originated from real world problems and thus seem to be of particular interest.
SIAM ReviewThe <i>N</i>-City Travelling Salesman Problem: Statistical Mechanics and the Metropolis Algorithm
251 Citations1984Ernesto Bonomi, Jean‐Luc Lutton
The Metropolis algorithm is used to generate a sequence of tours that may be viewed as the random evolution of a physical system in contact with a heat-bath, and it appears that for large N one arrives within a few percent of the optimal solution in better than quadratic time.
Naval Research Logistics QuarterlyUsing simulated annealing to solve routing and location problems
206 Citations1986Bruce Golden, Christopher C. Skiścim
This paper implements the analogy between the statistical mechanics of large multivariate physical systems and combinatorial optimization, applies it to the traveling salesman problem and the p‐median location problem, and test the approach extensively.
ScienceExact Solution of Large Asymmetric Traveling Salesman Problems
173 Citations1991Donald L. Miller, Joseph F. Pekny
The results show that the algorithm performs remarkably well for some classes of problems, determining an optimal solution even for problems with large numbers of cities, yet for other classes, even small problems thwart determination of a provably optimal solution.
Operations ResearchOn a Linear-Programming, Combinatorial Approach to the Traveling-Salesman Problem
172 Citations1959George B. Dantzig, D. R. Fulkerson +1 more
SIAM Journal on ComputingA Patching Algorithm for the Nonsymmetric Traveling-Salesman Problem
172 Citations1979Richard M. Karp
The algorithm first solves the assignment problem for the matrix D, and then patches the cycles of the optimum assignment together to form a tour, which tends to give nearly optimal solutions when the number of cities is extremely large.
Management ScienceSome New Branching and Bounding Criteria for the Asymmetric Travelling Salesman Problem
165 Citations1980G. Carpaneto, Paolo Toth
This paper presents a breadth-first branch and bound algorithm which differs from the method of Smith, Srinivasan and Thompson in the selection of the subtour to be split, in the ordering of the arcs in the selected subtour, and in the computation of different partial lower bounds and in different data structures to facilitate the updating of the cost matrix.
Annals of Operations ResearchAlgorithms and codes for the assignment problem
161 Citations1988G. Carpaneto, Silvano Martello +1 more
This paper analyzes the most efficient algorithms for the Linear Min-Sum Assignment Problem and shows that they derive from a common basic procedure, and evaluates the computational complexity and the average performance on randomly-generated test problems.
Mathematical programming studiesOn the symmetric travelling salesman problem: A computational study
153 Citations1980Manfred Padberg, Saman Hong
The empirical results lend convincing support to the hypothesis that inequalities defining facets of the convex hull of tours are of substantial computational value in the solution of this difficult combinatorial problem.
Mathematical ProgrammingA restricted Lagrangean approach to the traveling salesman problem
147 Citations1981Egon Balas, Nicos Christofides
An algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on the assignment problem (AP) that can be adapted to the symmetric TSP by using the 2-matching problem instead of AP is described.
Design Automation ConferenceSimulated Annealing and Combinatorial Optimization
138 Citations1986Surendra Nahar, Sartaj Sahni +1 more
Mathematical ProgrammingFacet identification for the symmetric traveling salesman polytope
130 Citations1990Manfred Padberg, Giovanni Rinaldi
Exact and heuristic shrinking conditions for the input graph are given that yield efficient procedures for the identification of simple and general comb inequalities and of some elementary clique tree inequalities.
Practica Oto-Rhino-LaryngologicaDer Saccus endolymphaticus bei Entzündungsprozessen
129 Citations2009J.P. Secrétan
Operations ResearchPathology of Traveling-Salesman Subtour-Elimination Algorithms
128 Citations1971Mandell Bellmore, John C. Malone
An underlying theory for the traveling-salesman problem is developed, pathological performance of some existing techniques are predicted, and two algorithms are presented, based upon the theory, with predictable polynomial growth in expected computation time and resistence to pathological problems.
European Journal of Operational ResearchA branch and bound algorithm for the symmetric traveling salesman problem based on the 1-tree relaxation
122 Citations1982Ton Volgenant, Roy Jonker
The Lagrangean approach to the symmetric traveling salesman problem is used in a new branch and bound algorithm that differs from other algorithms not only in the branching scheme, but also in the ascent method to calculate the 1-tree bounds.
Operations Research LettersLarge travelling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation
120 Citations1989Robert G. Bland, David Shallcross
The Lin-Kernighan heuristic consistently produces near-optimal sequences, and simple TSP heuristics give substantial improvements in utilization at small computational expense.
Operations ResearchAn Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
115 Citations1986Bezalel Gavish, Kizhanathan Srikanth
An efficient branch-and-bound based method for solving the Multiple Traveling Salesman Problem is developed, and lower bounds through a Lagrangean relaxation that requires computing a degree-constrained minimal spanning tree are developed.
Operations ResearchLocal Search for the Asymmetric Traveling Salesman Problem
108 Citations1980Paris-C. Kanellakis, Christos H. Papadimitriou
An extension of the Lin-Kernighan local search algorithm for the solution of the asymmetric traveling salesman problem is presented and computational results suggest that the heuristic is feasible for fairly large instances.
Mathematical ProgrammingUsing cutting planes to solve the symmetric Travelling Salesman problem
103 Citations1978P. Miliotis
Two algorithms using cutting planes for solving the Travelling Salesman Problem differ in the order in which the omitted constraints and the cutting planes that are required are generated.
Operations Research LettersClassification of travelling salesman problem formulations
94 Citations1990André Langevin, François Soumis +1 more
The purpose of this paper is to clarify the relations between these formulations and with other classical formulations for the traveling salesman problem.
Operations Research LettersOptimization of a 532-city symmetric traveling salesman problem by branch and cut
89 Citations1990Manfred Padberg, Giovanni Rinaldi
Mathematical ProgrammingInteger programming approaches to the travelling salesman problem
86 Citations1976P. Miliotis
The generality of the method and the modest solution times achieved leads the author to believe that such an LP approach to other combinatorial problems deserves further consideration.
Journal of the Operational Research SocietyAlgorithms for Large-scale Travelling Salesman Problems
86 Citations1972Nicos Christofides, Samuel Eilon
This algorithm is faster than the original r-optimal method, and computation times increase much less rapidly with problem size, so it is possible to solve large-scale travelling salesman problems and examples are given.
Mathematical ProgrammingAn additive bounding procedure for the asymmetric travelling salesman problem
83 Citations1992Matteo Fischetti, Paolo Toth
New lower bounds for the asymmetric travelling salesman problem are presented, based on spanning arborescences, in an additive procedure whose theoretical performance is compared with that of the Balas and Christofides procedure (1981).
Mathematical ProgrammingImprovements of the Held—Karp algorithm for the symmetric traveling-salesman problem
78 Citations1974Keld Helbig Hansen, Jakob Krarup
A highly efficient algorithm (HK) devised by Held and Karp for solving the symmetric traveling-salesman problem was presented at the 7th Mathematical programming Symposium in 1970 and published in Mathematical Programming in 1971.
23rd ACM/IEEE Design Automation ConferenceSimulated Annealing and Combinatorial Optimization
66 Citations1986Surendra Nahar, Sartaj Sahni +1 more
Operations ResearchMinimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems
61 Citations1977Robert Garfinkel
It is shown that the problem of wallpapering a room so as to minimize the paper wasted is equivalent to finding a shortest hamiltonian chain in a highly structured graph and the "nearest-neighbor" technique yields an optimal solution.
INFORMS Journal on ComputingFast Heuristics for Large Geometric Traveling Salesman Problems
60 Citations1992Gerhard Reinelt
Euclidean traveling salesman problems in the plane are considered and it is shown how their geometric structure can be exploited to derive fast heuristics.
Operations Research LettersResults from a parallel branch and bound algorithm for the asymmetric traveling salesman problem
51 Citations1989Donald L. Miller, Joseph F. Pekny
The algorithm uses an assignment problem based lower bounding technique, subtour elimination branching rules, and a subtour patching algorithm as an upper bounding procedure to optimally solve the asymmetric traveling salesman problem.
Management ScienceGeometric Approaches to Solving the Traveling Salesman Problem
50 Citations1977John P. Norback, Robert F. Love
Two geometric approaches to solving sequencing problems are described and tested, and the largest angle method can be used to generate tours without any computation, giving the practitioner an effective "back of the envelope method" of finding solutions.
Annals of discrete mathematicsA Lifo Implicit Enumeration Search Algorithm for the Symmetric Traveling Salesman Problem Using Held and Karp's 1-Tree Relaxation
50 Citations1977T. H. C. Smith, Gerald L. Thompson
The proposed LIFO implicit enumeration search algorithm for the symmetric traveling salesman problem which uses the 1-tree relaxation of Held and Karp is proposed and on the basis of the sample it can be stated that the proposed algorithm is faster and generates many fewer subproblems than Held andKarp's algorithm.
Annals of discrete mathematicsComputational Performance of Three Subtour Elimination Algorithms for Solving Asymmetric Traveling Salesman Problems
47 Citations1977T. H. C. Smith, V. Srinivasan +1 more
Three implicit enumeration algorithms for solving the asymmetric traveling salesman problem with subtour elimination using the assignment problem relaxation similar to the previous approaches by Eastman, Shapiro and Bellmore and Malone are developed and computationally test.
SIAM Journal on Applied MathematicsThe Shortest Hamiltonian Chain of a Graph
43 Citations1970Nicos Christofides
Two basic algorithms are given each of which can solve both of the above problems with only slight modification, and whereas the convergence of Algorithm A is self-evident, no proof of convergence has been obtained for Algorithm B.
OR SpectrumProbabilistic exchange algorithms and Euclidean traveling salesman problems
43 Citations1986Yves Rossier, M. Troyon +1 more
Journal of the Operational Research SocietyA Combinatorial Optimization Problem Arising in Dartboard Design
41 Citations1991H. A. Eiselt, Gilbert Laporte
The problem of optimally locating the numbers around a dartboard is investigated and the objective considered is risk maximization.
Operations ResearchTechnical Note—On Partitioning the Feasible Set in a Branch-and-Bound Algorithm for the Asymmetric Traveling-Salesman Problem
30 Citations1973Robert Garfinkel
This note develops a branching scheme for a branch-and-bound algorithm for the traveling-salesman problem that improves on the algorithm of Bellmore and Malone in that a partition of the feasible set is achieved at every vertex of the enumeration tree.
European Journal of Operational ResearchAsymptotic expected performance of some TSP heuristics: An empirical evaluation
27 Citations1989H.L. Ong, H. C. Huang
This study indicates that the expected tour lengths through n points in a unit square produced by these heuristics are all proportional to SQRT(n) asymptotically.
The application of tabu search to the symmetric traveling salesman problem
27 Citations1989John Edward Knox, Fred Glover
The values of desirable parameter settings are presented along with the methods used to identify them and a comparison based on solution quality and computational efficiency is made between tabu search and other general heuristic search strategies, such as simulated annealing and genetic algorithms.
Mathematical ProgrammingNew lower bounds for the Symmetric Travelling Salesman Problem
22 Citations1989G. Carpaneto, Matteo Fischetti +1 more
New lower bounds for the Symmetric Travelling Salesman Problem are proposed and combined in additive bounding procedures and fast procedures for computing the linear programming reduced costs of the Shortest Spanning Tree (SST) Problem and for finding all ther-SST of a given graph.
Journal of the Operational Research SocietyHeuristic for the Hamiltonian Path Problem in Euclidian Two Space
11 Citations1979John P. Norback, Robert F. Love
…