Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment

Nikola Mardešić; Tomislav Erdelić; Tonči Carić; Marko Đurasević

doi:10.3390/math12010028

journal article Open Access Dec 21, 2023

Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment

Nikola Mardešić

Tomislav Erdelić

Tonči Carić

Marko Đurasević

Mathematics Vol. 12 No. 1 pp. 28 · MDPI AG

View at Publisher Save 10.3390/math12010028

Abstract

Urban logistics encompass transportation and delivery operations within densely populated urban areas. It faces significant challenges from the evolving dynamic and stochastic nature of on-demand and conventional logistics services. Further challenges arise with application doctrines shifting towards crowd-sourced platforms. As a result, “traditional” deterministic approaches do not adequately fulfil constantly evolving customer expectations. To maintain competitiveness, logistic service providers must adopt proactive and anticipatory systems that dynamically model and evaluate probable (future) events, i.e., stochastic information. These events manifest in problem characteristics such as customer requests, demands, travel times, parking availability, etc. The Stochastic Dynamic Vehicle Routing Problem (SDVRP) addresses the dynamic and stochastic information inherent in urban logistics. This paper aims to analyse the key concepts, challenges, and recent advancements and opportunities in the evolving urban logistics landscape and assess the evolution from classical VRPs, via DVRPs, to state-of-art SDVRPs. Further, coupled with non-reactive techniques, this paper provides an in-depth overview of cutting-edge model-based and model-free reactive solution approaches. Although potent, these approaches become restrictive due to the “curse of dimensionality”. Sacrificing granularity for scalability, researchers have opted for aggregation and decomposition techniques to overcome this problem and recent approaches explore solutions using deep learning. In the scope of this research, we observed that addressing real-world SDVRPs with a comprehensive resolution encounters a set of challenges, emphasising a substantial gap in the research field that warrants further exploration.

Topics

No keywords indexed for this article. Browse by subject →

References

180

[1]

Ehmke, J.F. (2012). Integration of Information and Optimization Models for Routing in City Logistics, Springer. 10.1007/978-1-4614-3628-7

[2]

Pillac "A review of dynamic vehicle routing problems" Eur. J. Oper. Res. (2013) 10.1016/j.ejor.2012.08.015

[3]

Ritzinger "A survey on dynamic and stochastic vehicle routing problems" Int. J. Prod. Res. (2016) 10.1080/00207543.2015.1043403

[4]

Dynamic vehicle routing problems: Three decades and counting

Harilaos N. Psaraftis, Min Wen, Christos A. Kontovas

Networks 2016 10.1002/net.21628

[5]

Rios "Recent dynamic vehicle routing problems: A survey" Comput. Ind. Eng. (2021) 10.1016/j.cie.2021.107604

[6]

Soeffker "Stochastic dynamic vehicle routing in the light of prescriptive analytics: A review" Eur. J. Oper. Res. (2022) 10.1016/j.ejor.2021.07.014

[7]

Zhang "Dynamic vehicle routing with random requests: A literature review" Int. J. Prod. Econ. (2023) 10.1016/j.ijpe.2022.108751

[8]

Hildebrandt "Opportunities for reinforcement learning in stochastic dynamic vehicle routing" Comput. Oper. Res. (2023) 10.1016/j.cor.2022.106071

[9]

Ghiani "Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies" Eur. J. Oper. Res. (2003) 10.1016/s0377-2217(02)00915-3

[10]

Laporte "The vehicle routing problem: An overview of exact and approximate algorithms" Eur. J. Oper. Res. (1992) 10.1016/0377-2217(92)90192-c

[11]

Psaraftis "A Dynamic Programming Solution to the Single Vehicle Many-to-Many Immediate Request Dial-a-Ride Problem" Transp. Sci. (1980) 10.1287/trsc.14.2.130

[12]

Dantzig "The Truck Dispatching Problem" Manag. Sci. (1959) 10.1287/mnsc.6.1.80

[13]

Eksioglu "The vehicle routing problem: A taxonomic review" Comput. Ind. Eng. (2009) 10.1016/j.cie.2009.05.009

