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

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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.

Original languageEnglish (US)
JournalDistributed and Parallel Databases
DOIs
StateAccepted/In press - 2021
Externally publishedYes

Bibliographical note

Funding Information:
Funding was provided by National Science Foundation.

Publisher Copyright:
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.

Keywords

  • Parcel delivery problem
  • UAV
  • Visual-line-of-sight
  • Voronoi diagram

Fingerprint

Dive into the research topics of 'Multiple ground/aerial parcel delivery problem: a Weighted Road Network Voronoi Diagram based approach'. Together they form a unique fingerprint.

Cite this