Adaptive large neighborhood search algorithm for vehicle routing problem with drones with delivery options

Compared to traditional urban delivery systems, the last-mile delivery has become a complex issue due to lower daily customer demands, significant delivery time variations, and a widespread distribution of locations. The delivery time of customer orders is associated with the choice of delivery locations, where considerations of capacity and operating hours arise, especially when utilizing shared delivery spots such as parcel lockers. To address these issues and emphasize the advantages of shared parcel lockers, we propose a delivery problem with delivery options and preference levels. We define a routing scheme for the coordinated delivery of vehicles and drones, integrating various types of delivery locations. We solve this problem using an adaptive large neighborhood search algorithm with simulated annealing, introducing specific ruin and repair operators. These operators, combined with various operators from the literature, undergo numerical experiments. In the specific context of this problem, our proposed method outperforms conventional algorithms, such as large neighborhood search and a single-parent genetic algorithm.