Abstract

The utilization of unmanned aerial vehicles (UAVs) has garnered increasing interest across various disciplines. The idea of smart cities led to the exploration of using UAVs in the public service industry, with a focus on integrating all aspects of the system through information and physical items. In this paper, we introduce and model the operational problem of using UAVs to construct an emergency wireless network in a disaster situation using the set covering approach. Unique to our study is the consideration that UAVs do not require predetermined positioning or altitude specifications. Consequently, the problem described in this paper can be classified as a planar variable radius covering problem, which involves a nonconvex continuous relaxation feasible set. We introduce the application of the Dantzig–Wolfe decomposition alongside a branch-and-price algorithm to tackle this problem. Additionally, the pricing subproblem’s solvable equivalent formulation is ingeniously derived from existing theories on the minimum covering circle. For large-scale instances, we propose a heuristic derived from an extended formulation. Comparative computational experiments demonstrate that our proposed algorithms significantly surpass the efficiency of the benchmark genetic algorithm previously reported in the literature.