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.

Automated summary

Increasing e-commerce activities have led to the need for efficient logistics distribution. To address this challenge, firms are exploring the use of drones for parcel delivery. We propose a truck-based drone delivery routing problem with time windows, where drones collaborate with trucks to serve customers within specified time frames. We develop an enhanced algorithm incorporating a bounded bidirectional labelling algorithm to solve the pricing problem, and perform extensive numerical studies to evaluate the algorithm's performance and provide managerial insights.