OPTIMIZATION OF THE UAV ROUTE FOR MAXIMUM COVERAGE OF OBSERVATION OBJECTS TAKING INTO ACCOUNT RANGE LIMITATIONS

DOI: 10.31673/2412-4338.2026.019006

Abstract

The technological development of unmanned aerial vehicles (UAVs) has led to their widespread implementation in engineering management, infrastructure monitoring, construction, environmental supervision and other applied fields. The use of UAVs allows to increase the efficiency of inspections, reduce risks for personnel and provide access to hard-to-reach or dangerous objects, which makes such systems a competitive alternative to traditional inspection methods.

The article considers the problem of planning the route of an unmanned aerial vehicle (UAV) for inspection of objects taking into account flight length restrictions. The aim of the study is to maximize the number of inspected objects during the movement of the UAV between two given basing points.

A mathematical formulation of the problem is proposed, which takes into account the coordinates of objects, individual observation radii and the maximum length of the route. A feature of the proposed mathematical formulation is the consideration of the possibility of remote inspection by building a coverage area. UAV route planning problems with surveying a set of objects belong to the class of NP-hard. In this regard, heuristic and metaheuristic approaches are widely used in practical applications, in particular greedy algorithms, genetic and evolutionary methods, and hybrid strategies. Each of these approaches has its own advantages and limitations, which necessitates a well-founded choice of method for a specific applied problem.

Two approaches are implemented to solve the optimization problem: a greedy algorithm and an evolutionary optimization method. To build algorithms, we consider dividing the area with objects into a grid, through the nodes of which the route is laid.

The greedy algorithm is implemented according to the principle of iteratively adding a new segment to the existing route through the excluded objects of study. For the evolutionary algorithm, crossover, mutation, and crossing functions are constructed.

The algorithms are compared on different grids and under different conditions. It is shown that the greedy algorithm provides a fast approximate solution, while the evolutionary algorithm allows to improve the quality of the obtained solution, but requires additional time costs.

Keywords: unmanned aerial vehicle, routing problem, route optimization with length constraint, greedy algorithms, evolutionary algorithms

References

1. Hulyanytskyi L., Storchevyi V. Optimization of routes for a group of UAVs using a modified ant colony algorithm. Computer Mathematics. 2019. Issue 1. pp. 85–93. URL: http://nbuv.gov.ua/UJRN/Koma_2019_1_13
2. Dorigo M., Di Caro G. Ant colony optimization: a new meta-heuristic. Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), Washington, DC, USA, 1999, pp. 1470-1477 Vol. 2, URL:  doi: 10.1109/CEC.1999.782657.
3. Zhuravska I. Generation of suboptimal routes of an unmanned aerial vehicle using a Hopfield neural network. Problems of Information Technologies. 2018. No. 1. pp. 181–185.
4. Dudko M., Koroliuk N., Openko P. Generalized algorithm for planning the reconnaissance flight route of an unmanned aerial vehicle using fuzzy logic systems. Systems of Arms and Military Equipment. 2021. No. 2(66). pp. 44–50. https://doi.org/10.30748/soivt.2021.66.06
5. Jeong H.Y, Lee S. Drone routing problem with truck: Optimization and quantitative analysis. Expert Systems with Applications. 2023. 227. 120260. https://doi.org/10.1016/j.eswa.2023.120260
6. Pehlivanoglu V. Y., Pehlivanoglu P. An enhanced genetic algorithm for path planning of autonomous UAV in target coverage problems. Applied Soft Computing, 2021. Volume 112. 107796. https://doi.org/10.1016/j.asoc.2021.107796.
7. Debnath D., Vanegas F., Sandino J., Hawary A.F., Gonzalez F. A Review of UAV Path-Planning Algorithms and Obstacle Avoidance Methods for Remote Sensing Applications. Remote Sens. 2024, 16, 4019. https://doi.org/10.3390/rs16214019
8. Jeong H.Y, Lee S. Drone routing problem with truck: Optimization and quantitative analysis. Expert Systems with Ap-plications. 2023. 227. 120260. https://doi.org/10.1016/j.eswa.2023.120260
9. Tamke F., Buscher U. The Vehicle Routing Problem with Drones and Drone Speed Selection. Computers & Operations Research. 2023. 152. 106112. https://doi.org/10.1016/j.cor.2022.106112
10. Zhang, F.; Liu, H. Path Planning Methodologies for UAV Navigation. J. Robot. Autom. 2023, 29, 12–25 
11. Gugan G., Haque A. Path Planning for Autonomous Drones: Challenges and Future Directions. Drones. 2023. 7. 169. URL: https://doi.org/10.3390/drones7030169