The Vehicle Routing Problem: State-of-the-Art Classification and Review
Source abstract
Abstract
Transportation planning has been established as a key topic in the literature and social production practices. An increasing number of researchers are studying vehicle routing problems (VRPs) and their variants considering real-life applications and scenarios. Furthermore, with the rapid growth in the processing speed and memory capacity of computers, various algorithms can be used to solve increasingly complex instances of VRPs. In this study, we analyzed recent literature published between 2019 and August of 2021 using a taxonomic framework. We reviewed recent research according to models and solutions, and divided models into three categories of customer-related, vehicle-related, and depot-related models. We classified solution algorithms into exact, heuristic, and meta-heuristic algorithms. The main contribution of our study is a classification table that is available online as Appendix A. This classification table should enable future researchers to find relevant literature easily and provide readers with recent trends and solution methodologies in the field of VRPs and some well-known variants.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Vehicle Routing Optimization Methods · Transportation and Mobility Innovations · Urban and Freight Transport Logistics
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Industrial Engineering and Engineering Management, Integration and Collaboration Laboratory, National Tsing Hua University, Hsinchu 30013, Taiwan
References (100+)
Show source-provided references
1. The Truck Dispatching Problem10.1287/mnsc.6.1.80 ↗
2. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points10.1287/opre.12.4.568 ↗
3. The Vehicle Routing Problem: State of the Art Classification and Review10.1016/j.cie.2015.12.007 ↗
4. The Vehicle Routing Problem: A Taxonomic Review10.1016/j.cie.2009.05.009 ↗
5. A Taxonomic Review of Metaheuristic Algorithms for Solving the Vehicle Routing Problem and Its Variants10.1016/j.cie.2019.106242 ↗
6. Konstantakopoulos, G.D., Gayialis, S.P., and Kechagias, E.P. (2020). Vehicle Routing Problem and Related Algorithms for Logistics Distribution: A Literature Review and Classification. Oper. Res. Int. J., 1–30.10.1007/s12351-020-00600-7 ↗
7. Chapter 6 Vehicle Routing
8. Golden, B.L., Raghavan, S., and Wasil, E.A. (2008). The Vehicle Routing Problem: Latest Advances and New Challenges, Springer Science and Business Media.10.1007/978-0-387-77778-8 ↗
9. Toth, P., and Vigo, D. (2014). Vehicle Routing: Problems, Methods, and Applications, SIAM.10.1137/1.9781611973594 ↗
10. Nalepa, J. (2019). Smart Delivery Systems: Solving Complex Vehicle Routing Problems, Elsevier.
11. Complexity of Vehicle Routing and Scheduling Problems10.1002/net.3230110211 ↗
12. A Concise Guide to Existing and Emerging Vehicle Routing Problem Variants10.1016/j.ejor.2019.10.010 ↗
13. The Green Vehicle Routing Problem: A Systematic Literature Review10.1016/j.jclepro.2020.123691 ↗
14. Sustainable Vehicle Routing Problem for Coordinated Solid Waste Management
15. Nguyen, M.A., Dang, G.T.-H., Hà, M.H., and Pham, M.-T. (2021). The min-cost parallel drone scheduling vehicle routing problem. Eur. J. Oper. Res., In Press.10.1016/j.ejor.2021.07.008 ↗
16. Electric Vehicle Routing Problem with Machine Learning for Energy Prediction10.1016/j.trb.2020.12.007 ↗
17. Multi-Trip Time-Dependent Vehicle Routing Problem with Time Windows10.1016/j.ejor.2020.09.022 ↗
18. A Simulation-Based Heuristic for the Electric Vehicle Routing Problem with Time Windows and Stochastic Waiting Times at Recharging Stations10.1016/j.cor.2020.105060 ↗
19. Two-Echelon Collaborative Multi-Depot Multi-Period Vehicle Routing Problem10.1016/j.eswa.2020.114201 ↗
20. A Column Generation Approach for an Emission-Oriented Vehicle Routing Problem on a Multigraph10.1016/j.ejor.2020.06.035 ↗
21. Multi-Objective Optimization of a Two-Echelon Vehicle Routing Problem with Vehicle Synchronization and “Grey zone”Customers Arising in Urban Logistics10.1016/j.ejor.2019.07.049 ↗
22. A New Hybrid Whale Optimization Algorithm for Green Vehicle Routing Problem10.1080/21642583.2020.1863276 ↗
23. Agile Optimization of a Two-Echelon Vehicle Routing Problem with Pickup and Delivery10.1111/itor.12796 ↗
24. Tabu Search for the Time-Dependent Vehicle Routing Problem with Time Windows on a Road Network10.1016/j.ejor.2020.05.041 ↗
25. The Online Vehicle Routing Problem with Occasional Drivers10.1016/j.cor.2020.105144 ↗
26. A Two-Stage Metaheuristic Algorithm for the Dynamic Vehicle Routing Problem in Industry 4.0 Approach
27. Combining Simheuristics with Petri Nets for Solving the Stochastic Vehicle Routing Problem with Correlated Demands10.1016/j.eswa.2020.114240 ↗
28. NSGA-II with Objective-Specific Variation Operators for Multiobjective Vehicle Routing Problem with Time Windows10.1016/j.eswa.2021.114779 ↗
29. Solving Capacitated Vehicle Routing Problem Using Cooperative Firefly Algorithm10.1016/j.asoc.2021.107403 ↗
30. A Hybrid Variable Neighborhood Search Approach for the Multi-Depot Green Vehicle Routing Problem10.1016/j.tre.2021.102293 ↗
31. An Improved Simulated Annealing Algorithm with Crossover Operator for Capacitated Vehicle Routing Problem10.1016/j.swevo.2021.100911 ↗
32. Hybrid Genetic-Sweep Algorithm to Solve the Vehicle Routing Problem with Drones10.1016/j.phycom.2020.101236 ↗
33. A Branch-and-Price Algorithm for the Vehicle Routing Problem with Stochastic Demands and Probabilistic Duration Constraints10.1287/trsc.2020.1002 ↗
34. Vehicle Routing Problem for Reverse Logistics of End-of-Life Vehicles (ELVs)10.1016/j.wasman.2020.11.008 ↗
35. Waiting Strategy for the Vehicle Routing Problem with Simultaneous Pickup and Delivery Using Genetic Algorithm10.1016/j.eswa.2020.113959 ↗
36. An Adaptive Large Neighborhood Search Heuristic for the Vehicle Routing Problem with Time Windows and Delivery Robots10.1016/j.ejor.2021.02.027 ↗
37. Modelling and Multi-Criteria Analysis of the Sustainability Dimensions for the Green Vehicle Routing Problem10.1016/j.ejor.2020.10.028 ↗
38. A Hybrid Algorithm for Time-Dependent Vehicle Routing Problem with Time Windows10.1016/j.cor.2020.105193 ↗
39. An Exact Algorithm for the Electric-Vehicle Routing Problem with Nonlinear Charging Time10.1080/01605682.2020.1730250 ↗
40. Two-Echelon Vehicle Routing Problem with Satellite Bi-Synchronization10.1016/j.ejor.2020.06.019 ↗
41. Time-Dependent Multi-Depot Green Vehicle Routing Problem with Time Windows Considering Temporal-Spatial Distance10.1016/j.cor.2021.105211 ↗
42. A Case-Based Reasoning Approach to Solve the Vehicle Routing Problem with Time Windows and Drivers’ Experience10.1016/j.omega.2020.102340 ↗
43. A Parallelised Large Neighbourhood Search Heuristic for the Asymmetric Two-Echelon Vehicle Routing Problem with Swap Containers for Cargo-Bicycles10.1016/j.ejor.2020.07.034 ↗
44. Lin, B., Ghaddar, B., and Nathwani, J. (2021). Deep Reinforcement Learning for the Electric Vehicle Routing Problem with Time Windows. IEEE Trans. Intell. Transp. Syst., Early Access.10.1109/TITS.2021.3105232 ↗
45. Collaborative Multi-Depot Pickup and Delivery Vehicle Routing Problem with Split Loads and Time Windows10.1016/j.knosys.2021.107412 ↗
46. Online Clustering Reduction Based on Parametric and Non-Parametric Correlation for a Many-Objective Vehicle Routing Problem with Demand Responsive Transport10.1016/j.eswa.2020.114467 ↗
47. The Joint Order Batching and Picker Routing Problem: Modelled and Solved as a Clustered Vehicle Routing Problem10.1016/j.cor.2020.105168 ↗
48. An Improved Learnable Evolution Model for Solving Multi-Objective Vehicle Routing Problem with Stochastic Demand10.1016/j.knosys.2021.107378 ↗
49. Jia, Y.H., Mei, Y., and Zhang, M. (2021). A Bilevel Ant Colony Optimization Algorithm for Capacitated Electric Vehicle Routing Problem. IEEE Trans. Cybern.10.1109/TCYB.2021.3069942 ↗
50. Optimization of Capacitated Vehicle Routing Problem with Alternative Delivery, Pick-Up and Time Windows: A Modified Hybrid Approach10.1016/j.neucom.2020.02.126 ↗
51. MIMOA: A Membrane-Inspired Multi-Objective Algorithm for Green Vehicle Routing Problem with Stochastic Demands10.1016/j.swevo.2020.100767 ↗
52. A Route Decomposition Approach for the Single Commodity Split Pickup and Split Delivery Vehicle Routing Problem10.1016/j.ejor.2019.07.015 ↗
53. The Vehicle Routing Problem with Heterogeneous Locker Boxes10.1007/s10100-020-00725-2 ↗
54. Vehicle Routing Problem with Zone-Based Pricing10.1016/j.tre.2021.102383 ↗
55. A Hyper Heuristic for the Green Vehicle Routing Problem with Simultaneous Pickup and Delivery10.1016/j.cie.2020.107010 ↗
56. The Quality-Driven Vehicle Routing Problem: Model and Application to a Case of Cooperative Logistics10.1016/j.ijpe.2020.107849 ↗
57. An Ensemble Learning Based Multi-Objective Evolutionary Algorithm for the Dynamic Vehicle Routing Problem with Time Windows10.1016/j.cie.2021.107131 ↗
58. A Vehicle Routing Problem with Distribution Uncertainty in Deadlines10.1016/j.ejor.2020.10.026 ↗
59. Period Sewage Recycling Vehicle Routing Problem Based on Real-Time Data10.1016/j.jclepro.2020.125628 ↗
60. Addressing Orientation Symmetry in the Time Window Assignment Vehicle Routing Problem
61. Heuristic Approaches for a Vehicle Routing Problem with an Incompatible Loading Constraint and Splitting Deliveries by Order10.1016/j.cor.2021.105379 ↗
62. An Optimization Model and Solution Algorithms for the Vehicle Routing Problem with a “Factory-in-a-Box”10.1109/ACCESS.2020.3010176 ↗
63. An Efficient Parallel Genetic Algorithm Solution for Vehicle Routing Problem in Cloud Implementation of the Intelligent Transportation Systems10.1186/s13677-020-0157-4 ↗
64. Two Echelon Vehicle Routing Problem with Drones in Last Mile Delivery10.1016/j.ijpe.2019.107598 ↗
65. The Electric Vehicle Routing Problem with Time Windows and Synchronised Mobile Battery Swapping10.1016/j.trb.2020.06.012 ↗
66. Fuzzy Optimization Model for Electric Vehicle Routing Problem with Time Windows and Recharging Stations10.1016/j.eswa.2019.113123 ↗
67. Metaheuristics for Solving the Vehicle Routing Problem with the Time Windows and Energy Consumption in Cold Chain Logistics10.1016/j.asoc.2020.106561 ↗
68. Fuzzy Green Vehicle Routing Problem for Designing a Three Echelons Supply Chain10.1016/j.jclepro.2020.120774 ↗
69. Composite Multi-Objective Optimization on a New Collaborative Vehicle Routing Problem with Shared Carriers and Depots10.1016/j.jclepro.2020.122593 ↗
70. A Memory-Based Iterated Local Search Algorithm for the Multi-Depot Open Vehicle Routing Problem10.1016/j.ejor.2020.01.008 ↗
71. Solving the Vehicle Routing Problem with Multi-Compartment Vehicles for City Logistics10.1016/j.cor.2019.104859 ↗
72. Multi-Depot Multi-Trip Vehicle Routing Problem with Time Windows and Release Dates10.1016/j.tre.2020.101866 ↗
73. Electric Vehicle Routing Problem with Non-Linear Charging and Load-Dependent Discharging10.1016/j.eswa.2020.113714 ↗
74. An ACS-Based Memetic Algorithm for the Heterogeneous Vehicle Routing Problem with Time Windows10.1016/j.eswa.2020.113379 ↗
75. The Electric Vehicle Routing Problem with Time Windows and Multiple Recharging Options10.1109/ACCESS.2020.3003000 ↗
76. The Time-Dependent Electric Vehicle Routing Problem: Model and Solution10.1016/j.eswa.2020.113593 ↗
77. Logic-Based Benders Decomposition for the Heterogeneous Fixed Fleet Vehicle Routing Problem with Time Windows10.1016/j.cie.2020.106641 ↗
78. A Relative Robust Optimization for a Vehicle Routing Problem with Time-Window and Synchronized Visits Considering Greenhouse Gas Emissions10.1016/j.jclepro.2020.124112 ↗
79. A Firefly Algorithm for the Environmental Prize-Collecting Vehicle Routing Problem10.1016/j.swevo.2020.100712 ↗
80. Two-Echelon Vehicle Routing Problem with Time Windows and Mobile Satellites10.1016/j.trb.2020.05.010 ↗
81. Hybrid differential evolution algorithm and genetic operator for multi-trip vehicle routing problem with backhauls and heterogeneous fleet in the beverage logistics industry10.1016/j.cie.2020.106571 ↗
82. Vehicle Routing Problem with Drones10.1016/j.trb.2019.03.005 ↗
83. The Electric Vehicle Routing Problem with Energy Consumption Uncertainty10.1016/j.trb.2019.06.006 ↗
84. A Matheuristic for the Vehicle Routing Problem with Drones and Its Variants10.1016/j.trc.2019.06.016 ↗
85. A Path-Based Solution Approach for the Green Vehicle Routing Problem10.1016/j.cor.2018.10.019 ↗
86. An Improved Ant Colony Optimization Algorithm for the Multi-Depot Green Vehicle Routing Problem with Multiple Objectives10.1016/j.jclepro.2019.03.185 ↗
87. Energy Consumption Estimation Integrated into the Electric Vehicle Routing Problem10.1016/j.trd.2019.01.006 ↗
88. The Electric Two-Echelon Vehicle Routing Problem10.1016/j.cor.2018.11.005 ↗
89. A Vehicle Routing Problem Arising in Unmanned Aerial Monitoring10.1016/j.cor.2019.01.001 ↗
90. The Vehicle Routing Problem with Profits and Consistency Constraints10.1016/j.ejor.2018.09.046 ↗
91. Electric Vehicle Routing Problem with Time-Dependent Waiting Times at Recharging Stations10.1016/j.cor.2019.02.014 ↗
92. Solving the Feeder Vehicle Routing Problem Using Ant Colony Optimization10.1016/j.cie.2018.10.037 ↗
93. Knowledge-Guided Local Search for the Vehicle Routing Problem10.1016/j.cor.2019.01.002 ↗
94. A Hybrid Multi-Objective Genetic Local Search Algorithm for the Prize-Collecting Vehicle Routing Problem10.1016/j.ins.2018.11.006 ↗
95. An Adaptive Large Neighborhood Search Metaheuristic for the Vehicle Routing Problem with Drones10.1016/j.trc.2019.02.018 ↗
96. A Hybrid VNS/Tabu Search Algorithm for Solving the Vehicle Routing Problem with Drones and En Route Operations10.1016/j.cor.2019.04.021 ↗
97. Time-Dependent and Bi-Objective Vehicle Routing Problem with Time Windows10.14743/apem2019.2.322 ↗
98. Improved Formulations and Algorithmic Components for the Electric Vehicle Routing Problem with Nonlinear Charging Functions10.1016/j.cor.2018.12.013 ↗
99. A Branch-and-Price Algorithm for the Heterogeneous Fleet Green Vehicle Routing Problem with Time Windows10.1016/j.trb.2019.03.009 ↗
100. A Multi-Adaptive Particle Swarm Optimization for the Vehicle Routing Problem with Time Windows10.1016/j.ins.2018.12.086 ↗