E²VRP-CPP: An Energy-Efficient Approach for Multi-UAV Multi-Region Coverage Path Planning Optimization in the Enhanced Vehicle Routing Problem

Unmanned Aerial Vehicles (UAVs) are widely used in applications such as land assessment, surveillance, and rescue operations, where they are often required to cover multiple disjoint regions. Coverage Path Planning (CPP) aims to determine optimal paths for UAVs to cover these areas. While CPP for single regions has been extensively studied, multi-region CPP with multiple UAVs remains underexplored. Existing methods typically focus on minimizing path length, but often neglect the nonlinear variations in energy consumption during flight, limiting their practical applicability. This paper addresses the multi-UAV, multi-region CPP as a variant of the Vehicle Routing Problem (VRP) with energy estimation. We propose an approach that optimizes UAV flight speeds to minimize energy consumption, supported by an accurate energy estimation algorithm. In addition, a heuristic algorithm is developed to balance the distribution of tasks among UAVs, considering both the scanning and transit times. Experiments using real-world data from the Changsha urban area demonstrate that our approach outperforms state-of-the-art methods in computational efficiency and energy savings, highlighting its potential for practical UAV deployment.