УДК 519.8
ОПТИМИЗАЦИЯ МАРШРУТОВ КОМАНДЫ БПЛА ПРИ НАЛИЧИИ АЛЬТЕРНАТИВНЫХ
И ДИНАМИЧЕСКИХ ДЕПО
Аннотация. Предложены содержательная постановка и математические модели проблем оптимизации маршрутов команды беспилотных летательных аппаратов (БПЛА) при обследовании или обслуживании заданного множества объектов при наличии альтернативных и динамических депо (мест старта и/или приземления) и ресурсных ограничений. К таким задачам, в частности, относятся проблемы планирования полетов БПЛА, использующих движущие платформы в качестве депо. Критериями оптимизации являются как суммарная длина маршрутов, так и количество задействованных БПЛА. Разработаны и реализованы алгоритмы решения сформулированных задач комбинаторной оптимизации, основанные на оптимизации муравьиными колониями, табу поиске и полном переборе. Представлены результаты вычислительного эксперимента.
Ключевые слова: оптимизация маршрутов, БПЛА, муравьиные алгоритмы, динамические депо, табу поиск, гремлины.
ПОЛНЫЙ ТЕКСТ
Горбулін Володимир Павлович,
академік НАН України, професор, перший віце-президент НАН України, Київ,
horbulin@nas.gov.ua
Гуляницький Леонід Федорович,
доктор техн. наук, завідувач відділу Інституту кібернетики ім. В.М. Глушкова НАН України, Київ,
leonhul.icyb@gmail.com
Сергієнко Іван Васильович,
академік НАН України, професор, директор Інституту кібернетики ім. В.М. Глушкова НАН України, Київ,
incyb@incyb.kiev.ua
СПИСОК ЛИТЕРАТУРЫ
- Ponda S.S., Johnson L.B., Geramifard A., How J.P. Cooperative mission planning for multi-UAV teams. In: Valavanis K., Vachtsevanos G. (Eds). Handbook of Unmanned Aerial Vehicles. Dordrecht: Springer, 2015. P. 1447–1490.
- Otto A., Agatz N., Campbell J., Golden B., Pesch E. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey. Networks. 2018. Vol. 72, Iss. 4. P. 411–458.
- Горбулін В.П. Забезпечення оборони та безпеки України: актуальні проблеми і шляхи їх вирішення. Вісн. НАН України. 2019. № 9. С. 3–18.
- Coutinho W.P., Battarra M., Fliege J. The unmanned aerial vehicle routing and trajectory optimisation problem, a taxonomic review. Computers & Industrial Engineering. 2018. Vol. 120. P. 116–128.
- Zhao Y., Zheng Z., Liu Y. Survey on computational-intelligence-based UAV path planning. Knowledge-Based Systems. 2018. Vol. 158. P. 54–64.
- Гуляницький Л.Ф., Рибальченко О.В. Формалізація та розв’язування одного типу задач маршрутизації БПЛА. Теорія оптимальних рішень. 2018. № 17. С. 107–114.
- Perez-Carabaza S., Besada-Portas E., Lopez-Orozco J.A., Jesus M. Ant colony optimization for multi-UAV minimum time search in uncertain domains. Applied Soft Computing. 2018. Vol. 62. P. 789–806.
- Cekmez U., Ozsiginan M., Sahingoz O.K. Multi-UAV path planning with multi colony ant optimization. In: International Conference on Intelligent Systems Design and Applications (2017, December). Cham: Springer, 2017. P. 407–417.
- Chiang W.C., Li Y., Shang J., Urban T.L. Impact of drone delivery on sustainability and cost: Realizing the UAV potential through vehicle routing optimization. Applied Energy. 2019. Vol. 242. P. 1164–1175.
- Binol H., Bulut E., Akkaya K., Guvenc I. Time optimal multi-UAV path planning for gathering ITS data from roadside units. In: 88th Vehicular Technology Conference (VTC-Fall) (2018, August). IEEE, 2018. P. 1–5.
- Xu C., Duan H., Liu F. Chaotic artificial bee colony approach to uninhabited combat air vehicle (UCAV) path planning. Aerospace Science and Technology. 2010. Vol. 14, Iss. 8. P. 535–541.
- Tian G., Zhang L., Bai X., Wang B. Real-time dynamic track planning of multi-UAV formation based on improved artificial bee colony algorithm. In: 37th Chinese Control Conference (CCC) (2018, July). IEEE, 2018. P. 10055–10060.
- Shakhatreh H., Khreishah A., Alsarhan A., Khalil I., Sawalmeh A., Othman, N.S. Efficient 3D placement of a UAV using particle swarm optimization. In: 8th International Conference on Information and Communication Systems (ICICS) (2017, April). IEEE, 2017. P. 258–263.
- Austin R. Unmanned aircraft systems. UAVs design, development and deployment. West Sussex: John Wiley and Sons, 2010. 365 p.
- Tsourdos A., White B., Shanmugavel M. Cooperative path planning of unmanned aerial vehicles. West Sussex: John Wiley and Sons, 2011. 212 p.
- Shima T., Rasmussen S. UAV cooperative decision and control. Challenges and practical approaches. Philadelphia: SIAM, 2009. 186 p.
- Toth P., Vigo D. (Eds.). Vehicle routing: problems, methods, and applications. Philadelpia: SIAM, 2014. 462 p.
- Braekers K., Ramaekers K., Nieuwenhuyse I.V. The vehicle routing problem: State of the art classification and review. Computers & Industrial Engineering. 2016. Vol. 99. P. 300–313.
- Karakati S., Podgorelec V. A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing. 2015. Vol. 27. P. 519–532.
- Soto M., Sevaux M., Rossi A., Reinholz A. Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem. Computers & Industrial Engineering. 2017. Vol. 107. P. 211–222.
- Горбулін В.П., Гуляницький Л.Ф., Сергієнко І.В. Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів із динамічними депо. Управляющие системы и машины. 2019. № 1. С. 3–10.
- Husseini T. Gremlins are coming: DARPA enters Phase III of its UAV programme. Army Technology, 3 July 2018. URL: https://www.army-technology.com/features/gremlins-darpa-uav-programme/.
- Гуляницкий Л.Ф. Проблема оптимизации маршрутов транспортных средств с временными окнами. Компьютерная математика. 2007. № 1. C. 122–132.
- Андерсон Дж. Дискретная математика и комбинаторика. Москва; СПб; Киев: ИД «Вильямс», 2003. 957 с.
- Dorigo M., Sttzle T. Ant colony optimization: Overview and recent advances. In: Handbook of Metaheuristics. Cham: Springer, 2019. P. 311–352.
- Sttzle T., Hoos H.H MAX-MIN ant system. Future Generation Computer Systems. 2000. Vol. 16, Iss. 8. P. 889–914.
- Гуляницький Л.Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації. Київ: ВПЦ «Київський університет», 2016. 142 с.
- Гуляницький Л.Ф. Новий алгоритм оптимізації мурашиними колоніями. Сучасна інформатика: проблеми, досягнення та перспективи розвитку: Пр. Міжн. конф., присвяченої 60-річчю заснування ІК ім. В.М. Глушкова НАН України (Київ, 13–15 грудня 2017 р.). Київ: Ін-т кібернетики ім. В.М. Глушкова НАН України, 2017. С. 41–43.
- Mora A.M., GarcЗa-Sїnchez P., Merelo J.J., Castillo P.A. Pareto-based multi-colony multi-objective ant colony optimization algorithms: an island model proposal. Soft Computing. 2013. Vol. 17, Iss. 7. Р. 1175.–1207.