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

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 win-dows. 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 incorpo-rating 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 evalu-ate 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.(c) 2023 Elsevier B.V. All rights reserved.