Time Dependent Drone-aided Vehicle Routing Problem with Time Windows and Multi-visits

The continuous development of e-commerce and ongoing pandemic in recent years leads to a large increase in the demand for last-mile delivery with higher standards of service quality. The usage of unmanned aerial vehicles, also known as drones, is an ideal solution for such complex delivery problems. When designing the delivery system with the drone, we cannot omit the following features of drones: drones have the unique ability to avoid traffic congestion compared to truck traveling; and the dispatched drones need customer assistance to retrieve goods in parcel releasing procedures. In this paper, the time-dependent vehicle routing problem with drones and time windows (TDVRPDTW) is introduced. For practical application scenarios, the parcel releasing operation of drones needs customer assistance. Thus, the drone visits are fulfilled in given time windows for each demand point. Besides, the time-dependent traveling routes of trucks are also considered to capture road congestion. The objective is to minimize total route makespan, and vehicles’ dispatch times at the depot are crucial to avoid urban congestion. We present a branch-and-price algorithm to solve the optimization. The master problem is solved using a customized column generation algorithm and the pricing problem is solved by a tailored labeling algorithm with a novel dominance rule that allows more label dominance. For our numerous experimental results, we modified Solomon’s data sets by adding time dependency. Our algorithm can solve all the small-scale and medium-scale instances optimally. In terms of large-size instances, more than 90\% are solved optimally within 2 hours