Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2019
Hauptverfasser:	Гуляницький, Л.Ф., Сторчевий, В.В.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Schriftenreihe:	Компьютерная математика
Schlagworte:	Оптимизация вычислений
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/161937
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем / Л.Ф. Гуляницький, В.В. Сторчевий // Компьютерная математика. — 2019. — № 1. — С. 85-93. — Бібліогр.: 17 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-161937
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1619372025-02-10T01:22:12Z Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем Оптимизация маршрутов группы БПЛА модифицированым алгоритмом муравьиных систем Routes optimization of UAV groups by modified ant system algorithm Гуляницький, Л.Ф. Сторчевий, В.В. Оптимизация вычислений Розглянуто проблему маршрутизації групи безпілотних літальних апаратів (БПЛА) при обстеженні заданих об'єктів. Показано, що модель руху транспортних засобів з декількома депо можна використати для планування польоту групи БПЛА. Розроблено спеціальний макс-мін алгоритм мурашиних систем для розв'язування однієї із таких задач маршрутизації з декількома депо. Проведено порівняльний аналіз трьох алгоритмів розв'язування. Рассмотрена проблема маршрутизации группы беспилотных летательных аппаратов (БПЛА). Показано, что модель движения транспортных средств с несколькими депо можно применить для планирования полета группы БПЛА. Разработан макси-минный алгоритм муравьиных колоний для решения одной из задач маршрутизации. Проведен сравнительный анализ алгоритмов для решения задачи маршрутизации группы БПЛА. The problem of routing a group of unmanned aerial vehicles (UAVs) is considered. It is shown that the model of movement of vehicles with several depots can be used to plan the flight of UAV groups. Max-min ant system algorithm for solving a multi-depot routing problem is developed. A comparative analysis of algorithms for solving the problem of routing a group of UAVs is presented. 2019 Article Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем / Л.Ф. Гуляницький, В.В. Сторчевий // Компьютерная математика. — 2019. — № 1. — С. 85-93. — Бібліогр.: 17 назв. — укр. 2616-938Х https://nasplib.isofts.kiev.ua/handle/123456789/161937 519.8 uk Компьютерная математика application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Оптимизация вычислений Оптимизация вычислений
spellingShingle	Оптимизация вычислений Оптимизация вычислений Гуляницький, Л.Ф. Сторчевий, В.В. Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем Компьютерная математика
description	Розглянуто проблему маршрутизації групи безпілотних літальних апаратів (БПЛА) при обстеженні заданих об'єктів. Показано, що модель руху транспортних засобів з декількома депо можна використати для планування польоту групи БПЛА. Розроблено спеціальний макс-мін алгоритм мурашиних систем для розв'язування однієї із таких задач маршрутизації з декількома депо. Проведено порівняльний аналіз трьох алгоритмів розв'язування.
format	Article
author	Гуляницький, Л.Ф. Сторчевий, В.В.
author_facet	Гуляницький, Л.Ф. Сторчевий, В.В.
author_sort	Гуляницький, Л.Ф.
title	Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем
title_short	Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем
title_full	Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем
title_fullStr	Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем
title_full_unstemmed	Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем
title_sort	оптимізація маршрутів групи бпла модифікованим алгоритмом мурашиних систем
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
topic_facet	Оптимизация вычислений
url	https://nasplib.isofts.kiev.ua/handle/123456789/161937
citation_txt	Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем / Л.Ф. Гуляницький, В.В. Сторчевий // Компьютерная математика. — 2019. — № 1. — С. 85-93. — Бібліогр.: 17 назв. — укр.
series	Компьютерная математика
work_keys_str_mv	AT gulânicʹkiilf optimízacíâmaršrutívgrupibplamodifíkovanimalgoritmommurašinihsistem AT storčeviivv optimízacíâmaršrutívgrupibplamodifíkovanimalgoritmommurašinihsistem AT gulânicʹkiilf optimizaciâmaršrutovgruppybplamodificirovanymalgoritmommuravʹinyhsistem AT storčeviivv optimizaciâmaršrutovgruppybplamodificirovanymalgoritmommuravʹinyhsistem AT gulânicʹkiilf routesoptimizationofuavgroupsbymodifiedantsystemalgorithm AT storčeviivv routesoptimizationofuavgroupsbymodifiedantsystemalgorithm
first_indexed	2025-12-02T11:01:52Z
last_indexed	2025-12-02T11:01:52Z
_version_	1850394083325902848
fulltext	ISSN 2616-938X. Компьютерная математика. 2019, № 1 85 Розглянуто проблему маршрути- зації групи безпілотних літальних апаратів (БПЛА) при обстеженні заданих об'єктів. Показано, що модель руху транспортних засо- бів з декількома депо можна вико- ристати для планування польоту групи БПЛА. Розроблено спеціаль- ний макс-мін алгоритм мураши- них систем для розв'язування од- нієї із таких задач маршрутизації з декількома депо. Проведено по- рівняльний аналіз трьох алгорит- мів розв'язування.  Л.Ф. Гуляницький, В.В. Сторчевий, 2019 УДК 519.8 Л.Ф. ГУЛЯНИЦЬКИЙ, В.В. СТОРЧЕВИЙ ОПТИМІЗАЦІЯ МАРШРУТІВ ГРУПИ БПЛА МОДИФІКОВАНИМ АЛГОРИТМОМ МУРАШИНИХ СИСТЕМ Вступ. Безпілотні літальні апарати (БПЛА) набувають все більш широкого використання в різних сферах, зокрема, у військовій для ведення повітряної розвідки – як тактичної, так і стратегічної. Ефективним варіантом їх застосування є вирішення завдань у складі групи [1 – 4]. У роботі досліджується задача математичного моделювання маршрутів гру- пи БПЛА, для розв’язування якої пропону- ється спеціальний алгоритм мурашиних ко- лоній, оскільки ефективність мурашиних ал- горитмів підтверджується досвідом розв'язу- вання різних задач маршрутизації транспорту (Vehicle Routing Problems, VRP) [5 – 8]. Для дослідження ефективності розробленого ал- горитму проведено обчислювальний експе- римент, у якому порівнювалися результати його застосування із алгоритмами спеціаль- ного локального пошуку і повного перебору. 1. Постановка задачі пошуку об’єкта Розглядається проблема пошуку опти- мальних маршрутів для групи спеціальних літальних апаратів, у першу чергу, БПЛА. Вона полягає у тому, що перед заданою гру- пою БПЛА, які можуть стартувати з різних точок пуску та мають можливість закінчува- ти маршрут у різних місцях (депо), стоїть завдання облетіти низку заданих об’єктів (то- чок на місцевості) з мінімізацією сумарної довжини маршрутів чи тривалості польотів за умов, що кожен об’єкт відвідується одним і лише одним БПЛА і всі об’єкти мають бути відвіданими. При цьому часто слід врахову- вати ще й ряд додаткових обмежуючих умов (дальність польоту без підзаряджання чи Л.Ф. ГУЛЯНИЦЬКИЙ, В.В. СТОРЧЕВИЙ ISSN 2616-938X. Компьютерная математика. 2019, № 186 дозаправлення, вантажопідйомність, погодні умови тощо). Отже, приземлення БПЛА може здійснюватися в декількох заданих територіально зонах. Припуска- ється також, що характеристики кожної зони вибираються так, що у конкретній зоні можливе приймання заданої кількості БПЛА: у такій зоні можуть завершу- вати свій маршрут всі чи частина БПЛА. Кожну зону будемо ідентифікувати її центроїдом. Отже, маршрут кожного із БПЛА повинен закінчуватися в одній із таких зон, але конкретна зона для БПЛА не вказується. Цю проблему назвемо задачею маршрутизації з альтернативними депо. Кількість місць старту БПЛА може перевищувати кількість самих БПЛА – це створює додаткові можливості для вибору місць (чи моментів) старту. Також відмітимо, що в процесі розв'язу- вання задачі маршрутизації може оптимізуватися також і кількість задіяних БПЛА. Задача. За умови наявності декількох можливих зон приймання БПЛА і місць старту БПЛА, а також завершення маршрутів БПЛА лише в одній із виді- лених зон слід визначити як маршрути БПЛА з оптимізацією сумарної довжини (тривалості польотів) та їх задіяної кількості, так і місця (зони) їх приймання. Зауважимо, що в одній зоні може завершуватися декілька маршрутів БПЛА. Змістовна постановка задачі маршрутизації груп БПЛА для пошуку об’єктів може бути подана так. Задано координати місць старту, кількість БПЛА, коор- динати точок, які необхідно відвідати, координати зон приймання, польотний ресурс кожного БПЛА, ємність зон приймання. Критерієм виступатиме мінімум сумарної довжини маршрутів польоту для виконання завдання, що і визначатиме час виконання завдання; мінімум БПЛА. 2. Математична модель Вважаємо заданими: m – загальна кількість БПЛА; b – кількість місць старту ( b m ); e – кількість зон приймання БПЛА ( 1e  ); n – кількість об'єктів, які слід відвідати; kR – польотний ресурс k-го БПЛА, 1,...,k m . Підкреслимо, що кількість місць старту БПЛА не може бути меншою m , а в разі, коли m n , частина із них не буде задіяною. Розглянемо зважений граф ( , )G Y U , де вершини Y відповідають об'єк- там, місцям старту та зонам приймання, тобто \|\| \|\|Y = n b e  , задавши таку їх нумерацію: від 1 до n – об'єкти, від 1n  до n b – місця старту, а від 1n b  до n b e  – зони (їх центроїди). Позначимо {1,..., }V n множину вершин, які відповідають об'єктам, { 1,..., }B n n b   – множину вершин, які відповідають місцям старту, { 1,..., }E n b n b e     – вершини, що відповідають зонам приймання. Зро- зуміло, що для вершин із множини B матимемо лише вихідні дуги, а для вер- шин із E – лише вхідні. ОПТИМІЗАЦІЯ МАРШРУТІВ ГРУПИ БПЛА МОДИФІКОВАНИМ АЛГОРИТМОМ МУРАШИНИХ… ISSN 2616-938X. Компьютерная математика. 2019, № 1 87 Для подання розв'язку введемо матрицю ( )ijX x розмірністю ( )m n b e   , де {0,1}ijx  , яка складається із трьох блоків. Перший блок включає стовпчики від 1 до n , другий – від 1n  до n b , третій – від 1n b  до n b e  , а рядки будуть відповідати номерам БПЛА. Ця матриця буде опи- сувати фактично етап розбиття, на якому кожному БПЛА приписуються ті об'єк- ти, які він має відвідати, разом із одним із місць старту та місцем завершення маршруту. Позначимо j максимальну кількість БПЛА, які можуть бути прийняті в зо- ні j , 1,...,j e . Задача розбиття (як окремий етап чи складова загального процесу розв'язу- вання) може бути подана так. Обмежуючі умови: 1 1, 1,..., ; n b ij j n x i m      (1) 1 1, 1,..., ; n b e ij j n b x i m        (2) 1 1, 1,..., ; m ij i x i n    (3) 1 1, 1,..., ; m ij i x j n n b      (4) 1 1 ; n b m ij j n i x m       (5) 1 , 1,..., ; m ij j n b i x j n b n b e          (6) ( ) , 1,..., .i i iL x R i m  (7) Задача полягає у пошуку такого розв'язку Х, для якого 1 ( ) ( ) min, m i i i F X L x    (8) за умов (1) – (7), де ix – це i -й вектор-рядок матриці X , а ( )i iL x – довжина маршруту i -го задіяного БПЛА як розв'язку задачі комівояжера, який визнача- ється вершинами, що відповідають ненульовим компонентам вектора ix , почи- наючи з певного стартового місця : 1iss B x  і закінчуючи зоною : 1iff E x  . Л.Ф. ГУЛЯНИЦЬКИЙ, В.В. СТОРЧЕВИЙ ISSN 2616-938X. Компьютерная математика. 2019, № 188 Зрозуміло, що для незадіяних БПЛА відповідний вектор-рядок матиме всі нульові координати. Тобто матриця X , як елемент простору розв'язків задачі (1) – (8), у ком- пактному вигляді може бути подана так: 1 m x X x             , де 1 2 ,( , ,..., )i i i i n b ex x x x   . Умова (1) визначає, що кожен і-й БПЛА стартує лише з одного із можливих місць старту (чи в момент часу, який і визначає таке місце), якщо ж деякий БПЛА не задіяний, то відповідний рядок стає нульовим. Аналогічно, формула (2) описує ситуацію, що до конкретного центроїда від об'єктів або веде одне і лише одне ребро графа G, або жодного. Умова (3) визначає, що кожен об'єкт j V відвідується лише одним БПЛА. Умова (4) визначає, що з кожного місця або стартує один БПЛА, або ж це місце не задіяне, а разом із умовою (5) – що кількість задіяних місць співпадає із кількістю БПЛА. Можливість приймати в кожній зоні j E (в іншому трактуванні – у момент часу) не більше, ніж j БПЛА, відображена у формулі (6). Обмеження на польотний ресурс кожного літального апарату визначено умовою (7). Зауважимо, що не виключаються випадки, коли в одній зоні (чи в момент часу) може прийматися лише один БПЛА, тоді 1j  для відповідної зони, чи всі БПЛА можуть бути прийняті в одній зоні – в цьому разі 1,e  а 1 .m  Таким чином, ця задача подібна до задачі маршрутизації транспортних засо- бів із декількома депо (Multiple Depot Vehicle Routing Problem, MDVRP) з додат- ковими обмеженнями [1, 5]. MDVRP є більш складною задачею, ніж класична задача VRP. До того ж, MDVRP є NP-складною задачею, це означає, що не існує ефективного алгоритму для отримання оптимального її розв’язування. Точні методи, такі як метод гілок і меж, метод гілок і відтинання, є неефективними для розв’язування MDVRP через надмірну трудомісткість. Для того, щоб ефективно розв'язувати подібні задачі, використовуються наближені алгоритми [9]. 3. Алгоритми розв'язування задачі Прямий перебір. Найпростіший точний метод, який можна застосувати – це прямий перебір всіх можливих варіантів. Алгоритм повного перебору всіх мож- ливих розв’язків задачі складається з чотирьох етапів. Перший етап – формуван- ня всіх можливих перестановок початкових депо. Для визначення кількості перестановок з b елементів маємо формулу !bP b . Другий етап – розбиття множини з n об'єктів, які необхідно відвідати. Загальна кількість поділів дові- льної n-елементної множини дорівнює числу Белла, яке можна обчислити як ОПТИМІЗАЦІЯ МАРШРУТІВ ГРУПИ БПЛА МОДИФІКОВАНИМ АЛГОРИТМОМ МУРАШИНИХ… ISSN 2616-938X. Компьютерная математика. 2019, № 1 89 суму чисел Стірлінга другого роду, 0 ( , ) n n m B S n m   [10]. Третій етап – формування всіх можливих розміщень для e зон приймання. Загальна кількість розміщень визначається за наступною формулою: ! ( )! b e bA b e   . Останній етап – композиція всіх маршрутів отриманих на перших трьох кроках, загальна кількість варіантів 0 !! ( , ) ( )! n m bk b S n m b e   . Через таку надзвичайно велику кількість варіантів можна зробити висновок, що методом повного перебору неможливо знайти оптимальний розв'язок за прийнятний час. Його застосування виправдане лише для задач невеликої розмірності для отримання точного розв’язку. Локальний пошук. Алгоритми локального пошуку використовують поняття околу в просторі розв’язків задачі .X Варіант розв’язку складається з множини маршрутів – послідовності номерів клієнтів, які відвідуються кожним БПЛА. Кожен маршрут починається з стартового депо та закінчується зоною приймання. Наприклад, маємо два БПЛА. Перший стартує з місця старту № 1, відвідує клієнта № 4, потім клієнта № 3 та летить у зону приймання № 6. Другий починає рух з місця старту № 2, відвідує клієнтів № 5, № 7, № 8 та летить у зону приймання № 9, що відобразимо так:     1,4,3,6 . 2,5,7,8,9       Для генерації околів ( )O x довільної точки x X застосовується оператор переміщення, який є одним з найбільш ефективних способів модифікації маршруту [11]. Для розв’язування сформульованої задачі пропонується два наближених алгоритми: табу пошуку та мурашиний алгоритм. Табуйований пошук, який довів свою ефективність при розв’язуванні ряду задач класу MDVRP [12], пропонується гібридизувати з конструктивним алгоритмом, який реалізує принцип жадібного вибору. Псевдокод алгоритму подамо так. procedure TABU_SEARCH_WITH_GREEDY (x); ініціалізація_алгоритму; :x  припустимий варіант розв'язку, сформований жадібним алгоритмом; :T  ; :recx x while не_виконується_критерій_завершення do пошук_прийнятного_варіанта ( ) \y O x T ; Л.Ф. ГУЛЯНИЦЬКИЙ, В.В. СТОРЧЕВИЙ ISSN 2616-938X. Компьютерная математика. 2019, № 190 :x y ; :T T x  ; if ( ) ( )recf x f x then :recx x ; if \| \|T  максимальний_розмір_табу_списку then видалення_з_множини_Т_найстарішого_елемента; endwhile end Макс-мін алгоритм мурашиних систем. Більш інтенсивне використання кращих розв’язків у ході пошуку призводить до підвищення продуктивності алгоритмів оптимізації мурашиною колонією [13], але при цьому підвищується ризик передчасної збіжності. Тому доречно комбінувати використання кращих розв’язків та процедури запобігання передчасній збіжності. Для задоволення цих двох потреб розроблений спеціальний макс-мін алгоритм мурашиних систем як покращення алгоритму мурашиних систем [14]. Для уникнення стагнації розв’язку вводиться інтервал значень для феромону, тобто вводиться поняття нижньої та верхньої межі. На початку роботи алгоритму матриця феромонів іні- ціалізується значеннями нижньої межі феромону. Після кожної ітерації тільки один агент залишає слід феромону, зазвичай це агент, що знайшов кращий маршрут на поточній ітерації. Для розв'язування сформульованої задачі викори- стовується модифікований макс-мін алгоритм мурашиних систем. Розв’язок будується покроково: поточна мураха вибирає наступну вершину графа задачі, після переходу в яку ця вершина стає недоступною для відвідання мурахами, які роблять свій крок пізніше. Псевдокод алгоритму можна подати так. procedure MMAS (x) ініціалізація_алоритму; while кількість_ітерацій_без_покращення_менша_заданої do формування_популяції_мурах; while не_всі_вершини_відвідані do for чергова_мураха_з_популяції do ініціалізація_поточного_кроку_мурахи; М = оновлення_пам'яті_мурахи; А = локальна_матриця_мурашиних_маршрутів; сформувати_множину_припустимих_вершин_зурахуванням _наявного_ресурсу; р = обчислити_ймовірність_переходів(А, М, П); наступний_стан = правило_прийняття_рішення(р, П); вибравши вершину, перейти_в_наступний_стан; М = оновити_внутрішній_стан; вилучити вибрану вершину із списку припустимих; ОПТИМІЗАЦІЯ МАРШРУТІВ ГРУПИ БПЛА МОДИФІКОВАНИМ АЛГОРИТМОМ МУРАШИНИХ… ISSN 2616-938X. Компьютерная математика. 2019, № 1 91 endfor endwhile завершити_діяльність; відкласти_феромон_на_найкращому_маршруті_на_поточній_ітерації; випаровування_феромону; оновлення_рекорду (х); endwhile end Тут П – предикат, що описує обмеження задачі (більш детальніший опис обчислювальної схеми алгоритмів оптимізації мурашиними колоніями див. в [15]). 4. Обчислювальний експеримент Оскільки у відкритому доступі немає даних для даної задачі, то був згенеро- ваний набір задач з використанням системи Google Maps API. Згенеровані зада- чі мають розмірність від 10 до 500 об’єктів, які необхідно відвідати, у середньо- му 4 – 7 місць старту та 2 – 5 зон приймання. Додаткові позначення: n  кількість об’єктів, що необхідно відвідати; MMAS – модифікований мах- мінний алгоритм мурашиних систем; TabuSearch – локальний пошук (табу по- шук) з використанням оператора переміщення; Bruteforce – алгоритм прямого перебору; почf – початковий розв’язок; розf – розв’язок задачі, отриманий алго- ритмом; 100 %поч роз поч f f q f    – відносне покращення початкового розв’язку (у відсотках); t  час виконання алгоритму (у мілісекундах). Всі алгоритми реалізовані на одній і тій же програмній базі на мові Kotlin, пошук розв’язків здійснювався на персональному комп’ютері з 16 ГБ оператив- ної пам’яті та восьмиядерним процесором з тактовою частотою 3.6 ГГц. Це до- зволяє порівнювати час роботи алгоритмів. Жирним шрифтом виділені найкращі розв’язки між всіма алгоритмами (таблиця). Параметри. Для локального пошуку застосовані наступні параметри: 5l  – розмір списку заборон, 500iter  – кількість можливих ітерацій, на яких не відбувається покращення розв’язку. Для макс-мін алгоритму мурашиних систем: noa m (кількість БПЛА) – кількість мурах, noi = 1000 – кількість можливих ітерацій, на яких не відбувається покращення розв’язку,  = 1 – ступінь значу- щості феромонного сліду, = 1 – ступінь значущості евристичної інформації, e = 0.1 – стала випаровування. Параметри підібрані шляхом вибору найкращих з проведеної серії попере- дніх випробувань. Л.Ф. ГУЛЯНИЦЬКИЙ, В.В. СТОРЧЕВИЙ ISSN 2616-938X. Компьютерная математика. 2019, № 192 ТАБЛИЦЯ MMAS TabuSearch Bruteforce Задача n fпоч fроз q t fпоч fроз q t fроз t 1 10 2757.1 2193.9 20.4 61 2465.5 2157.3 12.5 6 1690.1 62 2 16 3987.4 3299.2 17.2 69 4510.5 3669.4 18.6 7 3151.2 23621 3 30 7696.4 4369.5 43.2 158 6941.6 4478.9 35.4 30 – – 4 50 7947.9 5738.7 27.7 294 7784 6443 17.2 149 – – 5 100 13619.2 9693.4 28.8 978 16430 9665.8 41.1 212 – – 6 500 28725.4 19698.2 31.4 44712 29906 24869.6 16.8 35840 – – Як випливає з результатів експерименту, розроблений модифікований макс- мінний алгоритм мурашиних систем продемонстрував підвищені показники то- чності в порівнянні з алгоритмами локального пошуку та прямого перебору. Висновки. Запропоновано змістовну постановку виділеної задачі маршру- тизації для виконання обльоту об’єктів групою БПЛА з умовою завершення ма- ршруту в зонах приймання та обмеженнях на ресурси БПЛА як спеціальної за- дачі комбінаторної оптимізації. Показано, що математична модель руху групи БПЛА може бути зведена до моделі маршрутизації транспортних засобів із декількома депо. Таку оптиміза- ційну задачу можна розв’язувати методом повного перебору лише при малій розмірності задачі. Для розв’язування сформульованої задачі маршрутизації групи БПЛА розроблено макс-мін алгоритм мурашиних систем. Особливістю алгоритму є покрокова взаємодія мурах при формуванні розв'язків. Напрямком подальших досліджень може бути покращення мурашиного ал- горитму за рахунок використання «далекозорих» мурах [16] та паралельної реа- лізації острівної моделі [17]. Л.Ф. Гуляницкий, В.В. Сторчевый ОПТИМИЗАЦИЯ МАРШРУТОВ ГРУППЫ БПЛА МОДИФИЦИРОВАНЫМ АЛГОРИТМОМ МУРАВЬИНЫХ СИСТЕМ Рассмотрена проблема маршрутизации группы беспилотных летательных аппаратов (БПЛА). Показано, что модель движения транспортных средств с несколькими депо можно применить для планирования полета группы БПЛА. Разработан макси-минный алгоритм муравьиных колоний для решения одной из задач маршрутизации. Проведен сравнительный анализ алго- ритмов для решения задачи маршрутизации группы БПЛА. L.F. Hulianytskyi, V.V. Storchevyi ROUTES OPTIMIZATION OF UAV GROUPS BY MODIFIED ANT SYSTEM ALGORITHM The problem of routing a group of unmanned aerial vehicles (UAVs) is considered. It is shown that the model of movement of vehicles with several depots can be used to plan the flight of UAV groups. Max-min ant system algorithm for solving a multi-depot routing problem is developed. A comparative analysis of algorithms for solving the problem of routing a group of UAVs is pre- sented. ОПТИМІЗАЦІЯ МАРШРУТІВ ГРУПИ БПЛА МОДИФІКОВАНИМ АЛГОРИТМОМ МУРАШИНИХ… ISSN 2616-938X. Компьютерная математика. 2019, № 1 93 Список літератури 1. Golden B., Raghavan S., Wasil E. The Vehicle Routing Problem: Latest Advances and New Challenges. Springer Science+Business Media. 2008. 2. Гуляницький Л.Ф., Рибальченко О.В. Формалізація та розв'язування одного типу задач маршрутизації БПЛА. Теорія оптимальних рішень. 2018. 17.– С. 107 – 114. 3. Adbelhafiz M., Mostafa A., Girard A. Vehicle Routing Problem Instances: Application to Multi-UAV Mission Planning. AIAA Guidance, Navigation, and Control Conference, Ontario. 2010. 4. Chiang W., Li Y., J. Shang, Urban T.L. Impact of drone delivery on sustainability and cost: Realizing the UAV potential through vehicle routing optimization, Applied Energy. 2019. 242. Р. 1164 – 1175. 5. Гуляницкий Л.Ф. Проблема оптимизации маршрутов транспортных средств с вре- менными окнами. Компьютерная математика. 2007. № 1. С. 122 – 132. 6. Liu D., Li S. Research on efficient online planning of emergency logistics path based on doublelayer ant colony optimization algorithm. International Journal of Computers and Applications. 2018. 33. Р. 1 – 7. 7. Franco C., Aguilar H., Ochoa-Zezzatti A., Gallegos P. Comparison between instances to solve the CVRP. International Journal of Combinatorial Optimization Problems and Informatics. 2018. 9(2). Р. 41 – 54. 8. Yu M., Li S., Kong M., Song J., Yang J., Ren G. Comparison of advantages and disadvantages among various algorithms in logistics path design – Taking H-group as an example. Cognitive Systems Research. 2018. 52. Р. 843 – 852. 9. Pereira F. B., Tavares J. Bio-inspired Algorithms for the Vehicle Routing Problem. Studies in Computational Intelligence 161, Springer. 2009. Р. 79. 10. Липский В. Комбинаторика для программистов: Пер. с польск. М.: Мир. 1988. 213 с. 11. Kohl N. Exact methods for Time Constrained Routing and Related Scheduling Problems. PhD thesis, Department of Mathematical Modelling, Technical University of Denmark. 1995. 12. 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 En- gineering. 2017. Vol. 107. Р. 211 – 222. 13. Dorigo M., Stützle T. Ant Colony Optimization: Overview and Recent Advances. Springer International Publishing AG. 2019. Р. 311 – 352. 14. Stützle T., Hoos H.H. MAX-MIN ant system. Future Generation Computer Systems. 2000. Р. 889 – 914. 15. Гуляницький Л.Ф., Мулеса О.Ю. Прикладні методи комбінаторної оптимізації: навч. посіб. К.: Видавничо-поліграфічний центр "Київський університет". 2016. 142 с. 16. Гуляницький Л.Ф. Новий алгоритм оптимізації мурашиними колоніями. Сучасна інфор- матика: проблеми, досягнення та перспективи розвитку. Пр. Міжн. конф., присвя- ченої 60-річчю заснування ІК імені В.М. Глушкова НАН України (Київ, 13 – 15 грудня 2017 р.). К.: ІК ім. В.М. Глушкова НАН України. 2017. С. 41 – 43. 17. Mora A.M., García-Sánchez P., Merelo J.J. Pareto-based multi-colony multi-objective ant col- ony optimization algorithms: an island model proposal. Soft Computing. 2013. Vol. 17. Р. 1175. Одержано 20.04.2019 Про авторів: Гуляницький Леонід Федорович, доктор технічних наук, завідувач відділу Інституту кібернетики імені В.М. Глушкова НАН України, E-mail:LeonHul.ICyb@dmail:com Сторчевий Владислав Володимирович, магістрант Інституту кібернетики імені В.М. Глушкова НАН України.

Оптимізація маршрутів групи БПЛА модифікованим алгоритмом мурашиних систем

Institution

Ähnliche Einträge