A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows

Yunqiang Yin; Dongwei Li; Dujuan Wang; Joshua Ignatius; T. C.E. Cheng; Sutong Wang

doi:10.1016/j.ejor.2023.02.030

A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows

Yunqiang Yin, Dongwei Li, Dujuan Wang, Joshua Ignatius, T. C.E. Cheng, Sutong Wang

Research output: Journal article publication › Journal article › Academic research › peer-review

39 Citations (Scopus)

Abstract

Increasing e-commerce activities poses a tough challenge for logistics distribution. With the development of new technology, firms attempt to leverage drones for parcel delivery to improve delivery efficiency and reduce overall costs. We consider the truck-based drone delivery routing problem with time windows. In our setting, a set of trucks and drones (each truck is associated with a drone) collaborate to serve customers, where a drone can take off from its associated truck at a node, independently serve one or more customers within the time windows, and return to the truck at another node along the truck route. To solve the problem, we develop an enhanced branch-and-price-and-cut algorithm incorporating a bounded bidirectional labelling algorithm to solve the challenging pricing problem. To improve the algorithm, we use the subset-row inequalities to tighten the lower bound and apply enhancement strategies, which solve the pricing problem efficiency. We perform extensive numerical studies to evaluate the performance of the developed algorithm, assess the gain of the truck-based drone delivery over the truck-only delivery, and provide some managerial insights.

Original language	English
Pages (from-to)	1125-1144
Number of pages	20
Journal	European Journal of Operational Research
Volume	309
Issue number	3
DOIs	https://doi.org/10.1016/j.ejor.2023.02.030
Publication status	Published - 16 Sept 2023

Keywords

Column generation
Delivery
Logistics
Valid inequalities
Vehicle routing

ASJC Scopus subject areas

General Computer Science
Modelling and Simulation
Management Science and Operations Research
Information Systems and Management

More information

10.1016/j.ejor.2023.02.030

Cite this

