Pickup and delivery problem with drones and scheduled lines

Abstract

This paper introduces a multimodal urban parcel delivery framework that integrates drones with scheduled bus services. We formulate the Pick-up-and-Delivery Problem with Drones and Scheduled Lines (PDP-DSL), in which drones serve first- and last-mile legs while parcels may use public transport for middle-mile transfers. The problem is modelled as an arc-based mixed-integer linear program. To address computational complexity and overcome well-known limitations to commercial solvers, this work develops tailored metaheuristics and feasibility checks based on Bellman–Ford for overall feasibility and dynamic programming for battery-related constraints. While a commercial solver drops in solution quality beyond 40 tasks in a synthetic case study, our ALNS with dynamic programming feasibility checks finds good quality solutions for up to 125 tasks. Results further show that in terms of routing distances, the PDP-DSL can be a suitable alternative to truck delivery and drone delivery.