The DOI matches its Crossref record; 11 of the 11 references it cites were found in a registry or an index.
Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
Abstract
This paper considers the design and analysis of algorithms for vehicle routing and scheduling problems with time window constraints. Given the intrinsic difficulty of this problem class, approximation methods seem to offer the most promise for practical size problems. After describing a variety of heuristics, we conduct an extensive computational study of their performance. The problem set includes routing and scheduling environments that differ in terms of the type of data used to generate the problems, the percentage of customers with time windows, their tightness and positioning, and the scheduling horizon. We found that several heuristics performed well in different problem environments; in particular an insertion-type heuristic consistently gave very good results.
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
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
Integer Programming Formulation of Traveling Salesman Problems
Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960) · Journal of the ACM · doi:10.1145/321043.321046 · Cited by 2,020
Computer Solutions of the Traveling Salesman Problem
Lin, S. (1965) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1965.tb04146.x · Cited by 1,986
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 heuristic algorithm for the multi-vehicle advance request dial-a-ride problem with time windows
Jaw, J.-J., Odoni, A. R., Psaraftis, H. N., & Wilson, N. H. M. (1986) · Transportation Research Part B Methodological · doi:10.1016/0191-2615(86)90020-2 · Cited by 624
Shekhar, S., Xiong, H. Y., & Zhou, X. S. (2017) · Encyclopedia of GIS · doi:10.1007/978-3-319-17885-1_101452 · Cited by 568
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
Route Constrained Fleet Scheduling
Orloff, C. S. (1976) · Transportation Science · doi:10.1287/trsc.10.2.149 · Cited by 85
Swersey, A. J., & Ballard, W. (1984) · Management Science · doi:10.1287/mnsc.30.7.844 · Cited by 81
Cited by
Ropke, S., & Pisinger, D. (2006) · Transportation Science · doi:10.1287/trsc.1050.0135 · Cited by 2,580
Handbook of Constraint Programming
(2006) · Foundations of Artificial Intelligence · doi:10.1016/s1574-6526(06)x8001-x · 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
The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations
Schneider, M., Stenger, A., & Goeke, D. (2014) · Transportation Science · doi:10.1287/trsc.2013.0490 · Cited by 1,312
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 New Optimization Algorithm for the Vehicle Routing Problem with Time Windows
Desrochers, M., Desrosiers, J., & Solomon, M. (1992) · Operations Research · doi:10.1287/opre.40.2.342 · Cited by 1,197
Self-citationVehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms
Bräysy, O., & Gendreau, M. (2005) · Transportation Science · doi:10.1287/trsc.1030.0056 · Cited by 1,135
Multifactorial Evolution: Toward Evolutionary Multitasking
Gupta, A., Ong, Y.-S., & Feng, L. (2016) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2015.2458037 · Cited by 993
The orienteering problem: A survey
Vansteenwegen, P., Souffriau, W., & Oudheusden, D. V. (2011) · European Journal of Operational Research · doi:10.1016/j.ejor.2010.03.045 · Cited by 989
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
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 review of recent research on green road freight transportation
Demir, E., Bektaş, T., & Laporte, G. (2014) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.12.033 · Cited by 772
Survey of research in the design and control of automated guided vehicle systems
Vis, I. F. A. (2006) · European Journal of Operational Research · doi:10.1016/j.ejor.2004.09.020 · Cited by 757
A Coevolutionary Framework for Constrained Multiobjective Optimization Problems
Tian, Y., Zhang, T., Xiao, J., Zhang, X., & Jin, Y. (2021) · IEEE Transactions on Evolutionary Computation · doi:10.1109/tevc.2020.3004012 · Cited by 735
Routing a mixed fleet of electric and conventional vehicles
Goeke, D., & Schneider, M. (2015) · European Journal of Operational Research · doi:10.1016/j.ejor.2015.01.049 · Cited by 607
Partial recharge strategies for the electric vehicle routing problem with time windows
Keskin, M., & Çatay, B. (2016) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2016.01.013 · Cited by 600
Shortest Path Problems with Resource Constraints
Irnich, S., & Desaulniers, G. (2006) · Column Generation · doi:10.1007/0-387-25486-2_2 · Cited by 597
The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations
Hiermann, G., Puchinger, J., Ropke, S., & Hartl, R. F. (2016) · European Journal of Operational Research · doi:10.1016/j.ejor.2016.01.038 · Cited by 584
Sengupta, S., Basak, S., & Peters, R. (2018) · Machine Learning and Knowledge Extraction · doi:10.3390/make1010010 · Cited by 543
Multi-Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows
Ombuki, B., Ross, B. J., & Hanshar, F. (2006) · Applied Intelligence · doi:10.1007/s10489-006-6926-z · Cited by 518
New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem
Baldacci, R., Mingozzi, A., & Roberti, R. (2011) · Operations Research · doi:10.1287/opre.1110.0975 · Cited by 506
Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows
Desaulniers, G., Errico, F., Irnich, S., & Schneider, M. (2016) · Operations Research · doi:10.1287/opre.2016.1535 · Cited by 497
Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows
Ropke, S., & Cordeau, J.-F. (2009) · Transportation Science · doi:10.1287/trsc.1090.0272 · Cited by 487
Baldacci, R., Mingozzi, A., & Roberti, R. (2012) · European Journal of Operational Research · doi:10.1016/j.ejor.2011.07.037 · Cited by 474
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
Battery swap station location-routing problem with capacitated electric vehicles
Yang, J., & Sun, H. (2015) · Computers & Operations Research · doi:10.1016/j.cor.2014.07.003 · Cited by 434
A unified solution framework for multi-attribute vehicle routing problems
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2014) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.09.045 · Cited by 433
Heuristics for multi-attribute vehicle routing problems: A survey and synthesis
Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013) · European Journal of Operational Research · doi:10.1016/j.ejor.2013.02.053 · Cited by 430
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
Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows
Jepsen, M., Petersen, B., Spoorendonk, S., & Pisinger, D. (2008) · Operations Research · doi:10.1287/opre.1070.0449 · Cited by 410
Applications and Research avenues for drone-based models in logistics: A classification and review
Moshref-Javadi, M., & Winkenbach, M. (2021) · Expert Systems with Applications · doi:10.1016/j.eswa.2021.114854 · Cited by 391
The electric vehicle routing problem and its variations: A literature review
Kucukoglu, I., Dewil, R., & Cattrysse, D. (2021) · Computers & Industrial Engineering · doi:10.1016/j.cie.2021.107650 · Cited by 384
Chapter 2 Time constrained routing and scheduling
Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1995) · Handbooks in Operations Research and Management Science · doi:10.1016/s0927-0507(05)80106-9 · Cited by 374
Self-citationAn 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 vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food
Osvald, A., & Stirn, L. Z. (2008) · Journal of Food Engineering · doi:10.1016/j.jfoodeng.2007.07.008 · Cited by 366
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
Simulated annealing metaheuristics for the vehicle routing problem with time windows
Chiang, W.-C., & Russell, R. A. (1996) · Annals of Operations Research · doi:10.1007/bf02601637 · Cited by 354
Iterated local search for the team orienteering problem with time windows
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Van Oudheusden, D. (2009) · Computers & Operations Research · doi:10.1016/j.cor.2009.03.008 · Cited by 353
Kuo, Y. (2010) · Computers & Industrial Engineering · doi:10.1016/j.cie.2010.03.012 · Cited by 343
The electric location routing problem with time windows and partial recharging
Schiffer, M., & Walther, G. (2017) · European Journal of Operational Research · doi:10.1016/j.ejor.2017.01.011 · Cited by 343
THE LAST MILE CHALLENGE: EVALUATING THE EFFECTS OF CUSTOMER DENSITY AND DELIVERY WINDOW PATTERNS
Boyer, K. K., Prud'homme, A. M., & Chung, W. (2009) · Journal of Business Logistics · doi:10.1002/j.2158-1592.2009.tb00104.x · Cited by 321
Heuristic methods for vehicle routing problem with time windows
Tan, K. C., Lee, L. H., Zhu, Q. L., & Ou, K. (2001) · Artificial Intelligence in Engineering · doi:10.1016/s0954-1810(01)00005-x · Cited by 310
PSO-based algorithm for home care worker scheduling in the UK
Akjiratikarl, C., Yenradee, P., & Drake, P. R. (2007) · Computers & Industrial Engineering · doi:10.1016/j.cie.2007.06.002 · Cited by 296
Li, X., Tian, P., & Leung, S. C. H. (2010) · International Journal of Production Economics · doi:10.1016/j.ijpe.2010.01.013 · Cited by 288
Ghoseiri, K., & Ghannadpour, S. F. (2010) · Applied Soft Computing · doi:10.1016/j.asoc.2010.04.001 · Cited by 282
Rich Vehicle Routing Problem: Survey
Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., & Juan, A. A. (2015) · ACM Computing Surveys · doi:10.1145/2666003 · Cited by 280
Real-Time Multivehicle Truckload Pickup and Delivery Problems
Yang, J., Jaillet, P., & Mahmassani, H. (2004) · Transportation Science · doi:10.1287/trsc.1030.0068 · Cited by 280
A Survey on the Electric Vehicle Routing Problem: Variants and Solution Approaches
Erdelić, T., & Carić, T. (2019) · Journal of Advanced Transportation · doi:10.1155/2019/5075671 · Cited by 270
On-Time Last-Mile Delivery: Order Assignment with Travel-Time Predictors
Liu, S., He, L., & Max Shen, Z.-J. (2021) · Management Science · doi:10.1287/mnsc.2020.3741 · Cited by 268
Mobile Element Scheduling with Dynamic Deadlines
Somasundara, A. A., Ramamoorthy, A., & Srivastava, M. B. (2007) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2007.57 · Cited by 265
Waste collection multi objective model with real time traceability data
Faccio, M., Persona, A., & Zanin, G. (2011) · Waste Management · doi:10.1016/j.wasman.2011.07.005 · Cited by 263
Time-dependent vehicle routing problem with path flexibility
Huang, Y., Zhao, L., Van Woensel, T., & Gross, J.-P. (2017) · Transportation Research Part B: Methodological · doi:10.1016/j.trb.2016.10.013 · Cited by 257
Vehicle routing with time windows: An overview of exact, heuristic and metaheuristic methods
El-Sherbeny, N. A. (2010) · Journal of King Saud University - Science · doi:10.1016/j.jksus.2010.03.002 · Cited by 257
A matheuristic method for the electric vehicle routing problem with time windows and fast chargers
Keskin, M., & Çatay, B. (2018) · Computers & Operations Research · doi:10.1016/j.cor.2018.06.019 · Cited by 256
Liu, X., Laporte, G., Chen, Y., & He, R. (2017) · Computers & Operations Research · doi:10.1016/j.cor.2017.04.006 · Cited by 250
Xiao, Y., Zhang, Y., Kaku, I., Kang, R., & Pan, X. (2021) · Renewable and Sustainable Energy Reviews · doi:10.1016/j.rser.2021.111567 · Cited by 236
Liu, C., Kou, G., Zhou, X., Peng, Y., Sheng, H., & Alsaadi, F. E. (2020) · Knowledge-Based Systems · doi:10.1016/j.knosys.2019.06.021 · Cited by 150
An exact algorithm for agile earth observation satellite scheduling with time-dependent profits
Peng, G., Song, G., Xing, L., Gunawan, A., & Vansteenwegen, P. (2020) · Computers & Operations Research · doi:10.1016/j.cor.2020.104946 · Cited by 93
Reusken, M., Laporte, G., Rohmer, S. U. K., & Cruijssen, F. (2024) · European Journal of Operational Research · doi:10.1016/j.ejor.2024.03.031 · Cited by 23
Metadata
- Authors
- Solomon, M. M.
- Venue
- Operations Research
- Published
- 1987-04
- Volume
- 35
- Issue
- 2
- Pages
- 254-265
- ISSN
- 0030-364X (ISSN-L)
- 1526-5463
- OpenAlex
- W2096305430
- Cited by
- 4,298
- References
- 11
- FWCI
- 22.66
- 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.