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

i

This article has been updated. A Correction to this article was published on .

i

The Original Article was published on

i

The Original Article was published on

i

This article has been updated

i

This article was retracted on

i

This article has been updated

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.

Keywords

last-mile delivery / urban logistics / spatiotemporal clustering / hybrid algorithm / vehicle routing problem

CHANGE HISTORY

A Correction to this paper has been published:
https://doi.org

The Retraction Note was updated to reflect reception of statements of disagreement from all authors.

This article has been retracted.Please see the Retraction Notice for more detail:
https://doi.org

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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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.3272685

[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

[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

[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

[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

[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