A Novel Adaptive Large Neighborhood Search Heuristic for the UAV Routing Problem with Multiple Time Windows

Unmanned Aerial Vehicles (UAVs) have emerged as a promising alternative for last-mile delivery, offering cost-effective, rapid, and flexible logistics solutions; however, their limited battery life, payload capacity, and operational range impose significant routing challenges. This paper introduces a novel hybrid Adaptive Large Neighborhood Search (ALNS) framework for the UAV Routing Problem with Multiple Time Windows (UAV-RPMTW), a problem variant that explicitly allows flexible service scheduling. The proposed method integrates adaptive destroy-and-repair operator selection for optimal time-window assignment, enabling an effective balance between routing efficiency and service feasibility. The algorithm further enhances search performance through diversified neighborhood operators and tabu-based restart strategies to balance exploration and exploitation. Comprehensive experiments on new UAV-RPMTW benchmark datasets indicate that the method surpasses baseline approaches in both solution quality and runtime performance, yielding an average improvement of approximately 40 cost units between average and best solutions and achieving best solutions within an average of 39 seconds per instance.