Multi-Depot Vehicle Routing Problem with Drones: Mathematical formulation, solution algorithm and experiments

The use of Unmanned Aerial Vehicles (UAVs) is expected to grow rapidly in the coming years, driven by technological advancements, cost-effectiveness, and the increasing demand for faster and more efficient delivery solutions. This article deals with the mathematical formulation of the Multi-Depot Vehicle Routing Problem with Drones (MDVRP-D), whereby a set of heterogeneous trucks, each paired with a UAV, are located in different depots. Both types of vehicles deliver goods to customers; UAVs are dispatched from trucks while en route to make the last-mile delivery. A metaheuristic algorithm based on the Ant Colony Optimization (ACO) principle is proposed as the solution. This algorithm has been adapted for this newly proposed problem; the novel mechanics include the probabilistic decision to dispatch an UAV, the selection of a customer to be served, and local search optimization. Extensive computational experiments are performed to verify the proposed algorithm. First, its performance is compared with Adaptive Large Neighborhood Search (ALNS) metaheuristics on a set of Vehicle Routing Problem with Drones (VRP-D) benchmarks. A set of various benchmark instances are subsequently proposed for the newly formulated MDVRP-D (differing in complexity and graph topology). Finally, the behavior of the proposed algorithm is thoroughly analyzed, especially in respect of features connected with UAVs. The findings presented in this article provide valuable contributions to the NP-hard models related to the Travelling Salesman Problem (TSP) and to the very popular ACO-based algorithms.