ОПТИМІЗАЦІЯ МАРШРУТУ БПЛА ДЛЯ МАКСИМАЛЬНОГО ПОКРИТТЯ ОБ'ЄКТІВ СПОСТЕРЕЖЕННЯ З УРАХУВАННЯМ ОБМЕЖЕНЬ НА ДАЛЬНІСТЬ

DOI: 10.31673/2412-4338.2026.019006

Анотація

Технологічний розвиток безпілотних літальних апаратів (БПЛА) зумовив їх широке впровадження в інженерному менеджменті, моніторингу інфраструктури, будівництві, екологічному нагляді та інших прикладних галузях. Застосування БПЛА дозволяє підвищити ефективність обстежень, зменшити ризики для персоналу та забезпечити доступ до важкодоступних або небезпечних об’єктів, що робить такі системи конкурентною альтернативою традиційним методам інспекції. 

У статті розглядається задача планування маршруту безпілотного літального апарата (БПЛА) для обстеження об’єктів з урахуванням обмежень на довжину польоту. Метою дослідження є максимізація кількості обстежених об’єктів під час переміщення БПЛА між двома заданими точками базування. 

Запропоновано математичну постановку задачі, що враховує координати об’єктів, індивідуальні радіуси спостереження та граничну довжину маршруту. Особливістю запропонованої математичної постановки є врахування можливості віддаленого обстеження за рахунок вибудовування області покриття. Задачі планування маршруту БПЛА з обстеженням множини об’єктів належать до класу NP-складних. У зв’язку з цим у практичних застосуваннях широко використовуються евристичні та метаевристичні підходи, зокрема жадібні алгоритми, генетичні та еволюційні методи, гібридні стратегії. Кожен із цих підходів має власні переваги та обмеження, що зумовлює необхідність обґрунтованого вибору методу для конкретної прикладної задачі.

Для розв’язання задачі оптимізації реалізовано два підходи: жадібний алгоритм і еволюційний метод оптимізації. Для побудови алгоритмів розглядається розбиття області з об’єктами на сітку, через вузли якої прокладається маршрут.

Жадібний алгоритм реалізований за принципом ітеративного додавання до існуючого маршруту нового відрізка через невключені об’єкти дослідження. Для еволюційного алгоритму побудовані функції кросовера, мутації та схрещування.

Здійснено порівняння алгоритмів на різних сітках та за різними умовами. Показано, що жадібний алгоритм забезпечує отримання швидкого наближеного рішення, а еволюційний алгоритм дозволяє підвищити якість отриманого рішення, але потребує додаткових часових витрат.

Ключові слова: безпілотний літальний апарат, задача маршрутизації, оптимізація маршрутів з обмеженням на довжину, жадібні алгоритми, еволюційні алгоритми

Список використаних джерел

1. Гуляницький Л. Ф., Сторчевий В. В. Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем. Комп’ютерна математика. 2019. Вип. 1. С. 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. Журавська І.М. Генерація субоптимальних маршрутів безпілотного літального апарата з використанням нейронної мережі Хопфілда. Проблеми інформаційних технологій.  2018. № 1. С. 181-185
4. Дудко М.В., Королюк Н.О., Опенько П.В. Узагальнений алгоритм планування маршруту розвідувального польоту безпілотного літального апарату із використанням нечітких логічних систем. Системи озброєння і військова техніка. 2021. № 2(66). C. 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