Optimizing the Number of Drones for Aerial Power-Line Maintenance

Unmanned Aerial Vehicles (UAVs) are increasingly used in critical infrastructure maintenance due to their ability to improve safety, efficiency, and access in challenging environments. This paper focuses on optimizing drone-assisted equipment delivery for high-voltage power line maintenance, with the goal of minimizing the number of drones required to serve all pylons that lie on a line. Unlike prior work that maximizes delivery profit given a fixed fleet size, we aim to minimize the fleet size itself, addressing deployment constraints, such as load and energy, and coordination complexity. We introduce a novel optimization problem, the Minimum Drone Delivery Problem (MDDP), and study three key variants: unitary loads (MDDP-U), arbitrary loads (MDDP-A), and non-overlapping missions (N-MDDP). We formulate MDDP as an Integer Linear Program and prove its NP-hardness. To solve it, we propose polynomial-time approximation algorithms and a heuristic. Extensive evaluations on synthetic datasets demonstrate the effectiveness and scalability of our approaches.