Abstract
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%.
Original language | English (US) |
---|---|
Article number | 106435 |
Journal | Computers and Operations Research |
Volume | 161 |
DOIs | |
State | Published - Jan 2024 |
Keywords
- Adaptive large neighborhood search
- Drone
- Integer programming
- Pickup and delivery
- Vehicle routing problem
ASJC Scopus subject areas
- Computer Science(all)
- Modeling and Simulation
- Management Science and Operations Research