Optimizing routing for autonomous delivery and pickup vehicles in three-dimensional space

Qi Hong; Hongyi Zhao; Shiyu Chen; Aya Selmoune; Kai Huang; Qi Hong; Hongyi Zhao; Shiyu Chen; Aya Selmoune; Kai Huang

doi:10.3934/era.2025118

Electronic Research Archive

2025, Volume 33, Issue 4: 2668-2697. doi: 10.3934/era.2025118

Previous Article Next Article

Research article Special Issues

Optimizing routing for autonomous delivery and pickup vehicles in three-dimensional space

1.
School of Transportation, Southeast University, Nanjing 210096, China
2.
The Cho Chun Shik Graduate School of Mobility, Korea Advanced Institute of Science and Technology, South Korea
3.
School of Instrument Science and Engineering, Southeast University, Nanjing 210096, China
4.
Wuxi Campus, Southeast University, Wuxi 214000‌‌, China

Received: 23 February 2025 Revised: 15 April 2025 Accepted: 18 April 2025 Published: 30 April 2025

The last-mile delivery challenge in three-dimensional (3D) multi-floor building environments has a significant impact on logistics efficiency. Although autonomous delivery robots (ADRs) have been widely adopted to address last-mile logistics, most existing studies focus on optimizing ADR routing in simplified two-dimensional environments. Moreover, optimal layout of goods within the robot's physical containers brings another challenge. Hence, this paper formalizes the Discrete Capacity Vehicle Routing Problem with Simultaneous Delivery-Pickup and Soft Time Windows (DCVRP-SDP-STW) in a 3D environment. To achieve high-quality solutions, we propose an improved ant colony optimization algorithm that considers spatiotemporal multi-stage clustering characteristics, leading to a significant reduction in computation time. A data preprocessing framework is also developed to convert real-world architectural topologies into navigable 3D routing networks. To validate the proposed model and algorithm, we conducted a case study in Nanjing. The results show that the algorithm can improve optimization outcomes by 23% to 94% compared to pre-optimization results based on the proximity principle, which can contribute to the advancement of efficient and intelligent autonomous delivery systems.
- last-mile delivery,
- urban logistics,
- spatiotemporal clustering,
- hybrid algorithm,
- vehicle routing problem
Citation: Qi Hong, Hongyi Zhao, Shiyu Chen, Aya Selmoune, Kai Huang. Optimizing routing for autonomous delivery and pickup vehicles in three-dimensional space[J]. Electronic Research Archive, 2025, 33(4): 2668-2697. doi: 10.3934/era.2025118

Related Papers:

Abstract

The last-mile delivery challenge in three-dimensional (3D) multi-floor building environments has a significant impact on logistics efficiency. Although autonomous delivery robots (ADRs) have been widely adopted to address last-mile logistics, most existing studies focus on optimizing ADR routing in simplified two-dimensional environments. Moreover, optimal layout of goods within the robot's physical containers brings another challenge. Hence, this paper formalizes the Discrete Capacity Vehicle Routing Problem with Simultaneous Delivery-Pickup and Soft Time Windows (DCVRP-SDP-STW) in a 3D environment. To achieve high-quality solutions, we propose an improved ant colony optimization algorithm that considers spatiotemporal multi-stage clustering characteristics, leading to a significant reduction in computation time. A data preprocessing framework is also developed to convert real-world architectural topologies into navigable 3D routing networks. To validate the proposed model and algorithm, we conducted a case study in Nanjing. The results show that the algorithm can improve optimization outcomes by 23% to 94% compared to pre-optimization results based on the proximity principle, which can contribute to the advancement of efficient and intelligent autonomous delivery systems.

References

