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.

1. Poleshkina, I.O. (2022). Contribution of general aviation to ensuring transport accessibility to the arctic regions: the challenges and areas of focus. Civil Aviation High Technologies, vol. 25, no. 2, pp. 54–69. DOI: 10.26467/2079-0619-2022-25-2-54-69 (in Russian)

2. Garey, M.R., Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Editorial: W.H. Freeman, 340 p.

3. Chentsov, A.G., Chentsov, P.A. (2005). About one problem of work distribution with constraints. In: Matematicheskiy i prikladnoy analiz: sbornik nauchnykh trudov. Tyumen: izdatelstvo Tyumenskogo universiteta, issue 2, pp. 223–237. (in Russian)

4. Chentsov, A.G. (2008). Extremal routing and task allocation problems: Theoretical issues. Moscow–Izhevsk: NITS «Regulyarnaya i khaoticheskaya dinamika», Izhevskiy institut kompyuternykh issledovaniy, 240 p. (in Russian)

5. Melamed, I.I., Sergeev, S.I., Sigal, I.Kh. (1989). The traveling salesman problem. Theoretical issues. Avtomatika i telemekhanika, no. 9, pp. 3–33. (in Russian)

6. Little, J., Murthy, K., Sweeney, D., Carel, K. (1965). An algorithm for solving the traveling salesman problem. Ekonomika i matematicheskiye metody, vol. 1, no. 1, pp. 94–107. (in Russian)

7. Bellman, R. (1964). Application of dynamic programming to the traveling salesman problem. Kiberneticheskiy sbornik, vol. 9, pp. 219–228. (in Russian)

8. Held, M., Karp, R.M. (1964). Application of dynamic programming to ordering problems. Kiberneticheskiy sbornik, vol. 9, pp. 202–218. (in Russian)

9. Gimadi, E.Kh., Khachai, M.Yu. (2016). Extremal problems on sets of permutations. Yekaterinburg: UMC UPI, 220 p. (in Russian)

10. Chentsov, A.G., Chentsov, P.A. (2023). Two-stage dynamic programming in a routing problem with decomposition elements. Avtomatika i telemekhanika, no. 5, pp. 133–164. DOI: 10.31857/S0005231023050070 (in Russian)

11. Chentsov, A.G., Chentsov, P.A. (2025). Dynamic programming and decomposition in extreme routing problems. Proceedings of the institute of mathematics and mechanics Ural branch of RAS, vol. 31, no. 1, pp. 247–272. DOI: 10.21538/0134-4889-2025-31-1-fon-03 (in Russian)

12. Kuratowski, K., Mostowski, A. (1967). Set theory. Amsterdam: North-Holland publishing company, Warszawa: PWN-Polish scientific publishers, 440 p.

13. Dieudonne, J. (1960). Foundations of Modern Analysis. Hesperides Press, 408 p.

14. Cormen, T.H., Leiserson, C.E., Rivest, R.L. (1990). Introduction to algorithms. MIT Press, 1312 p.

15. Warga, J. (1972). Cover for optimal control of differential and functional equations. Elsevier Inc., 531 p. DOI: 10.1016/C2013-0-11669-8

16. Chentsov, A.G. (2014). Problem of successive megalopolis traversal with the precedence conditions. Automation and Remote Control, vol. 75, no. 4, pp. 728–744. DOI: 10.1134/S0005117914040122

17. Chentsov, A.G., Chentsov, A.A. (2015). Route problem with constraints depending on a list of tasks. Doklady Mathematics, vol. 92, no. 3, pp. 685–688. DOI: 10.1134/S1064562415060083

18. Chentsov, A.G., Chentsov, P.A. (2016). Routing under constraints: problem of visit to megalopolises. Automation and Remote Control, vol. 77, no. 11, pp. 1957–1974. DOI: 10.1134/S0005117916110060

