Optimisation of Multi-Type Logistics UAV Scheduling under High Demand

Hong Jiang; Tong Wu; Xinhui Ren; Lizhen Gou

doi:10.7307/ptt.v36i1.261

Authors

Hong Jiang Civil Aviation University of China
Tong Wu Civil Aviation University of China
Xinhui Ren Civil Aviation University of China
Lizhen Gou Civil Aviation University of China

DOI:

https://doi.org/10.7307/ptt.v36i1.261

Keywords:

logistics distribution, logistics UAVs, improved ant colony algorithm, delivery path

Abstract

At present, interest in the application of unmanned aerial vehicles (UAV) for delivery is growing. A new “multi-type of UAV collaborative delivery” mode has been proposed. Through a combination of large, medium and small UAVs, the delivery capabilities of the UAV logistics system are significantly improved. Sometimes there is high demand, resulting in planned delivery routes that are no longer feasible, and even cause a shortage of distribution centre capacity and drones. This study explores logistics delivery strategies to solve problems caused by high demand. In this study, a multitype and multidistribution UAV model was established with the objective of minimising the total cost of distribution by considering factors such as the UAV energy consumption, load and distribution centre conditions. An improved ant colony algorithm was designed and its effectiveness was verified through the variability of the calculation time and multiple calculation results of different-scale examples. Finally, the classic vehicle routing problem (VRP) case is used in three scenarios to analyse the UAV scheduling optimisation problem. The results indicate that assisted delivery can reduce costs by 3% while ensuring delivery timeliness. The results of this study can provide guidance and benchmarks for the application of UAVs in urban logistics delivery systems.

References

Khan SI, et al. UAVs path planning architecture for effective medical emergency response in future networks. Physical Communication. 2021;47:101337. DOI: 10.1016/j.phycom.2021.101337.

Song BD, Park K, Kim J. Persistent UAV delivery logistics: MILP formulation and efficient heuristic. Computers & Industrial Engineering. 2018;120:418-428. DOI: 10.1016/j.cie.2018.05.013.

Hwang J, Kim I, Gulzar MA. Understanding the eco-friendly role of UAV food delivery services: Deepening the theory of planned behavior. Sustainability. 2020;12(4):1440. DOI: 10.3390/su12041440.

Hwang J, Lee J, Kim H. Perceived innovativeness of UAV food delivery services and its impacts on attitude and behavioral intentions: The moderating role of gender and age. International Journal of Hospitality Management. 2019;81:94-103. DOI: 10.1016/j.ijhm.2019.03.002.

Liu Y. An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using UAVs. Computers & Operations Research. 2019;111:1-20. DOI: 10.1016/j.cor.2019.05.024.

Lin Y, Lyu J, Jiang Y. Research on optimization of drone delivery based on urban-rural transportation considering time-varying characteristics of traffic. Application Research of Computers. 2020;37(10):2984-2989. DOI: 10.19734/j.issn.1001-3695.2019.07.0210.

Pinto R, Lagorio A. Point-to-point UAV-based delivery network design with intermediate charging stations. Transportation Research Part C: Emerging Technologies. 2022;135:103506. DOI: 10.1016/j.trc.2021.103506.

Deng X, et al. Vehicle-assisted UAV delivery scheme considering energy consumption for instant delivery. Sensors. 2022;22(5):2045. DOI: 10.3390/s22052045.

Cao Q, Zhang X, Ren X. Path optimization of joint delivery mode of trucks and UAVs. Mathematical Problems in Engineering. 2021;2021:1-15. DOI: 10.1155/2021/4670997.

Thibbotuwawa A, et al. UAV mission planning resistant to weather uncertainty. Sensors. 2020;20(2):515. DOI: 10.3390/s20020515.

Huang J-L，et al. Fault influence model of swarm UAVs based on cellular automata. Control and Decision. 2023;38(1):103-111. DOI: 10.13195/j.kzyjc.2021.0910.

Glaudel HS. Establishing the framework for e-VTOL Flight mission scenario development for urban air mobility research using cognitive task analysis. AIAA Aviation 2021 Forum. 2021; p. 2339.

Torabbeigi M, et al. An Optimization approach to minimize the expected loss of demand considering UAV failures in UAV Delivery scheduling. Journal of Intelligent & Robotic Systems. 2021;102(1):1-15. DOI: 10.1007/s10846-021-01370-w.

Ren XH, Gou LZ, Wu T. Drone last delivery under uncertainty failure. Journal of Guangxi University (Natural Science Edition). 2022;47(03):732-745. DOI: 10.13624/j.cnki.issn.1001-7445.2022.0732.

Ren XH, Gou LZ, Wu T. Disturbance recovery model of logistics drone with capacity disturbance. Science, Technology and Engineering. 2023;23(01):407-413.

