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

Hailong Huang, Andrey V. Savkin, Chao Huang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

10 Citations (Scopus)


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.

Original languageEnglish
Article number9151388
Pages (from-to)1526-1534
Number of pages9
JournalIEEE Transactions on Industrial Informatics
Issue number2
Publication statusPublished - Feb 2021
Externally publishedYes


  • Control of parcel delivery systems
  • drones
  • parcel delivery
  • public transportation network
  • unmanned aerial vehicles

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Information Systems
  • Computer Science Applications
  • Electrical and Electronic Engineering

Cite this