Launching drones from a vessel: routing unmanned aerial vehicles from a linearly moving depot

Abstract Unmanned aerial vehicles (or drones) are expected to free urban areas from the negative impacts of traditional last-mile delivery by trucks and vans. To overcome one of the major operational challenges of drones, their limited range, existing concepts propose to launch them either from decentralized depots or trucks moving through the city center. Both solutions have drawbacks, so recent ideas suggest using river barges as mobile launch platforms. These ships act as linearly moving depots for drone launches, and this paper investigates the resulting routing problem when serving a given set of customers. First, we formulate the basic optimization problem and derive some structural properties through an in-depth computational complexity analysis. Based on these insights, we derive appropriate methods to attain exact, $$\rho $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ρ</mml:mi> </mml:math> -approximative, or heuristic solutions, and apply them to evaluate the potential savings of delivery vans (benchmarked as a standalone delivery option and as a van-drone tandem) if, instead, drones are launched from ships or trains.