Branch-price-and-cut for the truck-drone routing problem with time windows

Considering the important realistic benefits of drones combined with trucks for last-mile parcel deliveries, we define the truck-drone routing problem with time windows (TDRP-TW). The TDRP-TW has the characteristics of time windows, synchronization en route, direct delivery, multiple trucks, and multiple drones carried by each truck. Customers covered by truck routes can be used as drone launch/retrieval locations, which are called satellites in this study. The synchronization en route enables drones to launch from trucks to return to paired trucks at nodes other than departure sites if necessary. We present an effective branch-price-and-cut algorithm, in which a concept named candidate forward-satellite (CFS) is introduced to manage the labeling challenge caused by the synchronization en route. In addition, the branch-price-and-cut algorithm is combined with an adaptive large neighborhood search to obtain approximation solutions for large-scale instances. In the computational experiments, instances with up to 50 customers are solved to optimality, and approximation solutions of large-scale instances with 100 customers are presented.