Torabbeigi M, Lim GJ, Kim SJ. UAV delivery schedule optimization considering the reliability of UAVs. 2018 International Conference on Unmanned Aircraft Systems (ICUAS). IEEE; 2018. p. 1048-1053.

Sawadsitang S, et al. Joint ground and aerial package delivery services: A stochastic optimization approach. IEEE Transactions on Intelligent Transportation Systems. 2019;20(6):2241-2254. DOI: 10.1109/TITS.2018.2865893.

Sawadsitang S, et al. Shipper cooperation in stochastic UAV delivery: A dynamic Bayesian game approach. IEEE Transactions on Vehicular Technology. 2021;70(8):7437-7452. DOI: 10.48550/arXiv.2002.03118.

Sawadsitang S, et al. Multi-objective optimization for UAV delivery. 2019 IEEE 90th Vehicular Technology Conference (VTC2019-Fall). IEEE; 2019. p. 1-5.

Wang Z, Dessouky M, van Woensel T, Ioannou P. Pickup and delivery problem with hard time windows considering stochastic and time-dependent travel times. EURO Journal on Transportation and Logistics. Vol. 12. 2023. DOI: 10.1016/j.ejtl.2022.100099.

Kim SJ, Lim GJ, Cho J. Drone flight scheduling under uncertainty on battery duration and air temperature. Computers & Industrial Engineering. 2018;117:291-302. DOI: 10.1016/j.cie.2018.02.005.

Kim SJ, Lim GJ, Cho J. A robust optimization approach for scheduling UAVs considering uncertainty of battery duration. Proceedings of the IIE Annual Conference. Institute of Industrial and Systems Engineers (IISE); 2017. p. 187-192.

Di Puglia Pugliese L, Guerriero F, Scutellá MG. The last-mile delivery process with trucks and UAVs under uncertain energy consumption. Journal of Optimization Theory and Applications. 2021;191(1):31-67. DOI: 10.1007/s10957-021-01918-8.

Patel R, et al. Robust multi-UAV route planning considering UAV failure. 2019 International Conference on Unmanned Aircraft Systems (ICUAS). 2019. p. 205-212.

Sung I, et al. A design of a scheduling system for an unmanned aerial vehicle (UAV) deployment. IFAC-PapersOnLine. 2019;52(13):1854-1859. DOI: 10.1016/j.ifacol.2019.11.472.

Kang H, et al. Time coordination of multiple UAVs over switching communication networks with digraph topologies. 2021 IEEE International Systems Conference(SysCon). 2021. p. 5964-9. DOI: 10.1109/CDC45484.2021.9683619.

Rabta B, Wankmüller C, Reiner G. A drone fleet model for last-mile distribution in disaster relief operations. International Journal of Disaster Risk Reduction. 2018;28:107-112. DOI: 10.1016/j.ijdrr.2018.02.020.

Huang H, Savkin AV, Huang C. Drone routing in a time-dependent network: Toward low-cost and large-range parcel delivery. IEEE Transactions on Industrial Informatics. 2021;17(2):1526-1534. DOI: 10.1109/TII.2020.3012162.

Zhang C, Liu Y, Hu C. Path planning with time windows for multiple UAVs based on Gray Wolf algorithm. Biomimetics. 2022;7:225. DOI: 10.3390/biomimetics7040225.

Nikolić M, Teodorović D. Vehicle rerouting in the case of unexpectedly high demand in distribution systems. Transportation Research Part C: Emerging Technologies. 2015;55:535-545. DOI: 10.1016/j.trc.2015.03.002.

Cheng C, Adulyasak Y, Rousseau LM. Drone routing with energy function: Formulation and exact algorithm. Transportation Research Part B: Methodological. 2020;139:364-387. DOI: 10.1016/j.trb.2020.06.011.

D'Andrea R. Guest editorial can drones deliver?. IEEE Transactions on Automation Science & Engineering. 2014;11(3):647-648. DOI: 10.1109/TASE.2014.2326952.

Aggarwal S, Kumar N. Path planning techniques for unmanned aerial vehicles: A review, solutions, and challenges. Computer Communications. 2020;149:270-299. DOI: 10.1016/j.comcom.2019.10.014.

Dorigo M, Birattari M, Stützle T. Ant colony optimization. IEEE Computational Intelligence Magazine. 2006;1(4):28-39. DOI: 10.1109/MCI.2006.329691.

Dorigo M, Caro GD. The ant colony optimization metaheuristic: Algorithms, applications, and advances. McGraw-Hil Ltd; 2006. DOI: 10.1007/0-306-48056-5_9.

Eitzen H, et al. A multi-objective two-echelon vehicle routing problem. An urban goods movement approach for smart city logistics. 2017 XLIII Latin American Computer Conference (CLEI). IEEE; 2017. p. 1-10.