A Greedy and Variable Neighborhood Search Metaheuristic Approach for the Cumulative Unmanned Aerial Vehicle Routing Problem

The Cumulative Unmanned Aerial Vehicle Routing Problem (CUAVRP) has been proposed for addressing operations in which an area of interest needs to be covered using a fleet of drones with the minimum possible latency. Transforming the underlying coverage path planning problem into a vehicle routing problem allows for different objectives and constraints to be considered in the model. The CUAVRP uses the Cumulative Capacitated Vehicle Routing Problem cost model, which focuses on minimizing the sum of arrival times at all points of the area of interest. Thus, the CUAVRP is well-suited for search and rescue UAV missions, where latency is the most prominent indicator of success. In this paper, a Greedy and Variable Neighborhood Search (GnVNS) metaheuristic algorithm is implemented by combining greedy destroy-repair operators with VNS. Two variants of the destroy operator are implemented and tested on the 25 CUAVRP benchmark instances from the literature. Both GnVNS variants were able to match 9 previously published best-known values and provided new best solutions for multiple instances.