Drone delivery from trucks: Drone scheduling for given truck routes

Last mile deliveries with unmanned aerial vehicles (also denoted as drones) are seen as one promising idea to reduce excessive road traffic. To overcome the difficulties caused by the comparatively short operating ranges of drones, an innovative concept suggests to apply trucks as mobile landing and take-off platforms. In this context, the paper on hand schedules the delivery to customers by drones for given truck routes. Given a fixed sequence of stops constituting a truck route and a set of customers to be supplied, we aim at a drone schedule (i.e., a set of trips each defining a drone's take-off and landing stop and the customer serviced), such that all customers are supplied and the total duration of the delivery tour is minimized. We differentiate whether multiple drones or just a single one are placed on a truck and whether or not take-off and landing stops have to be identical. We provide an analysis of computational complexity for each resulting subproblem, introduce efficient mixed-integer programs, and compare all cases with regard to their potential of reducing the delivery effort on the last mile.