Branch‐price‐and‐cut for the truck–drone routing problem with time windows
研究了带时间窗的卡车-无人机协同配送问题，提出分支定价切割算法，可精确求解50个客户以内的实例，并用自适应大邻域搜索近似求解100个客户的大规模问题。
Abstract 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.