Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів з динамічними депо

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

Full description

Saved in:

Bibliographic Details
Date:	2019
Main Authors:	Горбулін, В.П., Гуляницький, Л.Ф., Сергієнко, І.В.
Format:	Article
Language:	Ukrainian
Published:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2019
Series:	Управляющие системы и машины
Subjects:	Фундаментальные и прикладные проблемы Computer Science
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/161571
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів з динамічними депо / В.П. Горбулін, Л.Ф. Гуляницький, І.В. Сергієнко // Управляющие системы и машины. — 2019. — № 1. — С. 3-10. — Бібліогр.: 12 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-161571
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1615712025-02-23T18:22:03Z Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів з динамічними депо Постановки и математические модели проблем оптимизации маршрутов летательных аппаратoв с динамическими депо Formulations and Mathematical Models of the Optimizing Routes Problems for Aircraft with Dynamic Depots Горбулін, В.П. Гуляницький, Л.Ф. Сергієнко, І.В. Фундаментальные и прикладные проблемы Computer Science Аналізуються проблеми оптимізації маршрутів групи безпілотних літальних апаратів, що діють як команда, перед якою поставлено завдання обстежити або обслужити кілька об'єктів. Вперше розглянуто випадок, коли ці апарати починають і завершують свій маршрут на борту літака-носія. Запропоновано математичну модель однієї з таких проблем і підходи до розв'язування, орієнтовані на застосування методів локального пошуку. Цель статьи – анализ и формализация задач маршрутизации указанного типа. Методика. Разработка математических моделей проблем оптимизации поиска оптимальных маршрутов ЛА, выполняющих задачи с использованием самолета-носителя, ориентированных на применение методов комбинаторной оптимизации. Результат. Разработана новая математическая модель проблем, заключающихся в том, что перед заданной группой ЛА, которые могут стартовать с разных точек пуска и имеют возможность заканчивать маршрут в разных местах траектории самолета-носителя, стоит задача облететь ряд заданных объектов (точек на местности) с минимизацией суммарной длины маршрутов или длительности полетов при условии, что каждый объект посещается одним и только одним ЛА и все объекты должны быть посещаемыми. Purpose. Analysis and formalization of routing problems of the specified type. Methods. Mathematical models development to find the optimal routes for the aircraft using an aircraft carrier, that are focused on the use of combinatorial optimization methods. Results. A new mathematical model has been developed for the problems where a given aircraft group, that can start from different launch points and has the ability to complete the route in different places of the aircraft carrier trajectory, has the task to fly over a number of specified objects (points on the ground) with minimizing the total route lengths or flight duration, provided that each object is visited by one and only one aircraft and all objects must be visited. 2019 Article Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів з динамічними депо / В.П. Горбулін, Л.Ф. Гуляницький, І.В. Сергієнко // Управляющие системы и машины. — 2019. — № 1. — С. 3-10. — Бібліогр.: 12 назв. — укр. 0130-5395 DOI: https://doi.org/10.15407/usim.2019.01.003 https://nasplib.isofts.kiev.ua/handle/123456789/161571 519.8 uk Управляющие системы и машины application/pdf Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Фундаментальные и прикладные проблемы Computer Science Фундаментальные и прикладные проблемы Computer Science
spellingShingle	Фундаментальные и прикладные проблемы Computer Science Фундаментальные и прикладные проблемы Computer Science Горбулін, В.П. Гуляницький, Л.Ф. Сергієнко, І.В. Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів з динамічними депо Управляющие системы и машины
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	Фундаментальные и прикладные проблемы Computer Science
url	https://nasplib.isofts.kiev.ua/handle/123456789/161571
citation_txt	Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів з динамічними депо / В.П. Горбулін, Л.Ф. Гуляницький, І.В. Сергієнко // Управляющие системы и машины. — 2019. — № 1. — С. 3-10. — Бібліогр.: 12 назв. — укр.
series	Управляющие системы и машины
work_keys_str_mv	AT gorbulínvp postanovkitamatematičnímodelíproblemoptimízacíímaršrutívlítalʹnihaparatívzdinamíčnimidepo AT gulânicʹkijlf postanovkitamatematičnímodelíproblemoptimízacíímaršrutívlítalʹnihaparatívzdinamíčnimidepo AT sergíênkoív postanovkitamatematičnímodelíproblemoptimízacíímaršrutívlítalʹnihaparatívzdinamíčnimidepo AT gorbulínvp postanovkiimatematičeskiemodeliproblemoptimizaciimaršrutovletatelʹnyhapparatovsdinamičeskimidepo AT gulânicʹkijlf postanovkiimatematičeskiemodeliproblemoptimizaciimaršrutovletatelʹnyhapparatovsdinamičeskimidepo AT sergíênkoív postanovkiimatematičeskiemodeliproblemoptimizaciimaršrutovletatelʹnyhapparatovsdinamičeskimidepo AT gorbulínvp formulationsandmathematicalmodelsoftheoptimizingroutesproblemsforaircraftwithdynamicdepots AT gulânicʹkijlf formulationsandmathematicalmodelsoftheoptimizingroutesproblemsforaircraftwithdynamicdepots AT sergíênkoív formulationsandmathematicalmodelsoftheoptimizingroutesproblemsforaircraftwithdynamicdepots
first_indexed	2025-11-24T09:20:40Z
last_indexed	2025-11-24T09:20:40Z
_version_	1849662940592996352
fulltext	iSSN 0130-5395, усим, 2019, № 1 3 Фундаментальные и прикладные проблемы Computer Science вступ В останнє десятиліття чітко визначилася тен- денція до розширення сфер використання безпілотних апаратів, зокрема, безпілотних лі- тальних апаратів (БПЛА) . Світовий досвід роз- витку безпілотної авіації, перш за все, у таких розвинених країнах, як США, Німеччина, Із- раїль, показує, що БПЛА в найближчі 10—15 років зможуть виконувати більшість завдань, які здійснюються нині пілотованими засоба- ми . Уже зараз БПЛА використовуються для контролю технічного стану, безпеки та про- цесу функціонування різних об'єктів і систем, зокрема, в екології, сільському чи лісовому господарстві, на залізничному транспорті, при організації морських пошуково-рятувальних операцій [1, 2] . Все більш суттєву роль БПЛА відіграють і у військових застосуваннях, один із таких аспектів можливого застосування буде розглянуто далі . Крім задач маршрутизації літальних апара- тів (ЛА), що стартують з землі, останнім часом набувають актуальності проблеми маршру- тизації у випадку, коли ЛА (БПЛА чи крилаті ракети) запускаються зі спеціального літака- носія, маршрут якого прокладається з ураху- ванням можливого застосування противником засобів протиповітряної оборони чи літаків- doi https://doi.org/10.15407/usim.2019.01.003 удк 519.8 в.п. ГорБУлІн, д-р техн. наук, проф., академік НаН україни, віце-президент НаН україни, директор Національного інституту стратегічних досліджень вул. Володимирська, 54, київ-30, 01601, україна, horbulin@nas.gov.ua л.Ф. ГУляниЦЬКиЙ д-р техн. наук, проф., ст. науковий співробітник, зав. відділом, Інститут кібернетики ім. В.м. глушкова НаН україни, просп. академіка глушкова, 40, київ, 03187, україна, leonhul.icyb@gmail.com І.в. серГІЄнКо, д-р фіз.-мат. наук, проф., академік НаН україни, директор інституту Інститут кібернетики ім. В.м. глушкова НаН україни, просп. академіка глушкова, 40, київ, 03187, україна, incyb@incyb.kiev.ua постановКи та математиЧнІ моделІ проБлем оптимІЗаЦІЇ маршрУтІв лІталЬниХ апаратІв З динамІЧними депо Аналізуються проблеми оптимізації маршрутів групи безпілотних літальних апаратів, що діють як команда, перед якою поставлено завдання обстежити або обслужити кілька об'єктів. Вперше розглянуто випадок, коли ці апарати починають і завершують свій маршрут на борту літака-носія. Запропоновано математичну модель однієї з таких проблем і підходи до розв'язування, орієнтовані на застосування методів локального пошуку. Ключові слова: безпілотні літальні апарати, оптимізація маршрутів, динамічні депо, математична модель, комбінаторна оптимізація. 4 iSSN 0130-5395, control systems and computers, 2019, № 1 Горбулін В.П., Гуляницький Л.Ф., Сергієнко І.В. винищувачів — це і стане предметом дослід- ження . Важливим аспектом, від якого залежить ефективність використання групи об'єднаних в мережу БПЛА, є питання вироблення стра- тегії кооперативної взаємодії при вирішенні поставлених завдань, що дає змогу суттєво під- вищити ефективність використання такої гру- пи взаємодіючих БПЛА у порівнянні з їх авто- номним застосуванням [1] . Загальна проблематика оптимізації маршрутів ла з декількома депо Розглядаються проблеми пошуку оптималь- них маршрутів для групи спеціальних ЛА, зокрема, БПЛА . Вони полягають у тому, що перед заданою групою ЛА, які можуть старту- вати з різних точок пуску та мати можливість закінчувати маршрут в різних місцях (депо), стоїть завдання облетіти низку заданих об'єктів (точок на місцевості) з мінімізацією сумарної довжини маршрутів або тривалос- ті польотів за умов, що кожен об'єкт відві- дується одним і лише одним ЛА і всі об'єкти мають бути відвіданими . При цьому часто слід враховувати ще й додаткові обмежуючі умови (дальність польоту без підзаряджання чи дозаправлення, вантажопідйомність, мі- німальний радіус розвороту, погодні умови тощо) [1—4] . У ряді випадків постановка таких проблем є близькою до відомого класу задач маршрутиза- ції транспортних засобів (МТЗ) [5, 6], зокрема, з багатьма депо [7] . Враховуючи це, в подаль- шому інколи вживатиметься і відповідна тер- мінологія . Особливістю розглянутих проблем буде те, що як старти ЛА, так і завершення їх марш- рутів здійснюватимуться з використанням літака-носія . У загальному випадку вирішення проблеми маршрутизації групи ЛА може бути природним чином розбите на три етапи:  Розбиття множини об’єктів на диз’юнкт- ні підмножини, за кожною з яких закріплю- ється один ЛА .  Побудова маршруту кожного ЛА з оптимі-Побудова маршруту кожного ЛА з оптимі- зацією його довжини .  Уточнення маршрутів за необхідності (при несуттєвих змінах обстановки, врахування по- годних умов у конкретний період тощо) . Зауважимо, що за певних підходів (напри- клад, із застосуванням оптимізації мураши- ними колоніями) перший та другий етапи об’єднуються в одну оптимізаційну задачу [8] . Отже, маємо літак-носій, з якого можуть стартувати кілька спеціальних ЛА (БПЛА, крилаті ракети з управлінням), які після вико- нання завдань можуть бути прийняті на борт літака-носія у спеціальний спосіб . Оскільки відомі параметри/характеристики літака-носія, моменти пуску чи приймання ЛА на борт можуть характеризуватися як часом, що минув від зльоту, так і місцями на маршруті . Спеціальні ЛА можуть використовувати- ся для виконання завдань двох таких типів: обстеження заданої множини об’єктів (роз- відка) чи відвідування об’єктів з їх обслуго- вуванням . Відповідно, це породжує певні математичні постановки спеціальних задач оптимізації . проблеми обстеження Серед задач пошуку оптимальних маршрутів ЛА, що породжуються проблемами обстеження, ви- ділимо такі (для кращого розуміння суті проблем обмежуючі умови поки не описуватимуться) . Задача 1. Літак-носій летить заданим марш- рутом, при цьому час/місце старту та час/місце приймання кожного ЛА відомі, а кожний ЛА має свої характеристики ресурсів . Математична постановка задачі зводиться до розширеної постановки задачі МТЗ з багатьма депо [5—7], де роль депо виконує літак-носій . Задача 2. Вважається, що маршрут літака- носія сформовано повністю . Також вважають- ся заданими:  часове вікно (відрізок маршруту), в межах якого дозволено проводити пуски ЛА та прий- мання їх на борт;  мінімально можливий часовий інтервал між пусками; iSSN 0130-5395, усим, 2019, № 1 5 Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів  часове вікно, яке визначає початок і завер-часове вікно, яке визначає початок і завер- шення процесу приймання ЛА на борт;  мінімально можливий часовий інтервал між прийманням двох ЛА . Задача 3. Разом із оптимізацією маршрутів ЛА розробити і траєкторію польоту літака- носія з урахуванням його характеристик (даль- ність польоту, швидкість, граничні кути пово- роту тощо) . Формалізація цієї проблеми призводить до складних динамічних задач неперервної опти- мізації, розв’язування яких у межах часових ресурсів, наявних у реальних ситуаціях, не ви- дається можливим . У той же час, врахування особливостей процесу планування маршрутів з використанням літака-носія дає змогу розро- бляти математичні моделі, придатні для прак- тичного використання, про що піде мова далі . проблеми обслуговування Постановка проблем обходу об’єктів з обслу- говуванням вимагає більш ускладненого опису та конкретизації умов виконання завдань . У загальному вигляді можна подати таку проблему . Задано:  множину об’єктів для обслуговування;  пріоритетність (важливість) об’єктів;  потреби кожного об’єкта;  характеристики утруднення доставки това-характеристики утруднення доставки това- рів (ймовірності недосягнення чи перехоплен- ня, завади);  групу ЛА із заданими характеристиками . Критерієм виступає оцінка максимального ефекту від обслуговування з врахуванням на- явних обмежень . Крім задач маршрутизації групи БПЛА, останнім часом виникла задача маршрутиза- ції групи крилатих ракет, яку відправляють у політ з літака-носія, що знаходиться на без- печній відстані від засобів протиповітряної оборони або винищувачів супротивника . Розробник таких систем — фірма Dynetics — називає їх гремлінгами [2—4] . На відміну від БПЛА, який може нести декілька ракет або бомб, багаторазова крилата ракета (гремлінг) має на борту засоби ураження і може засто- совуватись для знищення декількох цілей . Основним застосуванням гремлінгів є атака об’єкта групою з декількох (зазвичай, чоти- рьох) гремлінгів, які виконують різні функ- ції: ураження цілі, наведення, навігація, ре- трансляція команд керування, взаємодія з БПЛА інших типів або військовим літаком, пілотованим людиною . постановка спеціальної задачі маршрутизації з динамічними депо Для адаптації постановки задачі до умов практики зробимо припущення: приймання ЛА може здійснюватися в декількох заданих територіально зонах — виділених дільниць траєкторії літака-носія . Припускається та- кож, що характеристики кожної зони вибира- ються так, що під час польоту літака-носія в конкретній зоні можливе приймання на борт заданої кількості ЛА: в такій зоні можуть за- вершувати свій маршрут всі або частина ЛА . Тобто зона — це відрізок маршруту літака- носія (чи часове вікно, за яким розраховується відповідний відрізок маршруту), під час про- ходження якого літак-носій готовий і здатний приймати один або кілька ЛА . Кожну зону будемо ідентифікувати її центроїдом . Отже, маршрут кожного з ЛА повинен закінчувати- ся в одній із таких зон, але конкретна зона для конкретного ЛА не вказується . Цю проблему назвемо задачею маршрутиза- ції з динамічними депо . Кількість місць старту ЛА може перевищувати кількість самих ЛА — це створює додаткові можливості для вибору місць (чи моментів) старту . Також відзначимо, що в процесі розв’язу- вання задачі маршрутизації можна оптимізу- вати також і кількість застосованих ЛА . Основну задачу дослідження сформулюємо так . Задача 4. За умови використання літака- носія, наявності можливих зон приймання ЛА і місць або моментів їх старту та завершен- ня маршрутів лише в одній з виділених зон на маршруті літака-носія слід визначити як маршрути ЛА з оптимізацією сумарної довжи- 6 iSSN 0130-5395, control systems and computers, 2019, № 1 Горбулін В.П., Гуляницький Л.Ф., Сергієнко І.В. ни (тривалості польотів) та їх кількості, так і місця (зони) їх приймання . Тобто, в результаті розв’язування задачі в певному сенсі формується і маршрут літака- носія шляхом задання вузлових точок — місць старту та центроїдів зон приймання . Як від- значалося, в одній зоні може завершуватися декілька маршрутів БПЛА . Зауважимо, що у близькій постановці задачі з багатьма депо [8], ключовою відмінністю є те, що кожне депо ло- калізовано на місцевості і може використовува- тися як для відправлення, так і для приймання БПЛА . Дослідимо сформульовану проблему . Цілочислова математична модель проблеми Вважаємо заданими: т — загальна кількість ЛА, b — кількість місць старту (b m≥ ); е — кіль- кість зон приймання ЛА на літак-носій ( ); п — кількість об’єктів, які слід відвідати; Rk — польотний ресурс k-го ЛА, k = 1, . . ., m . Підкреслимо, що кількість місць старту ЛА не може бути меншою m, а в разі, коли m >n, частина з них не буде використана . Розглянемо зважений граф G = (Y, U), де вер- шини Y відповідають об’єктам, місцям старту та зонам приймання, тобто Y n b e= + + , за- давши таку їх нумерацію: від одиниці до п — об’єкти, від n + 1 до n + b — місця старту, а від n + b + 1 до n + b + e — зони (їх центроїди) . По- значимо V = {1,…,п} — множина вершин, які відповідають об’єктам, B = {n+1, . . ., n+b} — множина вершин, які відповідають місцям старту, E = {n+b+1, . . ., n+b+e} — вершини, що відповідають зонам приймання . Зрозуміло, що для вершин з множини B матимемо лише вихідні дуги, а для вершин з E — лише вхідні . Для подання розв’язку введемо матри- цю X = x ij розмірності ( )m n b e× + + , де { },0,1ijx ∈ яка складається з трьох блоків . У перший блок включено стовпчики від од- ного до п, у другий — від n + 1 до n + b, у третій — від n + b + 1 до n + b + e , а рядки будуть відповідати номерам ЛА . Ця матриця буде описувати фактично етап розбиття, на якому кожному ЛА приписуються ті об'єкти, які він має відвідати, разом з одним із місць старту та місцем завершення маршруту . Нехай c ij , c ij > 0, i j≠ — вага таких ребер ( ), ,i j U∈ що ( ), ,i j B B∉ × ( ),i j E E∉ × та ( ), .i j B E∉ × Позначимо δ j максимальну кіль- кість ЛА, які можуть бути прийняті в зоні j, j = 1, . . ., e . Задача розбиття (як окремий етап чи скла- дова загального процесу розв'язування) може бути подана так . Обмежуючи умови: (1) (2) (3) (4) (5) 1 , 1,..., . m ij j n b i x j n b n b eδ − − = ≤ = + + + +∑ (6) Задача полягає в пошуку такого розв'язку Х, для якого (7) за умов (1)—(6), де ix — це і-й вектор-рядок матриці Х, а ( )i iL x — довжина маршруту і-го застосованого ЛА, як розв'язку задачі комі- вояжера, який визначається вершинами, що відповідають ненульовим компонентам векто- ра ix , починаючи з певного стартового місця : 1iss B x∈ = і закінчуючи зоною : 1iff E x∈ = . Зрозуміло, що для незадіяних ЛА відповідний вектор-рядок має всі нульові координати . Тобто матриця Х, як елемент простору розв'язків задачі (1)—(7), у компактному ви- гляді може бути подана так: 1 1 2 ,, де ( , ,..., )i i i i n b e m x X x x x x x + +    = =      � . 1e ≥ 1 1, 1,..., ; n b ij j n x i m + = + ≤ =∑ 1 1, 1,..., ; n b e ij j n b x i m + + = + + ≤ =∑ 1 1, 1,..., ; m ij i x j n = = =∑ 1 1, 1,..., ; m ij i x j n n b = ≤ = + +∑ 1 1 ; n b m ij j n i x m + = + = =∑ ∑ 1 ( ) ( ) min, m i i i F X L x = ≡ →∑ iSSN 0130-5395, усим, 2019, № 1 7 Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів Умова (1) визначає, що кожен і-й ЛА стар- тує лише з одного з можливих місць старту (або момент часу, який і визначає таке місце) на маршруті літака-носія, якщо ж деякий ЛА не задіяний, то відповідний рядок стає нульо- вим . Аналогічно, формула (2) описує ситуа- цію, що до конкретного центроїда від об'єктів або веде одне і лише одне ребро графа G, або — жодного . Умова (3) визначає, що кожен об'єкт j V∈ відвідується лише одним ЛА . Умова (4) — що з кожного місця або стартує один ЛА, або ж це місце не використане, а разом з умо- вою (5) — що кількість задіяних місць збіга- ється з кількістю ЛА . Можливість літака-носія приймати в кожній зоні j E∈ (в іншому трак- туванні — у певний проміжок часу) не більше, ніж δ ј ЛА, відображена у формулі (6) . Зауважимо, що не виключаються випадки, коли в одній зоні (або в проміжок часу) може прийматися лише один ЛА, тоді δ 1j = для від- повідної зони, або ж всі ЛА можуть бути прий- няті в одній зоні — в цьому разі матимемо 1,e = а 1δ .m= Комбінаторна модель задачі Враховуючи обчислювальну складність про- блеми [9], більш придатною для розв'язування буде подання її у вигляді спеціальної задачі комбінаторної оптимізації . Під задачею ком- бінаторної оптимізації розуміємо пошук опти- муму цільової функції, визначеної у локально скінченому просторі розв'язків [10] . Як зазначалося, вершини графа G задачі пронумеровано спеціальним чином, що дає підстави оперувати їх номерами як числами — це дає можливість розв’язки задачі подати у вигляді такої матриці: 1 1 1 1 1 1 1 1 1 1 2 1 1 1 2 1 1 , ,..., , , ,..., , ,..., , , ,..., m m m k k k k m m m m m m k k k k y y y y y y Y y y y y y y − + − +     =       � , де 1 , i i i ky B y E∈ ∈ , якщо i-й ЛА має завдання відвідати хоча б один об’єкт, та в іншому разі 1 0, 1 i i i ky y= = − ; ,i jy V∈ 2,..., 1ij k= − , якщо i-й ЛА повинен відвідати ці вершини; { } 1 max ii m k k ≤ ≤ = ; 0,i j iy k j k= < ≤ , якщо для деяко- го i маємо k i < k; i = 1, . . ., m . Отже, кількість вершин, які відповідають об’єктам i приписуються до задіяного i-го ЛА, дорівнює k i – 2 . При розробці та програмній реалізації дея- ких алгоритмів більш зручним буде подання розв’язку у вигляді вектора X, у якому почер- гово відображаються рядки матриці Y (інфор- мативні елементи), а елементи i i ky E∈ беруть- ся зі знаком мінус, позначаючи у такий спосіб кінець списку номерів вершин, які належать до i-го ЛА, i = 1, . . ., m, якщо він є у розв’язку; в іншому разі, як зазначалося, рядок матриці Y матиме вигляд 0, -1, 0, …, 0 . Зазначимо, що іноді подібний вектор містить лише номери вершин, а їх розподіл між маршрутами ЛА описується додатко- вим вектором . Отже, розв’язок можна записати так: X = (Ф1, ..., Фm), де фрагмент Ф1, i = 1, . . ., m , може мати два варіанти подання: 1 2( , ,..., , ) i i i i i i kb v v e−Φ = − , якщо i-й ЛА має завдання відвідати вершини , 1,..., 2i j iv V j k∈ = − , починаючи з вершини ib B∈ і закінчуючи вершиною ie E∈ , або ж Ф1 = (0, -1), якщо i-й ЛА не бере участі у варі- анті розв’язку — назвемо такий фрагмент ви- родженим . Таким чином, фрагмент вектора від першої компоненти (яка відповідає вершині з B або дорівнює нулю) до першої від’ємної компо- ненти буде належати до першого ЛА, наступ- ний такий фрагмент до першої ж від’ємної компоненти — до другого ЛА і т .д . Позначимо Li множину компонентів векто- ра X, що утворюють i-й фрагмент, i = 1, . . ., m . За побудовою кожна така множина або міс- тить один елемент з B та один, взятий зі зна- ком мінус, з множини E, або ж є множиною {0, –1} — для вироджених фрагментів . Тоді цільову функцію задачі можна подати так: 1 ( ) ( ) m i i f X T L = = ∑ , (8) 8 iSSN 0130-5395, control systems and computers, 2019, № 1 Горбулін В.П., Гуляницький Л.Ф., Сергієнко І.В. де T (Li) для невироджених фрагментів — це розв’язок розімкнутої задачі комівояже- ра, побудованої на вершинах множини Li, маршрути у якому починаються з наявної в Li вершини з B, закінчуються — у відповід- ній вершині з E, причому порядок вершин у векторі X задає порядок їх обходу в марш- руті; для вироджених фрагментів, зрозуміло, T (Li) = 0 . Позначимо Ω множину всіх можливих век- торів зазначеного виду: { }.XΩ = Досліджувана задача, яку названо задачею маршрутизації з динамічними депо, в комбіна- торній формі може бути подана так: знайти такий вектор X ∈Ω , що ( ) arg min X X f X ∈Ω = (9) за обмежень (10) де Li — множина, сформована у зазначений вище спосіб, i = 1, . . ., m . У багатьох алгоритмах комбінаторної оптимізації, на основі яких видається мож- ливим розробка алгоритмів розв’язування сформульованої задачі, використовується поняття сусідства у просторі розв’язків, зо- крема, околів [11] . В даному випадку, якщо є деякий елемент X ∈Ω , для породження сусідніх до нього варіантів можна використати процедури, засновані на таких діях, які зручніше про- ілюструвати з використанням матриці Y, описаної вище: 1) Обмін між собою ненульовими елемен- тами першого стовпчика між двома рядками (відповідає зміні місця старту двох ЛА) . 2) Обмін між собою від’ємними елементами двох рядків (відповідає зміні зон для прийман- ня між двома ЛА) . 3) Обмін між собою двох елементів певного рядка матриці, які відповідають вершинам V . 4) Обмін між собою двох елементів, що відповідають вершинам із V і розташова- ні в різних рядках матриці; при цьому слід окремо опрацьовувати випадки, коли ви- никають або використовуються вироджені фрагменти . 5) Переміщення елемента одного рядка, який відповідає вершині з V, в інший рядок шляхом вставляння в довільне місце між пер- шим елементом і від’ємним елементом . У п . 4 при можливому переміщенні верши- ни з V між рядками можуть виникнути випад- ки, коли: а) виникає вироджений фрагмент (якщо така вершина була єдиною в рядку, з якого пе- реміщується); б) вставляння здійснюється у виродже- ний фрагмент; у першому випадку обну- ляється місце старту і замість номера зони приймання заноситься мінус одиниця як фіктивний номер . У випадку б) для остаточного формування фрагмента слід також розглянути всі можливі варіанти вставляння місць старту, а також но- мерів зон приймання, які можуть це зробити . висновки Виділено два основних типи проблем фор- мування маршрутів ЛА при обстеженні або обслуговуванні заданої множини пунктів на місцевості за наявності групи ЛА, що можуть стартувати та завершувати маршрути в різних місцях . Вперше розглянуто проблему марш- рутизації, у якій ЛА стартують з літака-носія і на ньому ж (або подібному) завершують маршрут . На основі реалістичних припущень, що відо- бражають технічні аспекти процесу, запро- поновано зведення цієї проблеми до спеці- альної задачі комбінаторної оптимізації, яка названа задачею маршрутизації з динамічни- ми депо . Обговорено можливі підходи до її розв’язування на основі використання околів спеціального типу . Подальші дослідження будуть спрямовані на розробку ефективних алгоритмів розв’язу- вання сформульованих задач оптимізації маршрутів ЛА з використанням літака-носія . Цікавим розвитком розглянутих задач є про- блеми кооперації і оптимізації маршрутів ко- манди, що складається як з БПЛА, так і назем- них роботизованих систем [12] . ( ) ,i iT L R≤ iSSN 0130-5395, усим, 2019, № 1 9 Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів REFERENCES 1. Ponda, S.S., Johnson, L.B., Geramifard, A., How, J.P., 2015. "Cooperative mission planning for multi-UAV teams". In Handbook of Unmanned Aerial Vehicles. Dordrecht: Springer, pp. 1447–1490. 2. Austin, R., 2010. Unmanned Aircraft Systems. UAVs Design, Development And Deployment. West Sussex: John Wiley and Sons, 365 p. 3. Tsourdos, A., White, B., Shanmugavel, M., 2011. Cooperative Path Planning of Unmanned Aerial Vehicles. West Sussex: John Wiley and Sons, 212 p. 4. Shima, T., Rasmussen, S., 2009. UAV Cooperative Decision and Control. Challenges and Practical Approaches. Philadelphia: SIAM, 186 p. 5. Toth, P., Vigo, D., 2014. (eds.). Vehicle routing: problems, methods, and applications. Society for Industrial and Applied Mathematics, 462 p. 6. Braekers, K., Ramaekers, K., Nieuwenhuyse, I.V., 2015. "The Vehicle Routing Problem: Stateof the Art Classification and Review". Computers & Industrial Engineering, pp. 300–313. 7. Karakatič, S., Podgorelec, V., 2015. "A survey of genetic algorithms for solving multi depot vehicle routing problem". Applied Soft Computing, 27, pp. 519–532. 8. Hulianytskyi, L.F., Rybalchenko, O.V., 2018. "“Formalizatsiya ta rozv’yazuvannya odnoho typu zadach marshrutyzatsiyi BPLA”. Teoriya optymal'nykh rishen, 17, pp. 107–114. (In Ukrainian). 9. Serhiyenko, I.V., 2010. Metody optymizatsiyi ta systemnoho analizu dlya zadach transobchyslyuval'noyi skladnosti. K.: Akademperiodyka, 318 p. (In Ukrainian). 10. Hulianytskyi, L.F., Riasna, I.I., 2017. "Formalization and classification of combinatorial optimization problems". In Optimization Methods and Applications (eds. Butenko S., Pardalos P. M., Shylo V.). Cham: Springer International Publishing AG, pp. 239–250. 11. Hulianytskyi, L.F., Mulesa, O.Yu., 2016. Prykladni metody kombinatornoyi optymizatsiyi. K.: Vyd.-polihraf. tsentr “Kyyivs'kyy universytet”, 142 p. (In Ukrainian). 12. Arbanas, B. et al., 2018. "Decentralized planning and control for UAV–UGV cooperative teams". Autonomous Robots, 42 (8), pp .1601–1618 . Received 27 .11 .2018 V.P. Horbulin, Academician of the National Academy of Sciences of Ukraine, First Vice-President of the National Academy of Sciences of Ukraine, 54 Volodymyrska Str ., Kyiv-30, 01601, Ukraine, horbulin@nas .gov .ua L.F. Hulianytskyi, Doctor of Technical Sciences, Professor, Head of Department V .M . Glushkov Institute of Cybernetics of NAS of Ukraine, 40 Acad . Glushkova Ave ., 03180, Kyiv, Ukraine, leonhul .icyb@gmail .com I.V. Sergienko, Academician of the National Academy of Sciences of Ukraine, Director V .M . Glushkov Institute of Cybernetics of NAS of Ukraine, 40 Acad . Glushkova Ave ., 03180, Kyiv, Ukraine, incyb@incyb .kiev .ua FORMULATIONS AND MATHEMATICAL MODELS OF THE OPTIMIZING ROUTES PROBLEMS FOR AIRCRAFT WITH DYNAMIC DEPOTS Introduction . In recent years there has been a tendency to expand the use of unmanned vehicles, in particular, unmanned aerial vehicles (UAVs) . In addition to the tasks of routing the aircraft launching from the ground, the problem of routing has recently become topical for the aircraft (UAVs or cruise missiles) that are launched from a special aircraft carrier, the route of which is laid subject to possible restrictions . The problems of finding the optimal routes for a special aircraft group, in particular, UAVs, which can start and complete the route on an aircraft carrier, are considered . Purpose . Analysis and formalization of routing problems of the specified type . Methods . Mathematical models development to find the optimal routes for the aircraft using an aircraft carrier, that are focused on the use of combinatorial optimization methods . 10 iSSN 0130-5395, control systems and computers, 2019, № 1 Горбулін В.П., Гуляницький Л.Ф., Сергієнко І.В. Results . A new mathematical model has been developed for the problems where a given aircraft group, that can start from different launch points and has the ability to complete the route in different places of the aircraft carrier trajectory, has the task to fly over a number of specified objects (points on the ground) with minimizing the total route lengths or flight dura- tion, provided that each object is visited by one and only one aircraft and all objects must be visited . Conclusion . For the first time the problem of routing is considered for the case when aircraft start from an aircraft carrier and finish the route on it . Based on realistic assumptions reflecting the technical aspects of the process, the formalization of this problem is proposed as a special combinatorial optimization problem, which is called the routing problem with dynamic depots . The possible approaches to its solution based on the using the neighborhoods of a special type are discussed . Keywords: unmanned aerial vehicles, route optimization, dynamic depots, mathematical model, combinatorial optimization . В.П. Горбулин, д-р техн . наук, проф ., академик НАН Украины, вице-президент НАН Украины, директор Национального института стратегических исследований, ул . Владимирская, 54, Киев-30, 01601, Украина, horbulin@nas .gov .ua Л.Ф. Гуляницкий, д-р техн . наук, проф ., ст . научный сотрудник, зав . отделом, Институт кибернетики им . В .М . Глушкова НАН Украины, просп . Академика Глушкова, 40, Киев, 03187, Украина, leonhul .icyb@gmail .com И.В. Сергиенко, д-р физ .-мат . наук, проф ., академик НАН Украины, директор института, Институт кибернетики им . В .М . Глушкова НАН Украины, просп . Академика Глушкова, 40, Киев, 03187, Украина, incyb@incyb .kiev .ua ПОСТАНОВКИ И МАТЕМАТИЧЕСКИЕ МОДЕЛИ ПРОБЛЕМ ОПТИМИЗАЦИИ МАРШРУТОВ ЛЕТАТЕЛЬНЫХ АППАРАТOВ С ДИНАМИЧЕСКИМИ ДЕПО Введение . В последнее десятилетие четко обозначилась тенденция к расширению сфер использования беспилот- ных аппаратов, в частности, беспилотных летательных аппаратов (БПЛА) . Кроме задач маршрутизации летатель- ных аппаратов (ЛА), стартующих с земли, приобретают актуальность проблемы маршрутизации в случае, когда летательные аппараты (БПЛА или крылатые ракеты) запускаются со специального самолета-носителя, маршрут которого прокладывается с учетом возможных ограничений . Рассматриваются проблемы поиска оптимальных маршрутов для группы специальных ЛА, в частности, БПЛА, которые могут стартовать и завершать маршрут на самолете-носителе . Цель статьи – анализ и формализация задач маршрутизации указанного типа . Методика . Разработка математических моделей проблем оптимизации поиска оптимальных маршрутов ЛА, выполняющих задачи с использованием самолета-носителя, ориентированных на применение методов комби- наторной оптимизации . Результат . Разработана новая математическая модель проблем, заключающихся в том, что перед заданной группой ЛА, которые могут стартовать с разных точек пуска и имеют возможность заканчивать маршрут в разных местах траектории самолета-носителя, стоит задача облететь ряд заданных объектов (точек на местности) с мини- мизацией суммарной длины маршрутов или длительности полетов при условии, что каждый объект посещается одним и только одним ЛА и все объекты должны быть посещаемыми . Выводы . Впервые рассмотрена проблема маршрутизации, в которой ЛА стартуют с самолета-носителя и на нем же завершают маршрут . На основе реалистичных предположений, отражающих технические аспекты процесса, предложена формализация этой проблемы в виде специальной задачи комбинаторной оптимизации, которая на- звана задачей маршрутизации с динамическими депо . Обсуждены возможные подходы к ее решению на основе использования окрестностей специального типа . Ключевые слова: беспилотные летательные аппараты, оптимизация маршрутов, динамические депо, математиче- ская модель, комбинаторная оптимизация.

Постановки та математичні моделі проблем оптимізації маршрутів літальних апаратів з динамічними депо

Institution

Similar Items