[14]

Fisher "Optimal Solution of Vehicle Routing Problems Using Minimum K-Trees" Oper. Res. (1994) 10.1287/opre.42.4.626

[15]

Ropke, M.I.S., Cordeau, J.F., and Vigo, D. (2007). Branch-and-cut-and price for the capacitated vehicle routing problem with two-dimensional loading constraints. Proc. ROUTE.

[16]

Eilon "Distribution Management-Mathematical Modelling and Practical Analysis" IEEE Trans. Syst. Man, Cybern. (1974) 10.1109/tsmc.1974.4309370

[17]

Gheysens "A comparison of techniques for solving the fleet size and mix vehicle routing problem" Oper.-Res.-Spektrum (1984) 10.1007/bf01720070

[18]

Gendreau "Vehicle routing problem with time windows, Part I: Route construction and local search algorithms" Transp. Sci. (2005) 10.1287/trsc.1030.0056

[19]

Clarke "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points" Oper. Res. (1964) 10.1287/opre.12.4.568

[20]

An Analysis of Several Heuristics for the Traveling Salesman Problem

Daniel J. Rosenkrantz, Richard E. Stearns, Philip M. Lewis, II

SIAM Journal on Computing 1977 10.1137/0206041

[21]

Vidal "Heuristics for multi-attribute vehicle routing problems: A survey and synthesis" Eur. J. Oper. Res. (2013) 10.1016/j.ejor.2013.02.053

[22]

"A Survey on the Electric Vehicle Routing Problem: Variants and Solution Approaches" J. Adv. Transp. (2019)

[23]

Savelsbergh "The vehicle routing problem with time windows: Minimizing route duration" ORSA J. Comput. (1992) 10.1287/ijoc.4.2.146

[24]

Or, I. (1976). Traveling Salesman Type Combinatorial Problems and their Relation to the Logistics of Regional Blood Banking. [Ph.D. Thesis, Northwestern University].

[25]

Computer Solutions of the Traveling Salesman Problem

Shen Lin

Bell System Technical Journal 1965 10.1002/j.1538-7305.1965.tb04146.x

[26]

Fosin "Vehicle Routing Optimization Using Multiple Local Search Improvements" Automatika (2014) 10.7305/automatika.2014.01.580

[27]

Adaptation in Natural and Artificial Systems

John H. Holland

10.7551/mitpress/1090.001.0001

[28]

Resende, M., Ribeiro, C., Glover, F., and Marti, R. (2010). Handbook of Metaheuristics, Springer.

[29]

Dorigo, M., and Stützle, T. (2004). Ant Colony Optimization, The MIT Press. 10.7551/mitpress/1290.001.0001

[30]

Marinakis "Bumble bees mating optimization algorithm for the vehicle routing problem" Handbook of Swarm Intelligence. Adaptation, Learning, and Optimization (2011) 10.1007/978-3-642-17390-5_15

[31]

Kennedy, J., and Eberhart, R. (December, January 27). Particle swarm optimization. Proceedings of the ICNN’95—International Conference on Neural Networks, Perth, Australia.

[32]

Marinakis "A hybrid genetic—Particle Swarm Optimization Algorithm for the vehicle routing problem" Expert Syst. Appl. (2010) 10.1016/j.eswa.2009.06.085

[33]

Gendreau, M., and Potvin, J.Y. (2010). Handbook of Metaheuristics, Springer. [2nd ed.]. 10.1007/978-1-4419-1665-5

[34]

Optimization by Simulated Annealing

S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi

Science 1983 10.1126/science.220.4598.671

[35]

"Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulation Algorithm" J. Optim. Theory Appl. (1985) 10.1007/bf00940812

[36]

Glover "Tabu search—Part I" INFORMS J. Comput. (1990) 10.1287/ijoc.2.1.4

[37]

Glover "Tabu search—Part II" ORSA J. Comput. (1990) 10.1287/ijoc.2.1.4

[38]

