Drone Routing in a Time-Dependent Network: Toward Low-Cost and Large-Range Parcel Delivery
Publication Name
IEEE Transactions on Industrial Informatics
Abstract
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.
Open Access Status
This publication is not available as open access
Volume
17
Issue
2
Article Number
9151388
First Page
1526
Last Page
1534
Funding Number
TII-20-2583
Funding Sponsor
Australian Research Council