Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles

Bai, X., Cao, M., Yan, W. & Ge, S. S., 12-Jan-2020, In : IEEE Transactions on Automation Science and Engineering. 17, 1, p. 248-260

Research output: Contribution to journalArticleAcademicpeer-review

Copy link to clipboard



  • Xiaoshan Bai
  • Ming Cao
  • Weisheng Yan
  • Shuzhi Sam Ge
This paper studies the precedence-constrained task
assignment problem for a team of heterogeneous vehicles to
deliver packages to a set of dispersed customers subject to
precedence constraints that specify which customers need to be
visited before which other customers. A truck and a micro drone
with complementary capabilities are employed where the truck
is restricted to travel in a street network and the micro drone,
restricted by its loading capacity and operation range, can fly
from the truck to perform the last-mile package deliveries. The
objective is to minimize the time to serve all the customers
respecting every precedence constraint. The problem is shown
to be NP-hard, and a lower bound on the optimal time to
serve all the customers is constructed by using tools from graph
theory. Then, integrating with a topological sorting technique,
several heuristic task assignment algorithms are proposed to
solve the task assignment problem. Numerical simulations show
the superior performances of the proposed algorithms compared
with popular genetic algorithms.
Original languageEnglish
Pages (from-to)248-260
JournalIEEE Transactions on Automation Science and Engineering
Issue number1
Publication statusPublished - 12-Jan-2020

Download statistics

No data available

ID: 111897552