Publication

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 13 p., 8725908.

Research output: Contribution to journalArticleAcademicpeer-review

APA

Bai, X., Cao, M., Yan, W., & Ge, S. S. (2020). Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles. IEEE Transactions on Automation Science and Engineering, 17(1), 248-260. [8725908]. https://doi.org/10.1109/TASE.2019.2914113

Author

Bai, Xiaoshan ; Cao, Ming ; Yan, Weisheng ; Ge, Shuzhi Sam. / Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles. In: IEEE Transactions on Automation Science and Engineering. 2020 ; Vol. 17, No. 1. pp. 248-260.

Harvard

Bai, X, Cao, M, Yan, W & Ge, SS 2020, 'Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles', IEEE Transactions on Automation Science and Engineering, vol. 17, no. 1, 8725908, pp. 248-260. https://doi.org/10.1109/TASE.2019.2914113

Standard

Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles. / Bai, Xiaoshan; Cao, Ming; Yan, Weisheng; Ge, Shuzhi Sam.

In: IEEE Transactions on Automation Science and Engineering, Vol. 17, No. 1, 8725908, 12.01.2020, p. 248-260.

Research output: Contribution to journalArticleAcademicpeer-review

Vancouver

Bai X, Cao M, Yan W, Ge SS. Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles. IEEE Transactions on Automation Science and Engineering. 2020 Jan 12;17(1):248-260. 8725908. https://doi.org/10.1109/TASE.2019.2914113


BibTeX

@article{cd2aa47ce03d4ae9b4a228f3331af3a3,
title = "Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles",
abstract = "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. Note to Practitioners - This paper presents several task assignment algorithms for the precedence-constrained package delivery for the team of a truck and a micro drone. The truck can carry the drone moving in a street network, while the drone completes the last-mile package deliveries. The practical contributions of this paper are fourfold. First, the precedence constraints on the ordering of the customers to be served are considered, which enables complex logistic scheduling for customers prioritized according to their urgency or importance. Second, the package delivery optimization problem is shown to be NP-hard, which clearly shows the need for creative approximation algorithms to solve the problem. Third, the constructed lower bound on the optimal time to serve all the customers helps to clarify for practitioners the limiting performance of a feasible solution. Fourth, the proposed task assignment algorithms are efficient and can be adapted for real scenarios.",
author = "Xiaoshan Bai and Ming Cao and Weisheng Yan and Ge, {Shuzhi Sam}",
year = "2020",
month = jan,
day = "12",
doi = "10.1109/TASE.2019.2914113",
language = "English",
volume = "17",
pages = "248--260",
journal = "IEEE Transactions on Automation Science and Engineering",
issn = "1545-5955",
publisher = "IEEE",
number = "1",

}

RIS

TY - JOUR

T1 - Efficient Routing for Precedence-Constrained Package Delivery for Heterogeneous Vehicles

AU - Bai, Xiaoshan

AU - Cao, Ming

AU - Yan, Weisheng

AU - Ge, Shuzhi Sam

PY - 2020/1/12

Y1 - 2020/1/12

N2 - 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. Note to Practitioners - This paper presents several task assignment algorithms for the precedence-constrained package delivery for the team of a truck and a micro drone. The truck can carry the drone moving in a street network, while the drone completes the last-mile package deliveries. The practical contributions of this paper are fourfold. First, the precedence constraints on the ordering of the customers to be served are considered, which enables complex logistic scheduling for customers prioritized according to their urgency or importance. Second, the package delivery optimization problem is shown to be NP-hard, which clearly shows the need for creative approximation algorithms to solve the problem. Third, the constructed lower bound on the optimal time to serve all the customers helps to clarify for practitioners the limiting performance of a feasible solution. Fourth, the proposed task assignment algorithms are efficient and can be adapted for real scenarios.

AB - 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. Note to Practitioners - This paper presents several task assignment algorithms for the precedence-constrained package delivery for the team of a truck and a micro drone. The truck can carry the drone moving in a street network, while the drone completes the last-mile package deliveries. The practical contributions of this paper are fourfold. First, the precedence constraints on the ordering of the customers to be served are considered, which enables complex logistic scheduling for customers prioritized according to their urgency or importance. Second, the package delivery optimization problem is shown to be NP-hard, which clearly shows the need for creative approximation algorithms to solve the problem. Third, the constructed lower bound on the optimal time to serve all the customers helps to clarify for practitioners the limiting performance of a feasible solution. Fourth, the proposed task assignment algorithms are efficient and can be adapted for real scenarios.

U2 - 10.1109/TASE.2019.2914113

DO - 10.1109/TASE.2019.2914113

M3 - Article

VL - 17

SP - 248

EP - 260

JO - IEEE Transactions on Automation Science and Engineering

JF - IEEE Transactions on Automation Science and Engineering

SN - 1545-5955

IS - 1

M1 - 8725908

ER -

ID: 111897552