Hansen "Variable neighborhood search" Comput. Oper. Res. (1997) 10.1016/s0305-0548(97)00031-2

[39]

Gendreau, M., and Potvin, J.Y. (2010). Handbook of Metaheuristics, Springer. 10.1007/978-1-4419-1665-5

[40]

Ropke "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows" Transp. Sci. (2006) 10.1287/trsc.1050.0135

[41]

Pisinger "A general heuristic for vehicle routing problems" Comput. Oper. Res. (2007) 10.1016/j.cor.2005.09.012

[42]

Mayer, T., Uhlig, T., and Rose, O. (2018, January 9–12). Simulation-based Autonomous Algorithm Selection for Dynamic Vehicle Routing Problems with the Help of Supervised Learning Methods. Proceedings of the 2018 Winter Simulation Conference (WSC), Gothenburg, Sweden. 10.1109/wsc.2018.8632452

[43]

Jakobović, D., Đurasević, M., Brkić, K., Fosin, J., Carić, T., and Davidović, D. (2023). Evolving Dispatching Rules for Dynamic Vehicle Routing with Genetic Programming. Algorithms, 16. 10.3390/a16060285

[44]

Jacobsen-Grocott, J., Mei, Y., Chen, G., and Zhang, M. (2017, January 5–8). Evolving heuristics for Dynamic Vehicle Routing with Time Windows using genetic programming. Proceedings of the 2017 IEEE Congress on Evolutionary Computation (CEC), Donostia, Spain. 10.1109/cec.2017.7969539

[45]

Gala, F.J.G., Ðurasević, M., and Jakobović, D. (2022, January 9–13). Genetic Programming for Electric Vehicle Routing Problem with Soft Time Windows. Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO’22), Boston, MA, USA. 10.1145/3520304.3528994

[46]

Gil-Gala, F.J., Afsar, S., Durasevic, M., Palacios, J.J., and Afsar, M. (2023, January 15–19). Genetic Programming for the Vehicle Routing Problem with Zone-Based Pricing. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’23), Lisbon, Portugal. 10.1145/3583131.3590366

[47]

Zeimpekis, V., Tarantilis, C.D., Giaglis, G.M., and Minis, I. (2007). Dynamic Fleet Management: Concepts, Systems, Algorithms & Case Studies, Springer. 10.1007/978-0-387-71722-7

[48]

Larsen "Partially dynamic vehicle routing—Models and algorithms" J. Oper. Res. Soc. (2002) 10.1057/palgrave.jors.2601352

[49]

Lund, K., Madsen, O., and Rygaard, J. (1996). Vehicle Routing Problems with Varying Degrees of Dynamism, Institute of Mathematical Modelling, Technical University of Denmark. IMM Technical Report 1/96.

[50]

Bertsimas "A Stochastic and Dynamic Vehicle Routing Problem in the Euclidean Plane" Oper. Res. (1991) 10.1287/opre.39.4.601

Showing 50 of 180 references

Metrics

18

Citations

180

References

Details

Published: Dec 21, 2023
Vol/Issue: 12(1)
Pages: 28
License: View

Authors

N

Nikola Mardešić

Faculty of Transport and Traffic Sciences, University of Zagreb, Vukelićeva 4, 10000 Zagreb, Croatia

T

Tomislav Erdelić

Faculty of Transport and Traffic Sciences, University of Zagreb, Vukelićeva 4, 10000 Zagreb, Croatia

T

Tonči Carić

Faculty of Transport and Traffic Sciences, University of Zagreb, Vukelićeva 4, 10000 Zagreb, Croatia

M

Marko Đurasević

Faculty of Electrical Engineering and Computing, University of Zagreb, Unska 3, 10000 Zagreb, Croatia

Funding

Postdoctoral Research Support Program at the Faculty of Transport and Traffic Sciences, University of Zagreb

Cite This Article

Nikola Mardešić, Tomislav Erdelić, Tonči Carić, et al. (2023). Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment. Mathematics, 12(1), 28. https://doi.org/10.3390/math12010028

Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment

You May Also Like