19. Chentsov, A.G., Chentsov, A.A. (2022). Dynamic programming and questions of solvability of route bottleneck problem with resource constraints. Bulletin of Udmurt University. Mathematics. Mechanics. Computer Science, vol. 22, no. 4, pp. 569–592. DOI: 10.35634/vm220406 (in Russian)

20. Petunin, A.A., Chentsov, A.G., Chentsov, P.A. (2020). Optimal tool routing for figured sheet cutting machines with numerical control. Mathematical models and algorithms: Monograph. Yekaterinburg: UrFU imeni pervogo Prezidenta Rossii B.N. Yeltsina, 247 p. (in Russian)

21. Chentsov, A.G., Chentsov, P.A. (2024). Some constructions for solving routing problems using decompositions and transformations of target sets. Bulletin of Udmurt University. Mathematics. Mechanics. Computer Science, vol. 34, no. 4, pp. 518–540. DOI: 10.35634/vm240404 (in Russian)

22. Chentsov, A.G. (2023). A bottleneck routing problem with a system of priority tasks. Proceedings of the Institute of Mathematics and Informatics at Udmurt State University, vol. 61, pp. 156–186. DOI: 10.35634/2226-3594-2023-61-09

23. Chentsov, A.G. (2013). To question of routing of works complexes. Bulletin of Udmurt University. Mathematics. Mechanics. Computer Science, no. 1, pp. 59–82. (in Russian)

24. Petunin, А.A. (2009). About some strategies of the programming of tool route by developing of control programs for thermal cutting machines. Vestnik UGATU, vol. 13, no 2, pp. 280–286. (in Russian)

25. Petunin, A.A. (2009). Methodological and theoretical foundations of automation of design of cutting sheet materials on machines with numerical control: D. Tekh. Sc. Thesis. Ekaterinburg: UGTU-UPI, 348 p. (in Russian)

26. Petunin, A.A., Tavaeva, A.F. (2015). Optimization of tool route for cnc shape cutting machines provided that working stroke speed is not constant value. Fundamentalnyye issledovaniya, no. 6-1, pp. 56–62. (in Russian)

27. Tavaeva, A.F., Petunin, A.A. (2018). The accurate calculation of parts treatment cost from sheet metal on the cnc laser cutting machine in problem of tool routing optimization. Modeling, Optimization and Information Technology, vol. 6, no. 4, pp. 298–312. DOI: 10.26102/2310-6018/2018.23.4.022 (in Russian)

28. Ye, J., Chen, Z.G. (2013). An optimized algorithm of numerical cutting-path control in garment manufacturing. Advanced Materials Research, vol. 796, pp. 454–457. DOI: 10.4028/www.scientific.net/AMR.796.454

29. Dewil, R., Vansteenwegen, P., Cattrysse, D. (2014). Construction heuristics for generating tool paths for laser cutters. International Journal of Production Research, vol. 52, issue 20, pp. 5965–5984. DOI: 10.1080/00207543.2014.895064

30. Frolovskiy, V.D. (2005). Automation of design of control programs for thermal cutting of metal on CNC equipment. Informatsionnyye tekhnologii v proyektirovanii i proizvodstve, no. 4, pp. 63–66. (in Russian)

31. Gutin, G., Punnen, A.P. (2002). The traveling salesman problem and its variations. Berlin: Springer, 850 p.

32. Cook, W.J. (2012). In pursuit of the traveling salesman: mathematics at the limits of computation. Princeton University, 228 p.

33. Khachai, D., Sadykov, R., Battaia, O., Khachay, M. (2023). Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm. European Journal of Operational Research, vol. 309, issue 2, pp. 488–505. DOI: 10.1016/j.ejor.2023.01.039

34. Bellman, R., Dreyfus, S. (1965). Applied problems of dynamic programming. Moscow: Nauka, 460 p. (in Russian)

35. Papadimitriou, H., Steiglitz, K. (1985). Combinatorial optimization. Algorithms and complexity. Moscow: Mir, 510 p.