The multi-visit drone-assisted routing problem with soft time windows and stochastic truck travel times

We consider a combined truck-drone delivery problem with stochastic truck travel times and soft time windows. A fleet of homogeneous trucks and drones are deployed in pairs to provide delivery services to customers. Each drone can be launched from and retrieved to its truck multiple times, and in each flight, a drone can serve one or more customers. Our objective is to determine the truck routes and drone flights that minimise the total cost, including time window violation penalties. We formulate this problem into a two-stage stochastic model with recourse action in the second stage to optimise the truck waiting time at each node. We approximate the stochastic model with a large-scale mixed-integer program using the sample average approximation (SAA) framework, which is computationally intractable. To this end, we propose a hybrid metaheuristic approach that incorporates SAA. The waiting times obtained in the planning phase are only optimal against the sampled or estimated travel times along the entire route of each truck, whose actual values are known only once the truck has returned to the depot. To this end, we reformulate the second-stage model in a rolling-horizon manner, which can be easily implemented and efficiently solved in the execution phase. Extensive numerical experiments demonstrate the strong performance of the proposed metaheuristic approach and rolling-horizon model. The results also highlight the clear benefits of the stochastic modelling approach over its deterministic counterpart, with a pronounced reduction in total costs in various scenarios.