Optimization of fleet search on network of regions

Unmanned Aerial Vehicles (UAVs) are widely used in modern military missions, primarily for surveillance, reconnaissance, search and detection, and air-to-ground strikes. The widespread use of UAVs in recent conflicts, such as the Russia-Ukraine war, once again highlighted their growing strategic importance. The complexity of military missions carried out by UAVs, coupled with the need for autonomous and coordinated fleet operations, requires analytical approaches to optimize deployment planning and improve operational efficiency. In this study, we address a UAV deployment planning problem for search and detection missions, in which a homogeneous fleet of UAVs is tasked with searching for hostile assets across a network of disjoint regions. Each region is characterized by an a priori probability of target presence, a search difficulty factor which affects the probability of detection, and known inter-region distances. For this purpose, we first develop a mixed-integer nonlinear programming formulation which determines the base locations of UAVs, allocates the limited search time across regions, and sequences the visits to maximize the total time-weighted detection probability mass to achieve the highest probability as much and as early as possible during the operation. Next, we apply a tangent line approximation technique to reformulate the model as a mixed-integer linear programming problem, which we solve using commercial off-the-shelf solvers. We then propose a hybrid heuristic approach based on the ant colony optimization method to generate high-quality solutions. Our computational experiments reveal that the proposed heuristic significantly reduces solution time while maintaining superior performance compared to the linear approximation model.