@article{1da704c7f7c341608e617a60db99eb8f,

title = "A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows",

abstract = "Increasing e-commerce activities poses a tough challenge for logistics distribution. With the development of new technology, firms attempt to leverage drones for parcel delivery to improve delivery efficiency and reduce overall costs. We consider the truck-based drone delivery routing problem with time windows. In our setting, a set of trucks and drones (each truck is associated with a drone) collaborate to serve customers, where a drone can take off from its associated truck at a node, independently serve one or more customers within the time windows, and return to the truck at another node along the truck route. To solve the problem, we develop an enhanced branch-and-price-and-cut algorithm incorporating a bounded bidirectional labelling algorithm to solve the challenging pricing problem. To improve the algorithm, we use the subset-row inequalities to tighten the lower bound and apply enhancement strategies, which solve the pricing problem efficiency. We perform extensive numerical studies to evaluate the performance of the developed algorithm, assess the gain of the truck-based drone delivery over the truck-only delivery, and provide some managerial insights.",

keywords = "Column generation, Delivery, Logistics, Valid inequalities, Vehicle routing",

author = "Yunqiang Yin and Dongwei Li and Dujuan Wang and Joshua Ignatius and Cheng, {T. C.E.} and Sutong Wang",

note = "Funding Information: This paper was supported in part by the National Natural Science Foundation of China under grant numbers 71971041, 72171161, and 71871148; by the Major Program of National Social Science Foundation of China under Grant 20&ZD084; by the special key project of Chengdu Philosophy and social science planning “Young Eagle Plan” for “Study and Interpret the Party's Twenty Great Spirits” (2022E04); by the Key Research and Development Project of Sichuan Province (No. 2023YFS0397); by the Chengdu Philosophy and Social Science Planning Project (No. 2022C19); and by the Sichuan University to Building a World-class University (No. SKSYL2021-08). Funding Information: This paper was supported in part by the National Natural Science Foundation of China under grant numbers 71971041 , 72171161 , and 71871148 ; by the Major Program of National Social Science Foundation of China under Grant 20&ZD084; by the special key project of Chengdu Philosophy and social science planning “Young Eagle Plan” for “Study and Interpret the Party's Twenty Great Spirits” (2022E04); by the Key Research and Development Project of Sichuan Province (No. 2023YFS0397); by the Chengdu Philosophy and Social Science Planning Project (No. 2022C19); and by the Sichuan University to Building a World-class University (No. SKSYL2021-08). Publisher Copyright: {\textcopyright} 2023 Elsevier B.V.",

year = "2023",

month = sep,

day = "16",

doi = "10.1016/j.ejor.2023.02.030",

language = "English",

volume = "309",

pages = "1125--1144",

journal = "European Journal of Operational Research",

issn = "0377-2217",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows

AU - Yin, Yunqiang

AU - Li, Dongwei

AU - Wang, Dujuan

AU - Ignatius, Joshua

AU - Cheng, T. C.E.

AU - Wang, Sutong

N1 - Funding Information: This paper was supported in part by the National Natural Science Foundation of China under grant numbers 71971041, 72171161, and 71871148; by the Major Program of National Social Science Foundation of China under Grant 20&ZD084; by the special key project of Chengdu Philosophy and social science planning “Young Eagle Plan” for “Study and Interpret the Party's Twenty Great Spirits” (2022E04); by the Key Research and Development Project of Sichuan Province (No. 2023YFS0397); by the Chengdu Philosophy and Social Science Planning Project (No. 2022C19); and by the Sichuan University to Building a World-class University (No. SKSYL2021-08). Funding Information: This paper was supported in part by the National Natural Science Foundation of China under grant numbers 71971041 , 72171161 , and 71871148 ; by the Major Program of National Social Science Foundation of China under Grant 20&ZD084; by the special key project of Chengdu Philosophy and social science planning “Young Eagle Plan” for “Study and Interpret the Party's Twenty Great Spirits” (2022E04); by the Key Research and Development Project of Sichuan Province (No. 2023YFS0397); by the Chengdu Philosophy and Social Science Planning Project (No. 2022C19); and by the Sichuan University to Building a World-class University (No. SKSYL2021-08). Publisher Copyright: © 2023 Elsevier B.V.

PY - 2023/9/16

Y1 - 2023/9/16

N2 - Increasing e-commerce activities poses a tough challenge for logistics distribution. With the development of new technology, firms attempt to leverage drones for parcel delivery to improve delivery efficiency and reduce overall costs. We consider the truck-based drone delivery routing problem with time windows. In our setting, a set of trucks and drones (each truck is associated with a drone) collaborate to serve customers, where a drone can take off from its associated truck at a node, independently serve one or more customers within the time windows, and return to the truck at another node along the truck route. To solve the problem, we develop an enhanced branch-and-price-and-cut algorithm incorporating a bounded bidirectional labelling algorithm to solve the challenging pricing problem. To improve the algorithm, we use the subset-row inequalities to tighten the lower bound and apply enhancement strategies, which solve the pricing problem efficiency. We perform extensive numerical studies to evaluate the performance of the developed algorithm, assess the gain of the truck-based drone delivery over the truck-only delivery, and provide some managerial insights.

AB - Increasing e-commerce activities poses a tough challenge for logistics distribution. With the development of new technology, firms attempt to leverage drones for parcel delivery to improve delivery efficiency and reduce overall costs. We consider the truck-based drone delivery routing problem with time windows. In our setting, a set of trucks and drones (each truck is associated with a drone) collaborate to serve customers, where a drone can take off from its associated truck at a node, independently serve one or more customers within the time windows, and return to the truck at another node along the truck route. To solve the problem, we develop an enhanced branch-and-price-and-cut algorithm incorporating a bounded bidirectional labelling algorithm to solve the challenging pricing problem. To improve the algorithm, we use the subset-row inequalities to tighten the lower bound and apply enhancement strategies, which solve the pricing problem efficiency. We perform extensive numerical studies to evaluate the performance of the developed algorithm, assess the gain of the truck-based drone delivery over the truck-only delivery, and provide some managerial insights.

KW - Column generation

KW - Delivery

KW - Logistics

KW - Valid inequalities

KW - Vehicle routing

UR - http://www.scopus.com/inward/record.url?scp=85150026446&partnerID=8YFLogxK

U2 - 10.1016/j.ejor.2023.02.030

DO - 10.1016/j.ejor.2023.02.030

M3 - Journal article

AN - SCOPUS:85150026446

SN - 0377-2217

VL - 309

SP - 1125

EP - 1144

JO - European Journal of Operational Research

JF - European Journal of Operational Research

IS - 3

ER -

A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this