[1]	J. Juhász, T. Bányai, Last mile logistics: an integrated view, IOP Conf. Ser.: Mater. Sci. Eng., 448 (2018), 012026. https://doi.org/10.1088/1757-899X/448/1/012026 doi: 10.1088/1757-899X/448/1/012026
[2]	C. Liu, Z. Wang, Z. Liu, K. Huang, Multi-Agent reinforcement learning framework for addressing Demand-Supply imbalance of Shared Autonomous Electric Vehicle, Transp. Res. Part E Logist. Transp. Rev., 197 (2025), 104062. https://doi.org/10.1016/j.tre.2025.104062 doi: 10.1016/j.tre.2025.104062
[3]	M. R. Ibarra, J. D. M. Saphores, 1,000 HP electric drayage trucks as a substitute for new freeway lanes construction, Transp. Res. Part Policy Pract., 171 (2023), 103646. https://doi.org/10.1016/j.tra.2023.103646 doi: 10.1016/j.tra.2023.103646
[4]	D. Huang, J. Zhang, Z. Liu, A robust coordinated charging scheduling approach for hybrid electric bus charging systems, Transp. Res. Part Transp. Environ., 125 (2023), 103955. https://doi.org/10.1016/j.trd.2023.103955 doi: 10.1016/j.trd.2023.103955
[5]	Z. Liu, X. Chen, Q. Meng, I. Kim, Remote park-and-ride network equilibrium model and its applications, Transp. Res. Part B Methodol., 117 (2018), 37–62. https://doi.org/10.1016/j.trb.2018.08.004 doi: 10.1016/j.trb.2018.08.004
[6]	J. R. Montoya-Torres, J. L. Franco, S. N. Isaza, H. F. Jiménez, N. Herazo-Padilla, A literature review on the vehicle routing problem with multiple depots, Comput. Ind. Eng., 79 (2015), 115–129.
[7]	C. C. Murray, A. G. Chu, The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery, Transp. Res. Part C Emerg. Technol., 54 (2015), 86–109. https://doi.org/10.1016/j.trc.2015.03.005 doi: 10.1016/j.trc.2015.03.005
[8]	D. Reyes, M. Savelsbergh, A. Toriello, Vehicle routing with roaming delivery locations, Transp. Res. Part C Emerg. Technol., 80 (2017), 71–91. https://doi.org/10.1016/j.trc.2017.04.003 doi: 10.1016/j.trc.2017.04.003
[9]	Y. Wang, Y. Wei, X. Wang, Z. Wang, H. Wang, A clustering-based extended genetic algorithm for the multidepot vehicle routing problem with time windows and three-dimensional loading constraints, Appl. Soft Comput., 133 (2023), 109922. https://doi.org/10.1016/j.asoc.2022.109922 doi: 10.1016/j.asoc.2022.109922
[10]	D. Huang, Z. Liu, P. Liu, J. Chen, Optimal transit fare and service frequency of a nonlinear origin-destination based fare structure, Transp. Res. Part E Logist. Transp. Rev., 96 (2016), 1–19. https://doi.org/10.1016/j.tre.2016.10.004 doi: 10.1016/j.tre.2016.10.004
[11]	Z. Jia, D. Huang, Z. Liu, Z. Hu, R. Liu, W. Yu, Multi-objective optimization for the sightseeing bus problem: Trade-off between tourists and operator, Expert Syst. Appl., 269 (2025), 126341. https://doi.org/10.1016/j.eswa.2024.126341 doi: 10.1016/j.eswa.2024.126341
[12]	Y. Liu, Z. Liu, R. Jia, DeepPF: A deep learning based architecture for metro passenger flow prediction, Transp. Res. Part C Emerg. Technol., 101 (2019), 18–34. https://doi.org/10.1016/j.trc.2019.01.027 doi: 10.1016/j.trc.2019.01.027
[13]	X. Chen, Z. Liu, K. Zhang, Z. Wang, A parallel computing approach to solve traffic assignment using path-based gradient projection algorithm, Transp. Res. Part C Emerg. Technol., 120 (2020), 102809. https://doi.org/10.1016/j.trc.2020.102809 doi: 10.1016/j.trc.2020.102809
[14]	Q. Cheng, Z. Wang, Y. Lin, Z. Liu, Capturing traffic state variation process: An analytical modeling approach, Transp. Res. Part E Logist. Transp. Rev., 198 (2025), 104119. https://doi.org/10.1016/j.tre.2025.104119 doi: 10.1016/j.tre.2025.104119
[15]	J. C. Thill, T. H. D. Dao, Y. Zhou, Traveling in the three-dimensional city: applications in route planning, accessibility assessment, location analysis and beyond, J. Transp. Geogr., 19 (2011), 405–421. https://doi.org/10.1016/j.jtrangeo.2010.11.007
[16]	T. Bektas, The multiple traveling salesman problem: an overview of formulations and solution procedures, omega, 34 (2006), 209–219.
[17]	B. Eksioglu, A. V. Vural, A. Reisman, The vehicle routing problem: A taxonomic review, Comput. Ind. Eng., 57 (2009), 1472–1483.
[18]	J. Mańdziuk, C. Nejman, Uct-based approach to capacitated vehicle routing problem, in Artificial Intelligence and Soft Computing: 14th International Conference, Proceedings, Part II 14. Springer International Publishing, (2015), 679–690. https://doi.org/10.1007/978-3-319-19369-4_60
[19]	G. Kim, Y. S. Ong, C. K. Heng, P. S. Tan, N. A. Zhang, City Vehicle Routing Problem (City VRP): A review, IEEE Trans. Intell. Transp. Syst., 16 (2015), 1654–1666. https://doi.org/10.1109/TITS.2015.2395536 doi: 10.1109/TITS.2015.2395536
[20]	B. L. Golden, Vehicle Routing Problems: Formulations and Heuristic Solution Techniques. Massachusetts Institute of Technology, Operations Research Center, 1975.
[21]	H. Quak, M. B. de Koster, Delivering goods in urban areas: how to deal with urban policy restrictions and the environment, Transp. Sci., 43 (2009), 211–227.
[22]	S. W. Lin, V. F. Yu, S. Y. Chou, A note on the truck and trailer routing problem, Expert Syst. Appl., 37 (2010), 899–903. https://doi.org/10.1016/j.eswa.2009.06.077 doi: 10.1016/j.eswa.2009.06.077
[23]	M. M. Solomon, Algorithms for the vehicle routing and scheduling problems with time window constraints, Oper. Res., 35 (1987), 254–265.
[24]	N. Balakrishnan, Simple heuristics for the vehicle routeing problem with soft time windows, J. Oper. Res. Soc., 44 (1993), 279–287.
[25]	M. Gendreau, F. Guertin, J. Y. Potvin, É. Taillard, Parallel tabu search for real-time vehicle routing and dispatching, Transp. Sci., 1999. https://doi.org/10.1287/trsc.33.4.381 doi: 10.1287/trsc.33.4.381
[26]	H. Hashimoto, T. Ibaraki, S. Imahori, M. Yagiura, The vehicle routing problem with flexible time windows and traveling times, Discrete Appl. Math., 154 (2006), 2271–2290. https://doi.org/10.1016/j.dam.2006.04.009 doi: 10.1016/j.dam.2006.04.009
[27]	E. Angelelli, R. Mansini, The vehicle routing problem with time windows and simultaneous pick-up and delivery, in Quantitative Approaches to Distribution Logistics and Supply Chain Management, Springer, (2002), 249–267.
[28]	M. Goetschalckx, C. Jacobs-Blecha, The vehicle routing problem with backhauls, Eur. J. Oper. Res., 42 (1989), 39–51.
[29]	A. M. Altabeeb, A. M. Mohsen, A. Ghallab, An improved hybrid firefly algorithm for capacitated vehicle routing problem, Appl. Soft Comput., 84 (2019), 105728.
[30]	L. M. Gambardella, É. Taillard, G. Agazzi, MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows, Istituto Dalle Molle Di Studi Sull Intelligenza Artificiale, 1999.
[31]	Y. Wang, L. Wang, Z. Peng, G. Chen, Z. Cai, L. Xing, A multi ant system based hybrid heuristic algorithm for vehicle routing problem with service time customization, Swarm Evol. Comput., 50 (2019), 100563. https://doi.org/10.1016/j.swevo.2019.100563 doi: 10.1016/j.swevo.2019.100563
[32]	H. Zhang, Q. Zhang, L. Ma, Z. Zhang, Y. Liu, A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows, Inf. Sci., 490 (2019), 166–190. https://doi.org/10.1016/j.ins.2019.03.070 doi: 10.1016/j.ins.2019.03.070
[33]	X. Zheng, F. Gao, X. Tong, Research on green vehicle path planning of AGVs with simultaneous pickup and delivery in intelligent workshop, Symmetry, 15 (2023), https://doi.org/10.3390/sym15081505 doi: 10.3390/sym15081505
[34]	A. Goel, V. Gruhn, A general vehicle routing problem, Eur. J. Oper. Res., 191 (2008), 650–660.
[35]	Z. Gu, X. Yang, Q. Zhang, W. Yu, Z. Liu, TERL: Two-stage ensemble reinforcement learning paradigm for large-scale decentralized decision making in transportation simulation, IEEE Trans. Knowl. Data Eng., 35 (2023), 13043–13054. https://doi.org/10.1109/TKDE.2023.3272688 doi: 10.1109/TKDE.2023.3272688
[36]	A. H. Golsefidi, F. B. Hüttel, I. Peled, S. Samaranayake, F. C. Pereira, A joint machine learning and optimization approach for incremental expansion of electric vehicle charging infrastructure, Transp. Res. Part Policy Pract., 178 (2023), 103863. https://doi.org/10.1016/j.tra.2023.103863 doi: 10.1016/j.tra.2023.103863
[37]	Y. Wang, S. Luo, J. Fan, L. Zhen, The multidepot vehicle routing problem with intelligent recycling prices and transportation resource sharing, Transp. Res. Part E Logist. Transp. Rev., 185 (2024), 103503. https://doi.org/10.1016/j.tre.2024.103503 doi: 10.1016/j.tre.2024.103503
[38]	S. Erdoğan, E. Miller-Hooks, A green vehicle routing problem, Transp. Res. Part E Logist. Transp. Rev., 48 (2012), 100–114. https://doi.org/10.1016/j.tre.2011.08.001 doi: 10.1016/j.tre.2011.08.001
[39]	X. Yang, Z. Liu, Q. Cheng, P. Liu, Geometry-aware car-following model construction: Theoretical modeling and empirical analysis on horizontal curves, Transp. Res. Part C Emerg. Technol., 166 (2024), 104772. https://doi.org/10.1016/j.trc.2024.104772 doi: 10.1016/j.trc.2024.104772
[40]	Z. Wang, Y. Lin, Z. Liu, Y. Zheng, P. Liu, Q. Cheng, Traffic Dynamics Modeling with an Extended S3 Car Following Model, Social Science Research Network, Rochester, https://doi.org/10.2139/ssrn.4882338

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)