Multi-Depot Vehicle Routing Problem with Drones: Replicability, Revalidation, and Clustering Strategies

Last-mile logistics optimization with drones highlights the Drone Multi-Depot Vehicle Routing Problem (MDVRP-D), in which the AACO-NC-D algorithm has consolidated itself as a reference. This work presents an independent computational revalidation of the 1,150 published solutions for this method, evaluating the impact of strict accounting for standby time in stationary flight on drone battery restriction. The results reveal that 81.1% of these solutions are unfeasible under the strict model. Additionally, it is proposed the clustering by Voronoi Partition with adaptive diversity mechanism, which obtains the lowest average makespan in 22 of the 23 instances and establishes the first viable references under the strict model for medium and large instances.