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 and Sutong Wang

European Journal of Operational Research, 2023, vol. 309, issue 3, 1125-1144

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: Logistics; Delivery; Vehicle routing; Column generation; Valid inequalities (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723001625
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:309:y:2023:i:3:p:1125-1144

DOI: 10.1016/j.ejor.2023.02.030

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().