Exact and heuristic approaches for maximizing flows in UAV-enabled wireless cellular networks with multi-hop backhauls

Abstract

This paper investigates the problem of data routing in backhaul networks using Unmanned Aerial Vehicles (UAVs) to relay data from Small Cells (SCs) to the core network. The objective is to maximize the total fulfilled demand of data to be routed, while ensuring technical requirements such as hop constraints and edge capacity. The problem is formulated using a compact mixed-integer programming model, which can solve small- and medium-sized topologies. In addition, a fast constructive heuristic based on a maximal tree is developed to solve large-scale topologies, resulting in a significant reduction in CPU time. The quality of the heuristic is evaluated by using column generation for solving the linear programming relaxation of an exponential formulation. The computational study shows the effectiveness and value of the proposed compact model and constructive heuristic for various topology sizes. Furthermore, experiments demonstrate that by keeping the network setup constant and updating the demand vector only, the computational time of the compact model can be drastically reduced for all topology sizes.