The DOI matches its Crossref record; 49 of the 49 references it cites were found in a registry or an index.
Fifty Years of Vehicle Routing
Abstract
The Vehicle Routing Problem (VRP) was introduced 50 years ago by Dantzig and Ramser under the title “The Truck Dispatching Problem.” The study of the VRP has given rise to major developments in the fields of exact algorithms and heuristics. In particular, highly sophisticated exact mathematical programming decomposition algorithms and powerful metaheuristics for the VRP have been put forward in recent years. The purpose of this article is to provide a brief account of this development.
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
Cites
Holland, J. H. (1992) · The MIT Press eBooks · doi:10.7551/mitpress/1090.001.0001 · Cited by 47,002
Optimization by Simulated Annealing
Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983) · Science · doi:10.1126/science.220.4598.671 · Cited by 45,134
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Dantzig, G. B., & Ramser, J. H. (1959) · Management Science · doi:10.1287/mnsc.6.1.80 · Cited by 4,985
Mladenović, N., & Hansen, P. (1997) · Computers & Operations Research · doi:10.1016/s0305-0548(97)00031-2 · Cited by 4,254
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
(2002) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718515 · Cited by 4,008
Scheduling of Vehicles from a Central Depot to a Number of Delivery Points
Clarke, G., & Wright, J. W. (1964) · Operations Research · doi:10.1287/opre.12.4.568 · Cited by 3,894
The Traveling salesman problem: a computational study
(2007) · Choice Reviews Online · doi:10.5860/choice.45-0928 · Cited by 1,726
The Vehicle Routing Problem: Latest Advances and New Challenges
(2008) · Operations Research/Computer Science Interfaces · doi:10.1007/978-0-387-77778-8 · Cited by 1,483
Solution of a Large-Scale Traveling-Salesman Problem
Dantzig, G. B., Fulkerson, R., & Johnson, S. M. (1954) · Journal of the Operations Research Society of America · doi:10.1287/opre.2.4.393 · Cited by 1,483
A general heuristic for vehicle routing problems
Pisinger, D., & Ropke, S. (2007) · Computers & Operations Research · doi:10.1016/j.cor.2005.09.012 · Cited by 1,443
Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems
Shaw, P. (1998) · Lecture Notes in Computer Science · doi:10.1007/3-540-49481-2_30 · Cited by 1,366
A Tabu Search Heuristic for the Vehicle Routing Problem
Michel Gendreau, A., Hertz, A., & Gilbert Laporte, A. (1994) · Management Science · doi:10.1287/mnsc.40.10.1276 · Cited by 1,303
Solution of a Large-Scale Traveling-Salesman Problem
Chvátal, V., Cook, W. J., Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (2009) · Springer eBooks · doi:10.1007/978-3-540-68279-0_1 · Cited by 1,263
Dueck, G., & Scheuer, T. (1990) · Journal of Computational Physics · doi:10.1016/0021-9991(90)90201-b · Cited by 1,232
A Heuristic Algorithm for the Vehicle-Dispatch Problem
Gillett, B. E., & Miller, L. R. (1974) · Operations Research · doi:10.1287/opre.22.2.340 · Cited by 1,179
A generalized assignment heuristic for vehicle routing
Fisher, M. L., & Jaikumar, R. (1981) · Networks · doi:10.1002/net.3230110205 · Cited by 1,076
A simple and effective evolutionary algorithm for the vehicle routing problem
Prins, C. (2004) · Computers & Operations Research · doi:10.1016/s0305-0548(03)00158-8 · Cited by 1,058
An Algorithm for the Traveling Salesman Problem
Little, J. D. C., Murty, K. G., Sweeney, D. W., & Karel, C. (1963) · Operations Research · doi:10.1287/opre.11.6.972 · Cited by 1,058
Probabilistic diversification and intensification in local search for vehicle routing
Rochat, Y., & Taillard, É. D. (1995) · Journal of Heuristics · doi:10.1007/bf02430370 · Cited by 914
A unified tabu search heuristic for vehicle routing problems with time windows
Cordeau, J.-F., Laporte, G., & Mercier, A. (2001) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2601163 · Cited by 897
Self-citationA tabu search heuristic for periodic and multi-depot vehicle routing problems
Cordeau, J.-F., Gendreau, M., & Laporte, G. (1997) · Networks · doi:10.1002/(sici)1097-0037(199709)30:2<105::aid-net5>3.0.co;2-g · Cited by 864
Self-citationLocal Search in Combinatorial Optimization
(2018) · Princeton University Press eBooks · doi:10.2307/j.ctv346t9c · Cited by 808
Dueck, G. (1993) · Journal of Computational Physics · doi:10.1006/jcph.1993.1010 · Cited by 765
Shekhar, S., Xiong, H. Y., & Zhou, X. S. (2017) · Encyclopedia of GIS · doi:10.1007/978-3-319-17885-1_101452 · Cited by 568
The Granular Tabu Search and Its Application to the Vehicle-Routing Problem
Toth, P., & Vigo, D. (2003) · INFORMS journal on computing · doi:10.1287/ijoc.15.4.333.24890 · Cited by 558
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem
Fukasawa, R., Longo, H., Lysgaard, J., Aragão, M. P. D., Reis, M., Uchoa, E., & Werneck, R. F. (2006) · Mathematical Programming · doi:10.1007/s10107-005-0644-x · Cited by 539
Solving Airline Crew Scheduling Problems by Branch-and-Cut
Hoffman, K. L., & Padberg, M. (1993) · Management Science · doi:10.1287/mnsc.39.6.657 · Cited by 537
Christofides, N., Mingozzi, A., & Toth, P. (1981) · Mathematical Programming · doi:10.1007/bf01589353 · Cited by 535
A Gentle Introduction to Memetic Algorithms
Moscato, P., & Cotta, C. (2006) · International Series in Operations Research & Management Science · doi:10.1007/0-306-48056-5_5 · Cited by 457
Balas, E., & Padberg, M. W. (1976) · SIAM Review · doi:10.1137/1018115 · Cited by 449
Exact Algorithms for the Vehicle Routing Problem
Gilbert Laporte, A., & Nobert, Y. (1987) · North-Holland mathematics studies · doi:10.1016/s0304-0208(08)73235-3 · Cited by 429
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
On an Integer Program for a Delivery Problem
Balinski, M., & Quandt, R. E. (1964) · Operations Research · doi:10.1287/opre.12.2.300 · Cited by 373
Baldacci, R., Christofides, N., & Mingozzi, A. (2008) · Mathematical Programming · doi:10.1007/s10107-007-0178-5 · Cited by 364
Golden, B., Wasil, E., Kelly, J. P., & Chao, I. (1998) · Springer eBooks · doi:10.1007/978-1-4615-5755-5_2 · Cited by 345
State‐space relaxation procedures for the computation of bounds to routing problems
Christofides, N., Mingozzi, A., & Toth, P. (1981) · Networks · doi:10.1002/net.3230110207 · Cited by 330
What you should know about the vehicle routing problem
Gilbert Laporte, A. (2007) · Naval Research Logistics (NRL) · doi:10.1002/nav.20261 · Cited by 329
Optimal Routing under Capacity and Distance Restrictions
Laporte, G., Nobert, Y., & Desrochers, M. (1985) · Operations Research · doi:10.1287/opre.33.5.1050 · Cited by 307
Self-citationBaldacci, R., Hadjiconstantinou, E., & Mingozzi, A. (2004) · Operations Research · doi:10.1287/opre.1040.0111 · Cited by 289
An Integer Programming Approach to the Vehicle Scheduling Problem
Foster, B. A., & Ryan, D. M. (1976) · Journal of the Operational Research Society · doi:10.1057/jors.1976.63 · Cited by 231
3. Branch-And-Cut Algorithms for the Capacitated VRP
Naddef, D., & Rinaldi, G. (2002) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718515.ch3 · Cited by 201
A GRASP × Evolutionary Local Search Hybrid for the Vehicle Routing Problem
Prins, C. (2008) · Studies in computational intelligence · doi:10.1007/978-3-540-85152-3_2 · Cited by 173
Solving the vehicle routing problem with adaptive memory programming methodology
Tarantilis, C. D. (2004) · Computers & Operations Research · doi:10.1016/j.cor.2004.03.005 · Cited by 142
The Traveling Salesman Problem
Cook, W. J., Cunningham, W. H., Pulleyblank, W. R., & Schrijver, A. (1997) · Combinatorial optimization · doi:10.1002/9781118033142.ch7 · Cited by 141
Watt, R., Maslana, E. S., Navabi, M. J., & Mylrea, K. C. (1992) · Anesthesiology · doi:10.1097/00000542-199209001-00506 · Cited by 91
Creating very large scale neighborhoods out of smaller ones by compounding moves
Ergün, Ö., Orlin, J. B., & Steele-Feldman, A. (2006) · Journal of Heuristics · doi:10.1007/s10732-006-5561-5 · Cited by 78
Extensions to the generalised assignment heuristic for vehicle routing
Baker, B. M., & Sheasby, J. (1999) · European Journal of Operational Research · doi:10.1016/s0377-2217(98)00348-8 · Cited by 43
Cited by
The vehicle routing problem: State of the art classification and review
Braekers, K., Ramaekers, K., & Van Nieuwenhuyse, I. (2016) · Computers & Industrial Engineering · doi:10.1016/j.cie.2015.12.007 · Cited by 1,265
A review of dynamic vehicle routing problems
Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013) · European Journal of Operational Research · doi:10.1016/j.ejor.2012.08.015 · Cited by 1,253
A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems
Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., & Rei, W. (2012) · Operations Research · doi:10.1287/opre.1120.1048 · Cited by 709
Multimodal freight transportation planning: A literature review
SteadieSeifi, M., Dellaert, N. P., Nuijten, W., Van Woensel, T., & Raoufi, R. (2014) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.06.055 · Cited by 677
A survey on dynamic and stochastic vehicle routing problems
Ritzinger, U., Puchinger, J., & Hartl, R. F. (2016) · International Journal of Production Research · doi:10.1080/00207543.2015.1043403 · Cited by 443
Metadata
- Authors
- Laporte, G.
- Venue
- Transportation Science
- Published
- 2009-11
- Volume
- 43
- Issue
- 4
- Pages
- 408-416
- ISSN
- 0041-1655 (ISSN-L)
- 1526-5447
- OpenAlex
- W2168210873
- Cited by
- 1,022
- References
- 49
- FWCI
- 95.81
- Type
- journal article
- 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.