The drone-assisted pickup and delivery problem: An adaptive large neighborhood search metaheuristic

The use of unmanned aerial vehicles (UAVs), also known as drones, for last-mile delivery has grown in popularity in research and industry over the last decade. We propose a mathematical model formulation for the coordination of parcel pickups and deliveries between trucks and drones in this paper, which we call the drone-assisted pickup and delivery problem (DAPDP). In the DAPDP, multiple trucks depart a depot with a UAV on board. As the trucks pick up packages and make deliveries, the corresponding UAV can also be used to make deliveries to customers near the truck’s position. While the UAVs are making deliveries, the trucks continue on their route, making additional deliveries along the way, and retrieving the UAVs at customer locations other than the launch points. We formulate the DAPDP model as a mixed integer linear program (MILP) and propose an adaptive large neighborhood search (ALNS) metaheuristic to solve it for instances of practical size. Additionally, we propose a novel method for benchmarking the performance of the proposed metaheuristic, which concretely certifies the quality of the solution, with all optimality gaps under 3%.