The DOI matches its Crossref record; 32 of the 32 references it cites were found in a registry or an index.
A general heuristic for vehicle routing problems
Abstract
We present a unified heuristic which is able to solve five different variants of the vehicle routing problem: the vehicle routing problem with time windows (VRPTW), the capacitated vehicle routing problem (CVRP), the multi-depot vehicle routing problem (MDVRP), the site-dependent vehicle routing problem (SDVRP) and the open vehicle routing problem (OVRP). All problem variants are transformed into a rich pickup and delivery model and solved using the adaptive large neighborhood search (ALNS) framework presented in Ropke and Pisinger [An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, to appear]. The ALNS framework is an extension of the large neighborhood search framework by Shaw [Using constraint programming and local search methods to solve vehicle routing problems. In: CP-98, Fourth international conference on principles and practice of constraint programming, Lecture notes in computer science, vol. 1520, 1998. p. 417-31] with an adaptive layer. This layer adaptively chooses among a number of insertion and removal heuristics to intensify and diversify the search. The presented approach has a number of advantages: it provides solutions of very high quality, the algorithm is robust, and to some extent self-calibrating. Moreover, the unified model allows the dispatcher to mix various variants of VRP problems for individual customers or vehicles. As we believe that the ALNS framework can be applied to a large number of tightly constrained optimization problems, a general description of the framework is given, and it is discussed how the various components can be designed in a particular setting. The paper is concluded with a computational study, in which the five different variants of the vehicle routing problem are considered on standard benchmark tests from the literature. The outcome of the tests is promising as the algorithm is able to improve 183 best known solutions out of 486 benchmark tests. The heuristic has also shown promising results for a large class of vehicle routing problems with backhauls as demonstrated in Ropke and Pisinger [A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research, 2004, to appear].
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
Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
Solomon, M. M. (1987) · Operations Research · doi:10.1287/opre.35.2.254 · Cited by 4,298
(2002) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718515 · Cited by 4,008
Issues in Supply Chain Management
Lambert, D. M., & Cooper, M. C. (2000) · Industrial Marketing Management · doi:10.1016/s0019-8501(99)00113-3 · Cited by 3,099
Ropke, S., & Pisinger, D. (2006) · Transportation Science · doi:10.1287/trsc.1050.0135 · Cited by 2,580
Self-citationUsing 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 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
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
A 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
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
Feillet, D., Dejax, P., Gendreau, M., & Gueguen, C. (2004) · Networks · doi:10.1002/net.20033 · Cited by 693
VEHICLE ROUTING: METHODS AND STUDIES
Golden, B., & Assad, A. A. (1988) · North-Holland eBooks · Cited by 691
Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization
(1998) · Springer eBooks · doi:10.1007/978-1-4615-5775-3 · Cited by 669
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
Padberg, M. (1980) · Mathematical programming studies · doi:10.1007/bfb0120883 · Cited by 577
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
Fleet Management and Logistics
(1998) · Springer eBooks · doi:10.1007/978-1-4615-5755-5 · Cited by 485
Record Breaking Optimization Results Using the Ruin and Recreate Principle
Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H., & Dueck, G. (2000) · Journal of Computational Physics · doi:10.1006/jcph.1999.6413 · Cited by 413
2-Path Cuts for the Vehicle Routing Problem with Time Windows
Kohl, N., Desrosiers, J., Madsen, O. B. G., Solomon, M. M., & Soumis, F. (1999) · Transportation Science · doi:10.1287/trsc.33.1.101 · Cited by 411
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
A Two-Stage Hybrid Local Search for the Vehicle Routing Problem with Time Windows
Bent, R., & Van Hentenryck, P. (2004) · Transportation Science · doi:10.1287/trsc.1030.0049 · Cited by 355
An Introduction to Variable Neighborhood Search
Hansen, P., & Mladenović, N. (1999) · Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization · doi:10.1007/978-1-4615-5775-3_30 · Cited by 340
Vehicle Routing Problem with elementary shortest path based column generation
Chabrier, A. (2006) · Computers & Operations Research · doi:10.1016/j.cor.2005.02.029 · Cited by 232
2-Path Cuts for the Vehicle Routing Problem with Time Windows
Desrosiers, J., Solomon, M. M., Soumis, F., Kohl, N., & Madsen, O. B. G. (1997) · Les Cahiers du GERAD · Cited by 225
Fleet Management and Logistics.
Ittmann, H. W., Crainic, T. G., & Gilbert Laporte, A. (1999) · Journal of the Operational Research Society · doi:10.2307/3010639 · Cited by 221
The Shortest-Path Problem with Resource Constraints and k-Cycle Elimination for k ≥ 3
Irnich, S., & Villeneuve, D. (2006) · INFORMS Journal on Computing · doi:10.1287/ijoc.1040.0117 · Cited by 215
A cooperative parallel meta-heuristic for the vehicle routing problem with time windows
Bouthillier, A. L., & Crainic, T. G. (2004) · Computers & Operations Research · doi:10.1016/j.cor.2003.11.023 · Cited by 194
A new tabu search heuristic for the open vehicle routing problem
Fu, Z., Eglese, R., & Li, Y. O. (2004) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2601817 · Cited by 160
A Route-Directed Hybrid Genetic Approach For The Vehicle Routing Problem With Time Windows
Berger, J., Barkaoui, M., & Bräysy, O. (2003) · INFOR Information Systems and Operational Research · doi:10.1080/03155986.2003.11732675 · Cited by 119
A new hybrid genetic algorithm for the capacitated vehicle routing problem
Berger, J., & Barkaoui, M. (2003) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2601635 · Cited by 116
Robust Branch-and-Cut-and-Price for the Capacitated Vehicle Routing Problem
Fukasawa, R., Lysgaard, J., de Aragão, M. P., Reis, M., Uchoa, E., & Werneck, R. F. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-25960-2_1 · Cited by 50
Cited by
Ropke, S., & Pisinger, D. (2006) · Transportation Science · doi:10.1287/trsc.1050.0135 · Cited by 2,580
Self-citationHyper-heuristics: a survey of the state of the art
Burke, E. K., Gendreau, M., Hyde, M., Kendall, G., Ochoa, G., Özcan, E., & Qu, R. (2013) · Journal of the Operational Research Society · doi:10.1057/jors.2013.71 · Cited by 1,263
Fifty Years of Vehicle Routing
Laporte, G. (2009) · Transportation Science · doi:10.1287/trsc.1090.0301 · Cited by 1,022
An adaptive large neighborhood search heuristic for the Pollution-Routing Problem
Demir, E., Bektaş, T., & Laporte, G. (2012) · European Journal of Operational Research · doi:10.1016/j.ejor.2012.06.044 · Cited by 726
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
Metadata
- Authors
- Pisinger, D., & Ropke, S.
- Venue
- Computers & Operations Research
- Publisher
- Elsevier BV
- Published
- 2007-08
- Volume
- 34
- Issue
- 8
- Pages
- 2403-2435
- ISSN
- 0305-0548 (ISSN-L)
- OpenAlex
- W2109101401
- Cited by
- 1,443
- References
- 32
- FWCI
- 73.77
- 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.