A Sub-Mother UAV Swarm Deployment and Routing for Power Grid Emergency Communication

Abstract

This paper investigates the coordinated deployment and routing of communication equipment by a Sub-mother UAV swarm in power-grid emergency communication scenarios. Considering mission timeliness and payload constraints, a heterogeneous MUAV–SUAV coordinated deployment-and-routing model is established to minimize the total system cost, including platform flight cost, SUAV activation cost, and penalty cost caused by delayed deployment. To solve this problem, a two-stage optimization framework is proposed. In the first stage, an improved K-means clustering algorithm with neighborhood search (K-means-NS) is developed to divide deployment points into feasible sub-regions while satisfying SUAV endurance constraints and maintaining the deployment–retrieval payload balance required by the MUAV. In the second stage, the MUAV inter-region visiting sequence is treated as a routing subproblem, and an improved adaptive genetic algorithm (IAGA) is designed to optimize the coordinated routes of the MUAV and SUAVs within each sub-region. The IAGA adopts hybrid encoding, feasible-solution adjustment, elitist selection, and adaptive crossover–mutation operations to improve search efficiency under complex constraints. Numerical experiments on small-, medium-, and large-scale scenarios show that the proposed method can generate feasible sub-region divisions and coordinated routing schemes. Compared with GA and G-PSHA, IAGA reduces the total flight cost by approximately 21.2%, 10.5%, and 23.2% relative to GA and by approximately 0.2%, 2.5%, and 8.1% relative to G-PSHA in the three scenarios, respectively. Sensitivity analysis further indicates that stricter mission-timeliness requirements increase penalty costs, highlighting the importance of timely communication-device deployment in emergency restoration.