2021, випуск 4, c. 12-26

Одержано 11.12.2021; Виправлено 19.12.2021; Прийнято 21.12.2021

Надруковано 30.12.2021; Вперше Online 27.01.2022

https://doi.org/10.34229/2707-451X.21.4.2

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

УДК 519.8

Формалізація проблеми оптимізації місць базування та маршрутів групи БПЛА

Л.Ф. Гуляницький * ORCID ID favicon Big,   О.В. Рибальченко ORCID ID favicon Big

Інститут кібернетики імені В.М. Глушкова НАН України, Київ

* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

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

Мета роботи. Полягає у формалізації задачі маршрутизації БПЛА, розробці її математичної моделі та алгоритмів вирішення, аналізі їх ефективності.

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

Висновки. Розроблена математична модель та алгоритми дозволили отримати рішення, що задовольняють умовам завдання. Розроблені алгоритми порівнювалися з погляду ефективності знайденого рішення та часу обчислення. Змішаний алгоритм з диверсифікованим пошуком показав найкращий результат, але час обчислення збільшився.

 

Ключові слова: маршрутизація, комбінаторна оптимізація, БПЛА, локальний пошук, мурашині алгоритми.

 

Цитувати так: Гуляницький Л.Ф., Рибальченко О.В. Формалізація проблеми оптимізації місць базування та маршрутів групи БПЛА. Cybernetics and Computer Technologies. 2021. 4. С. 12–26. https://doi.org/10.34229/2707-451X.21.4.2

 

Список літератури

           1.     Ramos T.R.P, Gomes M.I., Povoa, A.P.B. Multi-depot vehicle routing problem: a comparative study of alternative formulations. International Journal of Logistics Research and Applications. Jun, 2019. P. 103–120. https://doi.org/10.1080/13675567.2019.1630374

           2.     Bezerra S.N., Souza S.R., Souza M.J.F. A GVNS Algorithm for Solving the Multi-depot Vehicle Routing Problem. Electronic Notes in Discrete Mathematics. 2018. 66. P. 167–174. https://doi.org/10.1016/j.endm.2018.03.022

           3.     Nucamendi-Guillen S., Padilla A.G., Olivares-Benitez E. et al. The multi-depot open location routing problem with a heterogeneous fixed fleet. Expert Systems with Applications. 2020. 165. 113846. https://doi.org/10.1016/j.eswa.2020.113846

           4.     Horbulin V.P., Hulianytskyi L.F., Sergienko I.V. Optimization of UAV Team Routes in the Presence of Alternative and Dynamic Depots. Cybernetics and Systems Analysis. 2020. 56 (2). P. 195–203. https://doi.org/10.1007/s10559-020-00235-8

           5.     Гуляницький Л.Ф., Рибальченко О.В. Формалізація та розв'язування одного типу задач маршрутизації БПЛА. Теорія оптимальних рішень. 2018. 17. С. 107–114. http://dspace.nbuv.gov.ua/handle/123456789/144979

           6.     Liu Y., Liu Z., Shi J., Wu G., Chen C. Optimization of Base Location and Patrol Routes for Unmanned Aerial Vehicles in Border Intelligence, Surveillance, and Reconnaissance. Hindawi Journal of Advanced Transportation. Volume 2019. Article ID 9063232. 13 p. https://doi.org/10.1155/2019/9063232

           7.     Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации. К.: Наук. думка, 1988.

           8.     Гуляницький Л.Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. К.: Видавничо-поліграфічний центр "Київський університет", 2016. 142 с.

           9.     Dorigo M., Stützle T. Ant Colony Optimization: Overview and Recent Advances. Handbook of metaheuristics. Cham: Springer, 2019. P. 311–352. https://doi.org/10.1007/978-3-319-91086-4_10

       10.     Dorigo M., Stutzle T. Ant Colony Optimization. MIT Press, Cambridge. 2004. https://doi.org/10.7551/mitpress/1290.001.0001

       11.     Stützle T., Hoos H.H. MAX-MIN ant system. Future Generation Computer Systems. 2000. P. 889 – 914. https://doi.org/10.1016/S0167-739X(00)00043-1

       12.     Гуляницький Л.Ф. Диверсифікація пошуку в алгоритмах оптимізації мурашиними колоніями. Теорія оптимальних рішень. 2017. 16. С. 47–57. http://dspace.nbuv.gov.ua/handle/123456789/131437

       13.     Бібліотека TSPLIB. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (звернення: 14.12.2021)

       14.     Гуляницький Л.Ф. Алгоритми ОМК з диверсифікованим пошуком. Міжн. наук. симпозіум "Інтелектуальні рішення". Теорія прийняття рішень: мат. ІХ Міжн. шк.-сем. (Ужгород, 15-20 квітня 2019 р.). Ужгород: УжНУ, 2019. С. 1721.

       15.     Mora A.M., García-Sánchez P., Merelo J.J. Pareto-based multi-colony multi-objective ant colony optimization algorithms: an island model proposal. Soft Computing. 2013. 17. Р. 1175. https://doi.org/10.1007/s00500-013-0993-y

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

 

 

© Вебсайт та оформлення. 2019-2021,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.