The Traveling Salesman Problem and Its Variations
Combinatorial optimizationPublished 27 January 2006
Gregory Gutin, Abraham P. Punnen
Citations1,374
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
This paper presents Polyhedral Theory and Branch-and-Cut Algorithms for the Symmetric TSP, a model for solving the Asymmetric Traveling Salesman Problem, and some examples of how this model was applied to the Geometric TSP.
Abstract
Preface. Contributing Authors.- 1. The Traveling Salesman Problem: Applications, Formulations and Variations.- 2. Polyhedral Theory and Branch-and-Cut Algorithms for the Symmetric TSP.- 3. Polyhedral Theory for the Asymmetric Traveling Salesman Problem.- 4. Exact Methods for the Asymmetric Traveling Salesman Problem.- 5. Approximation Algorithms for Geometric TSP.- 6. Exponential Neighborhoods and Domination Analysis for the TSP.- 7. Probabilistic Analysis of the TSP.- 8. Local Search and Metaheuristics.- 9. Experimental Analysis of Heuristics for the STSP.- 10. Experimental Analysis of Heuristics for the ATSP.- 11. Polynomially Solvable Cases of the TSP.- 12. The Maximum TSP.- 13. The Generalized Traveling Salesman and Orienteering Problems.- 14. The Prize Collecting Traveling Salesman Problem and Its Applications.- 15. The Bottleneck TSP.- 16. TSP Software.- Appendix A: Sets, Graphs and Permutations. Appendix B: Computational Complexity. References. List of Figures. List of Tables. Index.
Keywords
Computer ScienceEngineering
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.
Digraphs Theory Algorithms And Applications
1,921 Citations2002Jørgen Bang‐Jensen, Gregory Gutin
Digraphs is an essential, comprehensive reference for undergraduate and graduate students, and researchers in mathematics, operations research and computer science, and it will also prove invaluable to specialists in related areas, such as meteorology, physics and computational biology.
Journal of the Society for Industrial and Applied MathematicsA Dynamic Programming Approach to Sequencing Problems
1,253 Citations1962Michael Held, Richard M. Karp
The Traveling Salesman Problem: A Case Study in Local Optimization
601 Citations2008David S. Johnson, Lyle A. McGeoch
This chapter discusses how various approaches to combinatorial optimization have been adapted to the TSP and evaluates their relative success in this perhaps atypical domain from both a theoretical and an experimental point of view.
Some connections between nonuniform and uniform complexity classes
582 Citations1980Richard M. Karp, Richard J. Lipton
This work aims to understand when nonuniform upper bounds can be used to obtain uniform upper bounds, and how to relate it to more common notions.
Cambridge University Press eBooksBipartite Graphs and their Applications
481 Citations1998Armen S. Asratian, Tristan Denley +1 more
Lecture notes in computer scienceThe Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests
127 Citations2001Jill Cirasella, David S. Johnson +2 more
A preliminary report on the first broad-based experimental comparison of modern heuristics for the asymmetric traveling salesmen problem (ATSP), finding that no single algorithm is dominant over all instance classes, although for each class the best tours are found by Zhang's algorithm or an iterated variant on Kanellakis-Papadimitriou.
Decomposition into Cycles I: Hamilton Decompositions
119 Citations1990Brian Alspach, J.-C. Bermond +1 more
INFORMS journal on computingLinear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study
109 Citations2001Egon Balas, Neil Simonetti
An implementation of the dynamic-programming algorithm for the general case when the integerk is replaced with city-specific integersk( j),j = 1, .
European Journal of Operational ResearchConstruction heuristics for the asymmetric TSP
108 Citations2001Fred Glover, Gregory Gutin +2 more
Two new construction heuristics for the asymmetric TSP and a third heuristic based on combining the other two are described, disclosing that the combined heuristic clearly outperforms well-known TSP construction methods and proves significantly more robust in obtaining (relatively) high quality solutions over a wide range of problems.
Journal of Combinatorial Theory Series BA Hamiltonian decomposition of K2m∗, 2m ≥ 8
106 Citations1980Timothy W Tillson
It is shown that K2m∗, 2m ≥ 8, can be decomposed into Hamiltonian circuits.
Journal of the Operational Research SocietyThe travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms
76 Citations1997Fred Glover, Abraham P. Punnen
New procedures for the TSP are developed that require only linear time to execute and yield TSP tours that are better than an exponential number of alternative tours and their underlying results raise new theoretical questions about the analysis of heuristics for hard combinatorial problems.
AlgorithmicaTSP Heuristics: Domination Analysis and Complexity
60 Citations2002Punnen, Margot +1 more
It is shown that the 2-Opt and 3-Opt heuristics for the traveling salesman problem (TSP) on the complete graph Kn produce a solution no worse than the average cost of a tour in Kn in a polynomial number of iterations.
Discrete Applied MathematicsPolynomial approximation algorithms for the TSP and the QAP with a factorial domination number
57 Citations2002Gregory Gutin, Anders Yeo
It is proved that the answer to the question whether there exists a polynomial time algorithm that always produces a tour which is not worse than at least n !
Operations Research LettersTSP tour domination and Hamilton cycle decompositions of regular digraphs
27 Citations2001Gregory Gutin, Anders Yeo
This paper shows that for the asymmetric traveling salesman problem, there is a deterministic polynomial time algorithm that finds a tour that is at least as good as the median of all tour values.
Operations Research LettersAnti-matroids
22 Citations2002Gregory Gutin, Anders Yeo
An anti-matroid is introduced as a family F of subsets of a ground set E for which there exists an assignment of weights to the elements of E such that the greedy algorithm to compute a maximal set in F of minimum weight finds the unique maximal set of maximum weight.
Journal of Information and Optimization SciencesThe traveling salesman problem: new polynomial approximation algorithms and domination analysis
21 Citations2001Abraham P. Punnen
By using an O(n 4) algorithm, a TSP tour which dominates ω((n/2)!n) alternative tours can be identified and an O (n 5) algorithm is suggested which is guaranteed to produce a solution which is better than ω(n/(k+1))!(k!) n/(k+) alternative tours, whenever k is fixed.
Computers & Operations ResearchSmall diameter neighbourhood graphs for the traveling salesman problem: at most four moves from tour to tour
19 Citations1999Gregory Gutin, Anders Yeo
The diameter of the neighbourhood graph of some exponential size neighbourhood structure for the TSP is studied and it is shown that the diameter is surprisingly small: at most four.
Discrete Applied MathematicsUpper bounds on ATSP neighborhood size
6 Citations2003Gregory Gutin, Anders Yeo
It is proved that µ(n) 0 provided NP ⊈ P/poly, which (like P ≠ NP) is believed to be true.
INFOR Information Systems and Operational ResearchEvaluation of The Contract Or-Patch Heuristic Eor The Asymmetric Tsp<sup>1</sup>
6 Citations2005Gregory Gutin, Alexei Zverovitch
An extensive computational study of the original as well as new versions of the algorithm on a variety of ATSP instances, and the influence of the threshold parameter on the quality of tours produced by COP is studied.