On the Scheduling of Conflictual Deliveries in a last-mile delivery scenario with truck-carried drones

In this paper, we investigate the symbiosis between a truck and multiple drones in a last-mile package delivery scenario, introducing the Scheduling Conflictual Deliveries Problem (SCDP). From the main depot, a truck takes care of transporting a fleet of drones that will be used to deliver packages to customers. The route of the truck is predefined. Each delivery is associated with the energy cost of a drone, a reward that characterizes the priority of the delivery, and an interval between two points of the truck's route: the point from which the drone departs (launch point) and the point at which the drone returns to the truck (rendezvous point). The objective of the SCDP is to find a scheduling for the drones that maximizes the overall reward subject to the drone's battery capacity while ensuring that the same drone performs deliveries whose delivery intervals do not intersect. After showing that SCDP is an NP-hard problem, we devise an Integer Linear Programming (ILP) formulation for it. Furthermore, we devise a pseudo-polynomial time optimal algorithm for the single drone case and additional approximation algorithms for both the single and multiple drones case. Finally, we thoroughly compare the performances of our presented algorithms on different synthetic datasets.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

The paper investigates the cooperation between a truck and multiple drones in the last-mile package delivery scenario, presenting the Scheduling Conflictual Deliveries Problem (SCDP). The truck transports a fleet of drones from the main depot for package delivery. Each delivery is associated with the energy cost, reward, and interval along the truck's route. The objective of the SCDP is to find a scheduling for the drones that maximizes the overall reward while considering the battery capacity and non-intersecting delivery intervals. The paper proposes an Integer Linear Programming (ILP) formulation, optimal algorithm for single drone case, and approximation algorithms for both single and multiple drones cases. Extensive performance comparisons are conducted on synthetic datasets.