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 new 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Optimizing the Number of Drones for Aerial Power-Line Maintenance

  • Francesco Betti Sorbelli,
  • Sajjad Ghobadi,
  • Lorenzo Palazzetti,
  • Cristina M. Pinotti

摘要

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 new 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.