The DOI matches its Crossref record.
The Traveling Salesman Problem
Abstract
This chapter covers one important aspect of the transportation-related decisions a firm must make, namely, routing vehicles among the locations they must visit. It discusses the famous traveling salesman problem (TSP). The TSP is perhaps the best-known combinatorial optimization problem and has been intensely studied by researchers in supply chain management, operations research, computer science, and other fields. The chapter also discusses exact algorithms for the TSP, and construction heuristics for the TSP. The chapter considers improvement heuristics for the TSP that begin with a complete tour and perform operations on it to try to make it shorter. The first branching algorithm for the TSP was the branch-and-bound algorithm proposed by Little et al.; in fact, their paper was the first to introduce the term branch-and-bound. The heuristic finds an Eulerian tour and converts it to a TSP tour by shortcutting, exactly as in the minimum spanning tree heuristic.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Ant colony system: a cooperative learning approach to the traveling salesman problem
Dorigo, M., & Gambardella, L. M. (1997) · IEEE Transactions on Evolutionary Computation · doi:10.1109/4235.585892 · Cited by 8,081
“Neural” computation of decisions in optimization problems
Hopfield, J. J., & Tank, D. W. (1985) · Biological Cybernetics · doi:10.1007/bf00339943 · Cited by 6,031
Glover, F. (1990) · ORSA Journal on Computing · doi:10.1287/ijoc.2.1.4 · Cited by 5,647
Future paths for integer programming and links to artificial intelligence
Glover, F. (1986) · Computers & Operations Research · doi:10.1016/0305-0548(86)90048-1 · Cited by 4,181
Hoos (2000) · doi:10.1016/s0167-739x(00)00043-1 · Cited by 2,737
Greedy Randomized Adaptive Search Procedures
Resende, M. G. C., & Ribeiro, C. C. (2006) · International Series in Operations Research & Management Science · doi:10.1007/0-306-48056-5_8 · Cited by 2,310
The vehicle routing problem: An overview of exact and approximate algorithms
Laporte, G. (1992) · European Journal of Operational Research · doi:10.1016/0377-2217(92)90192-c · Cited by 1,749
A survey on optimization metaheuristics
Boussaïd, I., Lepagnot, J., & Siarry, P. (2013) · Information Sciences · doi:10.1016/j.ins.2013.02.041 · Cited by 1,655
The multiple traveling salesman problem: an overview of formulations and solution procedures
Bektas, T. (2006) · Omega · doi:10.1016/j.omega.2004.10.004 · Cited by 1,153
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Arora, S. (1998) · Journal of the ACM · doi:10.1145/290179.290180 · Cited by 1,137
A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
Padberg, M., & Rinaldi, G. (1991) · SIAM Review · doi:10.1137/1033004 · Cited by 1,097
A graduated assignment algorithm for graph matching
Gold, S., & Rangarajan, A. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.491619 · Cited by 1,090
The traveling salesman problem: An overview of exact and approximate algorithms
Laporte, G. (1992) · European Journal of Operational Research · doi:10.1016/0377-2217(92)90138-y · Cited by 971
Vehicle Routing Problem with Time Windows, Part II: Metaheuristics
Bräysy, O., & Gendreau, M. (2005) · Transportation Science · doi:10.1287/trsc.1030.0057 · Cited by 844
A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process
Hall, N. G., & Sriskandarajah, C. (1996) · Operations Research · doi:10.1287/opre.44.3.510 · Cited by 842
MAX-MIN Ant System and local search for the traveling salesman problem
Stutzle, T., & Hoos, H. (2002) · Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97) · doi:10.1109/icec.1997.592327 · Cited by 831
An analogue approach to the travelling salesman problem using an elastic net method
Durbin, R., & Willshaw, D. (1987) · Nature · doi:10.1038/326689a0 · Cited by 797
A Branch-and-Cut Algorithm for the Dial-a-Ride Problem
Cordeau, J.-F. (2006) · Operations Research · doi:10.1287/opre.1060.0283 · Cited by 695
Metaheuristics: A bibliography
Osman, I. H., & Laporte, G. (1996) · Annals of Operations Research · doi:10.1007/bf02125421 · Cited by 672
A survey of very large-scale neighborhood search techniques
Ahuja, R. K., Ergun, Ö., Orlin, J. B., & Punnen, A. P. (2002) · Discrete Applied Mathematics · doi:10.1016/s0166-218x(01)00338-9 · Cited by 643
New Search Spaces for Sequencing Problems with Application to Job Shop Scheduling
Storer, R. H., Wu, S. D., & Vaccari, R. (1992) · Management Science · doi:10.1287/mnsc.38.10.1495 · Cited by 546
A new approach to the minimum cut problem
Karger, D. R., & Stein, C. (1996) · Journal of the ACM · doi:10.1145/234533.234534 · Cited by 485
Rationality for mortals: how people cope with uncertainty
(2009) · Choice Reviews Online · doi:10.5860/choice.46-4133 · Cited by 469
A novel genetic algorithm based on immunity
Jiao, L., & Wang, L. (2000) · IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans · doi:10.1109/3468.867862 · Cited by 454
Polynomial time approximation schemes for Euclidean TSP and other geometric problems
Arora, S. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548458 · Cited by 449
The Hyper-Cube Framework for Ant Colony Optimization
Blum, C., & Dorigo, M. (2004) · IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics) · doi:10.1109/tsmcb.2003.821450 · Cited by 432
The Traveling Salesman Problem with Distances One and Two
Papadimitriou, C. H., & Yannakakis, M. (1993) · Mathematics of Operations Research · doi:10.1287/moor.18.1.1 · Cited by 412
A new algorithm to calculate the nestedness temperature of presence–absence matrices
Rodríguez‐Gironés, M. A., & Santamaría, L. (2006) · Journal of Biogeography · doi:10.1111/j.1365-2699.2006.01444.x · Cited by 404
D-Ants: Savings Based Ants divide and conquer the vehicle routing problem
Reimann, M., Doerner, K., & Hartl, R. F. (2004) · Computers & Operations Research · doi:10.1016/s0305-0548(03)00014-5 · Cited by 387
Burkard, R. E. (1984) · European Journal of Operational Research · doi:10.1016/0377-2217(84)90093-6 · Cited by 378
Simple heuristics and rules of thumb: Where psychologists and behavioural biologists might meet
Hutchinson, J. M. C., & Gigerenzer, G. (2005) · Behavioural Processes · doi:10.1016/j.beproc.2005.02.019 · Cited by 377
An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem
Gambardella, L. M., & Dorigo, M. (2000) · INFORMS Journal on Computing · doi:10.1287/ijoc.12.3.237.12636 · Cited by 373
A Survey of Automatic Parameter Tuning Methods for Metaheuristics
Huang, C., Li, Y., & Yao, X. (2020) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2019.2921598 · Cited by 371
Local search in combinatorial optimization
Crama, Y., Kolen, A. W. J., & Pesch, E. J. (1995) · Lecture Notes in Computer Science · doi:10.1007/bfb0027029 · Cited by 361
On network correlated data gathering
Cristescu, R., Beferull-Lozano, B., & Vetterli, M. (2005) · IEEE INFOCOM 2004 · doi:10.1109/infcom.2004.1354677 · Cited by 334
An improved discrete bat algorithm for symmetric and asymmetric Traveling Salesman Problems
Osaba, E., Yang, X.-S., Diaz, F., Lopez-Garcia, P., & Carballedo, R. (2016) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2015.10.006 · Cited by 312
Traveling Salesman Problem: an Overview of Applications, Formulations, and Solution Approaches
Matai, R., Singh, S., & Lal, M. (2010) · Traveling Salesman Problem, Theory and Applications · doi:10.5772/12909 · Cited by 299
Lu, C., Gao, L., Li, X., Pan, Q., & Wang, Q. (2017) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2017.01.011 · Cited by 292
An Integer L-Shaped Algorithm for the Capacitated Vehicle Routing Problem with Stochastic Demands
Laporte, G., Louveaux, F. V., & van Hamme, L. (2002) · Operations Research · doi:10.1287/opre.50.3.415.7751 · Cited by 289
Vehicle Routing with Stochastic Demands: Properties and Solution Frameworks
Dror, M., Laporte, G., & Trudeau, P. (1989) · Transportation Science · doi:10.1287/trsc.23.3.166 · Cited by 286
Kammerdiner, A., Gevezes, T., Pasiliao, E., Pitsoulis, L., & Pardalos, P. M. (2013) · Encyclopedia of Operations Research and Management Science · doi:10.1007/978-1-4419-1153-7_1152 · Cited by 273
Pierce, N. A., & Winfree, E. (2002) · Protein Engineering, Design and Selection · doi:10.1093/protein/15.10.779 · Cited by 267
Rectifiable sets and the Traveling Salesman Problem
Jones, P. W. (1990) · Inventiones Mathematicae · doi:10.1007/bf01233418 · Cited by 259
Landscapes and their correlation functions
Stadler, P. F. (1996) · Journal of Mathematical Chemistry · doi:10.1007/bf01165154 · Cited by 258
Slaney, J., & Thiébaux, S. (2001) · Artificial Intelligence · doi:10.1016/s0004-3702(00)00079-5 · Cited by 226
Gupta, P. K., Shree, V., Hiremath, L., & Rajendran, S. (2019) · Studies in Computational Intelligence · doi:10.1007/978-3-030-12500-4_11 · Cited by 129
AFSCN scheduling: How the problem and solution have evolved
Barbulescu, L., Howe, A., & Whitley, D. (2006) · Mathematical and Computer Modelling · doi:10.1016/j.mcm.2005.12.004 · Cited by 69
Metadata
- Venue
- Fundamentals of Supply Chain Theory
- Publisher
- Wiley
- Published
- 2019-06-28
- Pages
- 403-461
- OpenAlex
- W307896644
- Cited by
- 1,614
- References
- 0
- Type
- other
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.