Routing of cargo unmanned aerial vehicles in remote areas. Part 1

A serious problem in the Russian Arctic, which can be solved through the use of unmanned aerial vehicles (UAVs) given the lack of year-round road access, remains the delivery of goods and the patrolling of forests to identify and monitor the development of wild fires. This article is devoted to the development of methods for optimal forest area patrol route plotting based on solving a generalized traveling salesman problem (GTSP) with precedence constraints. The implementation of route optimization methods is based on dynamic programming combined with a special decomposition-based framework for two variants of cost aggregation: additive and a variant corresponding to a minimax formulation; the mentioned approach allows for finding a compositional extremum in a fully acceptable time for a “two-cluster” (in terms of decomposition) problem. The first part of this article explores the possibilities of its application in model tasks focused on the problems in general aviation, as the first step in building methods and algorithms for solving practical UAV route optimization problems, which are of interest for organizing air transport operations in the Arctic Zone and for radical improvement wild fire monitoring. The research results showed that using dynamic programming to solve a problem with an additive criterion, complicated by a precedence constraint, requires significant time costs—in the model variant, the computation time was 29 hours, 24 minutes, and 49 seconds. Therefore, the second part of the article will consider a variant for solving the additive problem by setting the initial and final tasks, where the object of study will be a compositional mathematical programming (MP) model.