Integrating Autonomous Vehicles and Drones for Last-Mile Delivery: A Routing Problem with Two Types of Drones and Multiple Visits

With the growing demand for delivery services and the escalating labor costs, much effort has been made to achieve faster and cost-efficient delivery. A promising emerging strategy involves the integration of autonomous delivery vehicles or drones into the last-mile delivery. This study presents a fully automated last-mile delivery system that synergistically integrates autonomous vehicles and drones. We also introduce a novel variant of the vehicle routing problem with drones, referred to as the hybrid autonomous vehicle-drone routing problem (HAVDRP). In HAVDRP, we employ three delivery tools: autonomous vehicles, vehicle-carried drones, and independent drones. The aim is to fully leverage the advantages of autonomous vehicles and drones to provide customers with more efficient last-mile delivery services. An improved adaptive large neighborhood search algorithm is developed to address this problem. The algorithm incorporates a tabu list and an adaptive mechanism specifically designed for the HAVDRP, thereby augmenting the search efficiency. Computational experiments are conducted to evaluate the efficiency of the designed algorithm. Additionally, sensitivity analyses are conducted to explore the influences of some key parameters on the total time, which includes the cumulative working time of autonomous vehicles and drones. Based on the results of sensitivity analyses, we propose some management recommendations for the fully automated last-mile delivery system utilizing autonomous vehicles and drones.