ВДОСКОНАЛЕННЯ АЛГОРИТМУ ПОБУДОВИ ОПТИМАЛЬНОГО МАРШРУТУ З ВИКОРИСТАННЯМ «ГАРЯЧИХ ЗОН»

Анотація

У статті авторами розглянуто вирішення проблеми планування оптимальних маршрутів у динамічному
середовищі з використанням географічних даних OpenStreetMap (OSM) для території України. В умовах
конфліктних ситуацій та ведення бойових дій виникає необхідність адаптації класичних алгоритмів пошуку
маршрутів для врахування специфічних обмежень на місцевості. Основна мета дослідження – розробка
адаптивного алгоритму A*, який враховує наявність зон підвищеного ризику (“гарячих зон”), які можуть значно
вплинути на ефективність та безпечність розрахованого маршруту. Для реалізації поставленої мети був
проведений аналіз існуючих алгоритмів пошуку найкоротшого шляху з використанням класичного алгоритму A*
та його евристичної функції, що враховує відстань між точками маршруту. Розглянута алгоритмічна
особливість модифікації алгоритму A*, що включає врахування додаткового коефіцієнта вартості для "гарячих
зон". Запропонований підхід базується на додаванні адаптивного множника, який обмежує можливість
прокладання маршруту через небезпечні ділянки. Для перевірки запропонованого методу було використано OSMдані, що містять лише базову інформацію про дороги без врахування воєнних обмежень. Це обмеження
підкреслює важливість додаткового аналізу таких факторів, як безпека та ризик при плануванні маршруту.
Отримані результати показують ефективність розробленого адаптивного алгоритму A* для задачі побудови
маршруту в умовах динамічного середовища, зокрема з можливістю уникнення небезпечних зон ("гарячих зон").
Висновки проведеного дослідження підтверджують, що додатковий коефіцієнт вартості у "гарячих зонах"
покращує точність маршруту та підвищує безпеку пересування. Розроблений алгоритм може застосовуватися
для автоматизованого планування маршрутів у ситуаціях, де критично важливо враховувати змінні фактори
ризику та специфічні умови на місцевості.

Посилання:

1. OpenStreetMap // [Електронний ресурс]. 29.10.2024. URL: https://uk.wikipedia.org/wiki/
   OpenStreetMap.
   2. Ваврук Є. Я., Мозіль З. Г. Вибір алгоритму пошуку оптимального шляху передавання даних
   у розподіленій системі. 2018 URL: https://science.lpnu.ua/sites/default/files/journal-paper/2019/sep/
   18542/182073vis905ksmzvichniy-42-48.pdf.
   3. Бульба C. C., Соловйова О. І., Семеренко Ю. О. Дослідження алгоритмів пошуку
   оптимального шляху 19.04.2024. URL: https://doi.org/10.26906/SUNZ.2024.2.067.
   4. Hybrid A* path search with resource constraints and dynamic obstacles. Secyrity Intelligent
   Aerospace Systems / Alán Cortez and oth. 25 January 2023. Vol. 1. URL: https://doi.org/10.3389/
   fpace.2022.1076271.
   5. Бартіш М. Я., Дудзяний І. М. Дослідження операцій. Частина 2. Алгоритми оптимізації на
   графах: Підручник. Львів: Видавничий центр ЛНУ ім. Івана Франка, 2007. 120 с.
   6. Comparison of optimal path finding techniques for minimal diagnosis in mapping repair.
   International Conference on Data and Software Engineering (ICoDSE) / Inne Gartina Husein*, Saiful Akbar,
   Benhard Sitohang, Fazat Nur Azizah. 2017. URL: http://dx.doi.org/10.1109/ICODSE.2017.8285853.
   7. Analysis of Dijkstra’s Algorithm and A* Algorithm in Shortest Path Problem. Journal of Physics:
   Conference Series / Dian Rachmawati1 and Lysander Gustin. 2019. URL: https://doi.org/10.1088/1742-
   6596/1566/1/012061.
   8. Трохимчук Р. М. Теорія графів. Навчальний посібник для студентів факультету кібернетики /
   Р. М. Трохимчук. К.: РВЦ «Київський університет», 1998. 43 с.
   9. Шевцов М. В., Ніколюк П. К. Порівняння різних евристичних функцій в алгоритмі А*
   18.07.2023. URL: https://jait.donnu.edu.ua/article/view/14012.
   10. Change Detection from Remote Sensing to Guide OpenStreetMap Labeling / Conrad M. Albrecht
   and oth. 2020. Journal: ISPRS Int. J. Geo-Inf. Vol. 9. Num. 427. URL: https://doi.org/10.3390/ijgi9070427