Drone Routing in a Time-Dependent Network: Toward Low-Cost and Large-Range Parcel Delivery

Drones are a promising tool for parcel delivery, since they are cost-efficient and environmentally friendly. However, owing to the limited capacity of the on-board battery, their flight range is constrained. Thus, they cannot deliver some parcels if the customers are too far from the depot. To address this issue, this article proposes a novel method, in which a parcel delivery drone can 'take' a public transportation vehicle and travel on its roof. The problem under consideration is how to make use of the public transportation network to route the drone between the depot and the customer. Compared to the currently available methods that use drones, the most important merit of this approach is a significant expansion of the delivery area. We construct a multimodal network consisting of public transportation vehicles' trips and drone flights. Because of the complexity of this multimodal network, we convert it to a simple network with a set of simple procedures. In the extended network, we formulate the shortest drone path problem that minimizes the return instant to the depot, subject to that the drone energy consumption on this path is no greater than the initial energy. We present a Dijkstra-based method to find the shortest drone path. Moreover, we extend the proposed method to the case with uncertainty, because the public transportation vehicles cannot exactly follow their timetables in practice. Simulation results are presented to demonstrate how the method works.