Greedy Backbone Matheuristics for Hierarchical Functional Connected Dominating Sets in Heterogeneous Drone Networks

This paper studies hierarchical functional drone deployment in disaster-response networks through the Hierarchical Functional Connected Dominating Set (HF-CDS) problem. The problem jointly determines active drone locations, a connected backbone of dominant drones, functionality assignments, and hierarchical authorization links between dominant and non-dominant drones. We introduce two HF-CDS variants with global functionality requirements imposed over the entire network and the same feasible structure but different design goals: a cost-minimizing model and a load-balanced model that penalizes excessive concentration of non-dominant drones around a single dominant drone. From a theoretical perspective, we establish the NP-hardness of the proposed variants and discuss structural properties related to connected domination, hierarchical containment, and backbone load. The main algorithmic contribution is an adaptive greedy backbone matheuristic that first constructs candidate connected dominating backbones using multiple greedy rules and then solves a reduced mixed-integer programming model with the backbone fixed. This design separates the combinatorial backbone-construction task from the functional activation and assignment decisions, enabling the generation of high-quality, feasible solutions with lower computational effort. Computational experiments on connected geometric graphs compare exact formulations with proposed matheuristic variants, analyzing solution quality, runtime, backbone size, and the trade-off between deployment cost and hierarchical load balancing. The results show that the proposed approach provides a scalable optimization framework for functional and connected heterogeneous drone networks.