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

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.