Multiple ground/aerial parcel delivery problem: a Weighted Road Network Voronoi Diagram based approach

Po wei Harn, Ji Zhang, Ting Shen, Wenlu Wang, Xunfei Jiang, Wei Shinn Ku, Min Te Sun, Yao Yi Chiang

研究成果: 雜誌貢獻期刊論文同行評審

1 引文 斯高帕斯(Scopus)

摘要

The Multiple Ground/Aerial Parcel Delivery Problem (MGAPDP), an extension of the Ground/Aerial Parcel Delivery Problem (GAPDP), aims to find an optimal partition that minimizes the overall delivery time of all trucks by serving all destinations once and returning to the distribution center. This paper presents two heuristic solutions to the MGAPDP based on the Weighted Road Network Voronoi Diagram, i.e., Multiplicatively Weighted Road Network Voronoi Diagram (MRVD) and Additively Weighted Road Network Voronoi Diagram (ARVD). In our proposed problem, we assume that trucks travel on road networks, and UAVs move in Euclidean spaces and can be launched at any locations on roads. Each truck is equipped with a UAV, and each UAV can only be operated in Visual-Line-Of-Sight (VLOS) areas. When only one truck is considered, an intuitive approach is to check all possible locations on roads in the VLOS areas and find a globally optimal location for every destination if UAVs are used for delivery. As for multiple trucks, all of the partitions of destinations have to be considered. To avoid high computational cost for multiple truck/UAV pairs, the Weighted Road Network Voronoi Diagram is utilized to form the delivery group for each truck/UAV pair. All of the results are evaluated through extensive experiments, and the results indicate that, while both heuristic solutions effectively reduce the delivery time especially when the number of truck/UAV pairs is low, ARVD has exhibited a lower delivery time than MRVD in the majority of the considered scenarios.

原文???core.languages.en_GB???
頁(從 - 到)549-569
頁數21
期刊Distributed and Parallel Databases
41
發行號4
DOIs
出版狀態已出版 - 12月 2023

指紋

深入研究「Multiple ground/aerial parcel delivery problem: a Weighted Road Network Voronoi Diagram based approach」主題。共同形成了獨特的指紋。

引用此