Two-Level Algorithm for the UAV Routing Problem with Moving Targets

Introduction. UAV routing problems gain relevance considering expanding uses in the defense industry. Contrary to the civil aviation with static depots and end users, the problems arising in defense require drone routing with moving targets. The theory of differential games has extensively studied the problems related to pursuit of dynamic targets in the general case, but the resulting solutions are difficult to apply in practical scenarios. Hence combinatorial methods are needed for simplified practical models. In particular, we consider all targets to be moving with a constant velocity vector. This article proposes a two-level algorithm for the problem of routing a group of UAVs with moving targets. We compare different clustering methods, including clustering by position, velocity, and a combined approach. The purpose of the article is to show the superiority of a two-level algorithm over the classical algorithm in solution quality under certain conditions. Additionally, we establish the necessity of the combined clustering methods in the general case and predict a correspondence between optimal clustering methods and practical routing scenarios. Results. We established that a two-level algorithm is better than the original algorithm under clustering conditions. We developed software that can be used to solve instances of the UAVRP with moving targets. Conclusions. A two-level algorithm improves the process of routing a group of UAVs in pursuit of a group of moving targets. A combined clustering strategy proved superior for total route length minimization. Keywords: unmanned aerial vehicle, drone, route optimization, clustering methods.