Одна спецiальна задача маршрутизацiї БПЛА
DOI:
https://doi.org/10.24144/2616-7700.2019.1(34).69-78Ключові слова:
безпiлотнi лiтальнi апарати, оптимiзацiя маршруту, мультидепо, математична модель, комбiнаторна оптимiзацiя, мурашина системаАнотація
Метою статтi є огляд задач маршрутизацiї транспортних засобiв, їх класифiкацiя, а також розгляд проблеми маршрутизацiї групи безпiлотних лiтальних апаратiв (БПЛА) при обстеженнi заданих об’єктiв. Запропонована математична модель проблем, якi полягають в тому, що перед заданою групою лiтальних апаратiв, якi можуть стартувати з рiзних точок пуску i повиннi закiнчувати маршрут у спецiальних зонах приймання, що мають певну ємкiсть, стоїть завдання облетiти ряд заданих об’єктiв (точок на мiсцевостi) з мiнiмiзацiєю сумарної довжини маршрутiв або тривалостi польотiв за умови, що кожен об’єкт вiдвiдується одним i тiльки одним БПЛА i всi об’єкти повиннi бути вiдвiданими. Показано, що модель руху транспортних засобiв з декiлькома депо можна адаптувати для планування польоту групи БПЛА в рядi задач обстеження. Пропонуються алгоритми розв’язування: повний перебiр розв’язкiв, гiбридний локальний пошук – табуйований пошук iз використанням жадiбного алгоритму для побудови початкового маршруту, макс-мiн алгоритм мурашиних систем MMAS. Оскiльки у вiдкритому доступi немає бiблiотек даних для сформульованих постановок задач, то був згенерований набiр задач за допомогою системи Google Maps API, що дало змогу отримати задачi, якi наближенi до реальностi (використанi координати сiл, селищ, мiст). Задачi мають рiзну кiлькiсть обстежуваних об’єктiв, лiтальних засобiв, початкових та кiнцевих депо. Для кожного з алгоритму був здiйснений пiдбiр параметрiв i потiм проведений обчислюваний експеримент, який дозволив порiвняти три розробленi алгоритми розв’язування задачi маршрутизацiї групи БПЛА. У результатi визначено, що метод прямого перебору можна застосувати лише до задач дуже малої розмiрностi, при цьому потрiбно багато часу на виконання алгоритму. Локальний пошук знаходив покращенi розв’язки на задачах середньої розмiрностi, а макс-мiн алгоритм мурашиних систем MMAS показав себе найкраще на задачах великої розмiрностi, тому вiн i визначений як перспективний для дослiдження. Визначено подальший напрямок покращення макс-мiнного алгоритму мурашиних систем шляхом використання принципiв диверсифiкацiї пошуку в них.Посилання
- Dantzig, G. B., & Ramser, J. H. (1959). The truck dispatching problem. Management Science, 6(1), 80–91.
- Baldacci, R., Toth, P., & Vigo, D. (2010). Exact algorithms for routing problems under vehicle capacity constraints. Annals of Operations Research, 175 (1), 213–245.
- Hulianytskyi, L.F. (2007). Problema optimizatsii marshrutov transportnykh sredstv s vremennymi oknami. Computer Mathematics, 1, 122–132 [in Russian].
- Montoya-Torres, J. R., L´opez Franco, J., & Nieto Isaza, S. (2015). A literature review on the vehicle routing problem with multiple depots. Computers & Industrial Engineering, 79, 115–129.
- Golden, B. L., Raghavan, S., & Wasil, E. A. (Eds.). (2008). The vehicle routing problem: latest advances and new challenges. Springer Science & Business Media , 43.
- Ponda, S. S., Johnson, L. B., & Geramifard, A. (2015). Cooperative mission planning for multiUAV teams. In: Handbook of Unmanned Aerial Vehicles. Dordrecht: Springer, 1447–1490.
- Liu, Y., Liu, Z., & Shi, J. (2019). Optimization of base location and patrol routes for unmanned aerial vehicles in border intelligence, surveillance, and reconnaissance. Journal of Advanced Transportation, 2019, 1–13.
- Renaud, J., Laporte, G., & Boctor, F. F. (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers & Operations Research, 23(3), 229–235.
- Hulianytskyi, L. F. (2019). Rozrobka matematychnoi modeli problemy optymizatsii marshrutiv hrupy BPLA za naiavnosti dekilkokh depo. In Mathematical and simulation modeling of systems, 324–327 [in Ukrainian].
- Horbulin, V. P., Hulianytskyi, L. F., & Serhiienko, I. V. (2019). Postanovky ta matematychni modeli problem optymizatsii marshrutiv litalnykh aparativ iz dynamichnymy depo. Control systems and machines, 1, 2–15 [in Ukrainian].
- Toth, P., & Vigo, D. (2014). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics.
- Austin, R. (2010). Unmanned aircraft systems: UAVS design, development and deployment. Chichester, UK: John Wiley & Sons, Ltd.
- Hulianytskyi, L. F., & Rybalchenko, O. V. (2018). Formalizatsiia ta rozviazuvannia odnoho typu zadach marshrutyzatsii BPLA. The theory of optimal solutions, 17, 107–114 [in Ukrainian].
- Pereira, F. B., & Tavares, J. (2009). Bio-inspired algorithms for the vehicle routing problem. Studies in Computational Intelligence 161, Springer.
- Kohl, N. (1995). Exact methods for time constrained routing and related scheduling problems. PhD thesis, Department of Mathematical Modelling, Technical University of Denmark.
- Soto, M., Sevaux, M., & Rossi, A. (2017). Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem. Computers & Industrial Engineering, 107, 211–222.
- Dorigo, M., & St¨utzle, T. (2019). Ant colony optimization: overview and recent advances. Springer International Publishing AG, 311–352.
- St¨utzle, T., Hoos, H.H. (2000). Ant system. Future Generation Computer Systems, 16(8), 889–914.
- Hulianytskyi, L. F. (2017). Novyi alhorytm optymizatsii murashynymy koloniiamy. Modern informatics: problems, achievements and prospects of development, 41–43 [in Ukrainian].
- Mora, A. M., Garc´ıa-S´anchez, P., & Merelo, J. J. (2013). Pareto-based multi-colony multiobjective ant colony optimization algorithms: an island model proposal. Soft Computing, 7(7), 1175–1207.
##submission.downloads##
Опубліковано
2019-07-02
Як цитувати
Гуляницький, Л. Ф., & Сторчевий, В. В. (2019). Одна спецiальна задача маршрутизацiї БПЛА. Науковий вісник Ужгородського університету. Серія «Математика і інформатика», 1(34), 69–78. https://doi.org/10.24144/2616-7700.2019.1(34).69-78
Номер
Розділ
Iнформатика, комп’ютернi науки та прикладна математика
Ліцензія
Авторське право (c) 2019 Л. Ф. Гуляницький, В. В. Сторчевий
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.