Одна спеціальна задача маршрутизації БПЛА

Метою статт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ї пошуку в них.