Оптимізація маршрутівдля гуманітарного розмінування

Ця наукова стаття вийшла в серпні 2023 року на сайті sciencedirect.com, присвяченому наукам про соціально-економічне планування. Проблема, поставлена в дослідженні, полягає в тому, як знайти оптимальний маршрут для розмінування території, імовірно забрудненої протипіхотними мінами, беручи до уваги безпеку ресурсів гуманітарного розмінування та вартість розмінування.Українська Асоціація Гуманітарного Розмінування взяла на себе переклад статті з англійської для всіх колег по ринку гуманітарного розмінування в Україні. Деякі елементи тексту наводимо у вигляді скріншотів для коректного відображення спеціальних формул, алгоритмів і позначень. Будемо вдячні за згадку першоджерела в українському перекладі (сайт Української Асоціації Гуманітарного Розмінування deminingua.com) при цитуванні матеріалу.

Каролай Камачо-Санчес, Рубен Іє-Пінедо, Джина ГаліндоУніверситет Серхіо Арболеда, Богота, КолумбіяУніверситет дель Норте, Барранкілья, Колумбія

АНОТАЦІЯ: Гуманітарне розмінування – це процес видалення наземних мін із забруднених територій. За цим важким завданням стоїть високий ризик супутньої шкоди для саперів та їхнього обладнання. Внутрішні операційні витрати часто змушують агентів відмовитися від виконання завдання до його завершення, що робить такі райони джерелом ризику, особливо для цивільного населення та біорізноманіття. Більшість досліджень на сьогоднішній день зосереджені на технологічній розробці пристроїв, здатних ефективно виявляти міни у вибраній точці місцевості, в той час як сама стратегія пошуку для прийняття рішення про те, де шукати і яким маршрутом слідувати, є недостатньо вивченою. 
У цій статті пропонується модель підтримки прийняття рішень (МППР), яка дозволяє створювати високонадійні та економічно ефективні плани пошуку мін. Оскільки час обчислення рішення зростає разом із розміром досліджуваної території, для малих і середніх варіантів проблеми пропонуються точні лінійні методи, тоді як для великих пропонується генетичний алгоритм (ГА). Результати показують, що підхід ГА здатний надавати рішення, близькі до оптимальних.

1. ВступНаземні міни є найбільш поширеною зброєю у збройних конфліктах і громадянських війнах в таких країнах, як Колумбія, Афганістан і Сирія, серед інших. Ці вибухові пристрої спричиняють серйозні поранення, часто призводять до ампутації кінцівок або інших форм каліцтва, а також до смерті та значних психологічних травм. Через гостроту цієї проблеми міжнародні комітети, такі як Міжнародний комітет Червоного Хреста (МКЧХ), оголосили наземні міни надзвичайною гуманітарною ситуацією.Відповідно до міжнародного права, виробництво та використання наземних мін суворо заборонено. Незважаючи на цю заборону, за оцінками МКЧХ, щороку понад 26 000 людей гинуть або отримують поранення від наземних мін. Колумбія є однією з країн, які найбільше постраждали від цієї проблеми, посідаючи друге місце за кількістю жертв наземних мін після Афганістану. За даними Колумбійського управління з комплексної боротьби з протипіхотними мінами, з 1990 року було зафіксовано 12 313 жертв протипіхотних мін. Таким чином, протипіхотні міни, встановлені під час минулих і поточних конфліктів, продовжують становити значну загрозу для цивільного населення. Виявлення, ідентифікація та безпечне переміщення цих мін зазвичай називають гуманітарним розмінуванням, і це складне і відповідальне завдання, яке вимагає великих витрат.Питання гуманітарного розмінування часто розглядається виключно через призму розробки роботів-саперів і застосування передових технологій для виявлення мін.Однак ефективне гуманітарне розмінування також вимагає стратегічних, тактичних і оперативних рішень, які можуть бути змодельовані і проаналізовані з точки зору оперативних досліджень. Це включає визначення оптимальної кількості необхідних засобів знешкодження, їх розміщення та розробку планів виявлення та знешкодження мін, серед інших факторів. Важливим і недостатньо дослідженим аспектом гуманітарного розмінування є мінімізація ризику для саперів. Наслідки для людей-саперів є серйозними, включаючи можливість каліцтва або смерті, в той час як оператори розмінування стикаються із ризиком пошкодження від детонації мін, що може призвести до затримок і додаткових витрат. Ці фактори часто призводять до того, що місії з розмінування залишаються незавершеними, залишаючи постраждалі райони небезпечними і невідновленими. Неповне розмінування становить ризик для цивільного населення, яке може помилково вважати територію безпечною, що збільшує ймовірність випадкової активації мін.У цій статті ми пропонуємо двоцільову модель змішаного цілочисельного програмування (MIP), яка одночасно мінімізує операційні витрати та мінімізує ризик для агентів. Решта цієї статті організована наступним чином: у Розділі 2 представлено наш огляд літератури. В Розділі 3 описано нашу постановку задачі. Розділ 4 містить формулювання нашої моделі. В Розділі 5 методологія на основі генетичного алгоритму (ГА). В Розділі 6 представлено звіт про загальні результати. Нарешті, у Розділі 7 представлено наші висновки та майбутні напрямки досліджень.

2. Огляд літературиУ літературі проблемі гуманітарного розмінування присвячено кілька робіт. Більшість з них зосереджені на підвищенні точності виявлення наземних мін шляхом розробки надійних технологій. У зв'язку з цим було проведено широкі дослідження з розробки, випробування та вдосконалення роботизованих пристроїв для виявлення протипіхотних мін [2–11]. Такі роботизовані пристрої зазвичай повинні пересуватися по землі, для чого їм потрібна стійкість і пристосованість до різних типів ґрунту. Для виявлення наземних мін також розглядаються георадари (GPR) [12–16]. Георадарна технологія використовує випромінювання та прийом електромагнітних хвиль для виявлення захованих під землею об'єктів [17–19]. Інші методи включають використання розпізнавання зображень [20–22], ольфакторних сенсорів [23,24] та глибокого навчання [25]. Посилання [26,27] пропонують цікавий аналіз завдань, пов'язаних з гуманітарним розмінуванням та пов'язаними з ним технологіями. Ці завдання включають розробку економічно ефективних технологій, які можуть адаптуватися до місцевості, надійних і точних методів розмінування, а також підвищення безпеки засобів розмінування, тощо.Одне з питань, що виникають під час гуманітарного розмінування, полягає в тому, як визначити пріоритетність зон, що підлягають розмінуванню [28,29]. У посиланні [28] методи географічних інформаційних систем (ГІС) використовуються для картування мінної небезпеки на різних типах територій (наприклад, ліси, муніципалітети, водні ресурси). Потім ця інформація подається в систему підтримки прийняття рішень (СППР), яка використовує багатокритеріальний аналіз для визначення пріоритетності районів для проведення операцій з розмінування. Аналогічно, [29] пропонує СППР, яка враховує вплив, ймовірність небезпеки та інші фактори для визначення пріоритетності дій з гуманітарного розмінування. Розширенням [28] є робота [30], в якій представлено веб-орієнтовану СППР для операцій з гуманітарного розмінування та відновлення забруднених мінами територій. Пов'язану роботу, присвячену картографуванню мінної небезпеки, наведено в [31], де пропонується порівняння просторових і непросторових моделей логістичної регресії для картографування мінної небезпеки з метою визначення пріоритетності районів мінної небезпеки. Необхідність визначення пріоритетності замінованих територій зумовлена насамперед фінансовими обмеженнями та обмеженими можливостями.З більш оперативної точки зору, деякі з найпоширеніших рішень в гуманітарному розмінуванні стосуються координації засобів розмінування та планування маршрутів. В посиланні [32] представлено алгоритм планування переміщення для сканування, виявлення та знешкодження мін. У своєму підході автори використовують криві та шляхи Дубінса для покриття всієї площі мінного поля. Схожу роботу наведено в [33], де представлено підхід до планування шляху для агента з розмінування, щоб автономно досягти повного покриття мінного поля.Важливою і ще недостатньо дослідженою проблемою в цій галузі є розробка економічно ефективних стратегій пошуку мін [26]. Одне з небагатьох досліджень, присвячених цьому питанню, представлено в посиланні [34], в якому пропонується модель прийняття рішень для управління автономними ресурсами очищення. У [34], ресурси розмінування завжди рухаються в напрямку з найбільшою ймовірністю знайти міну. Пов'язану роботу наведено в [35], яка порівнює повне та вибіркове покриття для переміщення засобів виявлення мін і включає випадок імовірнісного покриття, коли апріорні ймовірності присутності мін є доступними. У посиланні [36] порівнюється набір стратегій пошуку, включаючи випадкові переміщення, роїння та естафетну кластеризацію, серед інших, в умовах захаращеного перешкодами двовимірного простору. Однак, наскільки нам відомо, попередні дослідження в цій галузі не розглядали безпеку засобів розмінування. Це особливо актуально у випадках, коли ресурси для розмінування є людськими. Це також актуально при використанні роботизованих пристроїв, щоб уникнути пошкодження обладнання та додаткових витрат.
У цій статті ми представляємо двоцільову модель оптимізації для пошуку мін, яка спрямована на досягнення двох цілей: (1) мінімізувати операційні витрати та (2) оптимізувати індекс безпечної доступності (ІБД) всіх засобів розмінування. Ми пропонуємо метод лінеаризації для другої цілі, яка є нелінійною, що робить її вирішуваною за допомогою інструментів лінійного програмування. Цей підхід є унікальним внеском в існуючу літературу, оскільки така функція раніше не розглядалася. Крім того, у запропонованому формулюванні ми включаємо кілька типів технологій розмінування та гарантуємо, що кожна зона очищується лише один раз за допомогою однієї технології, щоб мінімізувати ризик, пов'язаний з переміщенням декількох операторів і технологій в одній зоні.

3. Опис проблемиПроблема, поставлена в цьому дослідженні, полягає в тому, як знайти оптимальний маршрут для розмінування території, імовірно забрудненої протипіхотними мінами, беручи до уваги безпеку ресурсів гуманітарного розмінування та вартість розмінування. Для спрощення проєктування пошукових маршрутів ми припускаємо, без порушення загальності, що область пошуку вписана в правильну фігуру, яка складається з менших квадратів розміром 1 метр в довжину і 5 метрів в глибину. Ця робота робить значний внесок у забезпечення безпеки ресурсів розмінування, пропонуючи Індекс безпечної доступності (ІБД).ІБД призначений для кількісної оцінки рівня небезпеки, на яку наражаються ресурси під час місії з розмінування. У зв'язку з цим у нашому підході квадрат вважається безпечнішим для розмінування, якщо його сусідні ділянки вже були розміновані. Це пов'язано з тим, що за відсутності сусідніх чистих квадратів вузький доступний простір для маневрів розмінування може призвести до випадкової детонації. Тому ми визначаємо ІБД для квадранта i на основі стану (чистий чи забруднений) сусідніх квадратів.
Щоб надати більш зрозуміле пояснення, розглянемо ситуацію, зображену на Рис. 1, де червоні квадрати позначають імовірно забруднені зони, тоді як зелені квадрати позначають зони, які вже були очищені. Квадрат, який нас цікавить, позначений синім кольором і хрестиком. На Рис. 1(a) розрахунок ІБД для синього квадрата прямо пропорційний кількості червоних квадратів, відмічених зірочкою (всього 3). У цьому випадку агент розмінування повинен бути обережним під час руху на північ, схід і захід. На Рис. 1(b), два квадрати вже очищено, тому на розрахунок ІБД для синього квадрата впливає лише червоний квадрант, позначений зірочкою *. У цьому другому сценарії оператор може вільно переміщатися на схід і на захід, оскільки ці райони вже були очищені раніше. Зрозуміло, що ситуація на Рис. 1(b) є більш бажаною. Значення ІБД є динамічним і змінюється при кожному очищенні квадрата. Тому значення ІБД для всіх сусідніх ділянок має бути перераховане. Зауважте, що ІБД не має на меті вимірювати ризик з точки зору ймовірності настання будь-якої конкретної події, а також не охоплює всі елементи, які можуть прямо чи опосередковано впливати на цю ймовірність.На практиці існує декілька ресурсів для виявлення та знешкодження наземних мін. Ці ресурси можна умовно поділити на дві категорії: наземні та повітряні технології. Кожен тип ресурсу має специфічні вимоги до використання. Наприклад, розглянемо очищення внутрішньої території, яка тут визначається як квадрат, де сусідні квадрати вважаються забрудненими, оскільки вони не були очищені в попередні періоди.У цьому випадку повітряні технології можна використовувати без необхідності очищення прилеглих територій, як показано на Рис. 2(a).На противагу цьому, наземні технології вимагають попередньо розчищеного шляху, як показано на рисунку. Рис. 2(b). Операційні витрати, пов'язані з кожним технологічним режимом, можуть відрізнятися, причому повітряне очищення, як правило, дорожче через такі фактори, як години використання, акумулятори, паливо, технічне обслуговування та інші супутні витрати.Мета запропонованого нами підходу полягає в тому, щоб знайти оптимальний маршрут для наявних наземних і повітряних агентів (ресурсів) для ефективного очищення всієї території при оптимізації безпеки (мінімізації загального ІБД) агентів і мінімізації загальних витрат. У наступному розділі наведено математичне формулювання задачі.

4. Математичне формулюванняДля нашої математичної моделі ми розглядаємо наступні припущення:1. Вважається, що розподіл, пов'язаний з кількістю та розташуванням мін, невідомий. Також припускається, що будь-який квадрат, який не було очищено, ймовірно, замінований.2. Наш підхід поділяє засоби розмінування на дві категорії: повітряні (𝐾𝐴) та наземні (𝐾𝑇).Це допускає кілька типів технологій очищення, кожна з яких має різну вартість і вимоги до користувача. Наприклад, використання дронів не вимагає очищення прилеглих територій, тоді як використання детекторів гамма-випромінювання вимагає чистої території для їх застосування. Як повітряні, так і наземні агенти здатні очистити будь-які квадрати.3. Передбачається, що агенти пересуваються обережно, щоб уникнути ризику випадкової детонації мін. Тому розумно припустити, що переміщення агентів відбувається без зіткнень.4. До кожного квадрата можна призначити лише один засіб розмінування.5. Всі квадрати мають однакові розміри (1м 𝑥 5м) [37]. Кількість квадратів є вхідним параметром моделі.6. Після того, як у певному квадраті розпочато очищення за певною технологією, воно має бути завершене без перерви7. Наявні технології спочатку будуть розташовані за межами забрудненої території.8. Час очищення для кожної технології є заздалегідь визначеним параметром.9. Ефективність засобів розмінування вважається 100%, тобто якщо квадрат був очищений за допомогою засобу, то він вважається вільним від мін.
4.1. ПозначенняПозначення, що використовуються для формулювання задачі, визначаються наступним чином:

4.2.2. ОбмеженняНа рівняння (3) та (6) накладено ряд обмежень, представлених нижче.Обмеження (7)–(17) відносяться до балансу руху ресурсів у замінованому квадраті і гарантують безперервний потік для доступних ресурсів у всьому квадраті, з моменту початку очищення і до його завершення.

5. Оптимізація маршрутів для гуманітарного розмінуванняНаше обчислювальне рішення використовує алгоритм Strength Pareto Evolutionary Algorithm (SPEA) II в якості ядра. Цей алгоритм включає в себе елітарність, що означає, що найкращі рішення покоління передаються наступному поколінню і відомі як елітарна популяція. Мета алгоритму – визначити оптимальний розподіл квадратів для кожної технології. Початкова популяція генерується випадковим чином, де випадковий розв'язок складається з двох цілочисельних векторів розміром |N|.Перший вектор (вектор положення) – це послідовність випадкових чисел від 1 до |N|, а другий вектор є послідовністю випадкових чисел від 1 до |K|. Нарешті, стандартні операції еволюційних алгоритмів, а саме кросинговер і мутація, використовуються для створення нової популяції.Рішення про використання ГА, зокрема SPEA II, ґрунтувалося на його доведеній ефективності у вирішенні задач комбінаторної оптимізації, таких як маршрутизація транспортних засобів та задачі комівояжера. Ці проблеми мають певну схожість з проблемою розмінування, яка передбачає пошук оптимального маршруту для саперів, щоб очистити мінне поле, мінімізуючи при цьому час, необхідний для очищення території, і зменшуючи ризик нещасних випадків.SPEA II – це багатоцільовий алгоритм оптимізації, що означає, що він може працювати з декількома конфліктуючими цілями, що особливо важливо для проблеми розмінування, де безпека та ефективність є критично важливими факторами. Крім того, оскільки SPEA II не допускає елітарності, він забезпечує збереження найкращих рішень кожного покоління, запобігаючи втраті цінної інформації та підтримуючи різноманітність у популяції, що призводить до кращої конвергенції та більш точних рішень [38]. Тому, хоча існують й інші метаевристичні підходи, які можуть бути використані для вирішення проблеми гуманітарного розмінування, SPEA II було обрано завдяки його перевіреному досвіду успішного вирішення різних оптимізаційних задач і здатності вирішувати численні завдання та підтримувати різноманітність у популяції.Також були розглянуті інші традиційні методи, в тому числі як точні алгоритми, так і евристичні підходи. Однак ці методи можуть не підходити для складності та обмежень проблеми розмінування. Точні алгоритми можуть страждати від проблеми розмірності і ставати обчислювально нерозв'язними для великих випадків, в той час як евристичні підходи можуть бути не в змозі забезпечити оптимальні рішення або ефективно впоратися з декількома цілями і обмеженнями.Крім того, для досягнення задовільних результатів ці методи можуть вимагати значних знань предметної області та налаштування під конкретну проблему [39]. Тому ми вирішили використовувати ГА-підхід на основі SPEA II, який продемонстрував чудову продуктивність і надійність у різних задачах комбінаторної оптимізації, в тому числі з декількома цілями та обмеженнями [38,40].Крім того, як зазначено в посиланні [41], ГА є простими в реалізації, а їх складність залежить від вибору параметрів. Таким чином, дуже важливо розробити добре підібрану структуру хромосом, яка дозволить скоротити час обчислень без шкоди для якості рішення. У наступних розділах наведено детальну інформацію про структуру хромосом, що використовується в нашому ГА, а також псевдокод і команди обробки, які необхідно виконати.

5.1. Представлення хромосом та початкова популяціяКожне рішення (хромосома) представлено двома цілочисельними векторами: перший вектор містить призначення доступного квадрата, який потрібно очистити, а другий – відповідну технологію очищення. Така схема представлення забезпечує реалістичність рішень, полегшуючи застосування операторів кросинговеру та мутації і підвищуючи ефективність роботи ГА, скорочуючи таким чином час обчислень.Пояснюючи далі, перший вектор складається з чисел від 1 до кількості квадратів (|N|). Це число представляє призначений доступний квадрат. В цьому випадку слово "доступний" означає, що квадрат можна буде досягти за допомогою наявної технології очищення в найближчий період часу, який вказано в другому векторі.Для ілюстрації припустимо, що Рис. 3 є графічним зображенням забрудненої території, яка містить 9 квадратів. Далі припустимо, що є 3 технології, включаючи дві наземні (T1 і T2) і одну повітряну (T3). Легко помітити, що для наземних технологій доступні всі квадрати, крім номера 5.На основі Рис. 3, можна визначити список доступних квадратів для першого призначення кожного типу технології наступним чином:Розглянемо випадкову хромосому для ситуації, зображеної на Рис. 3, яка наведена на Рис. 5.З другого вектора на Рис. 5, першою призначеною технологією є Т2, яка є наземною технологією. Таким чином, призначений квадрат буде обрано з наземного вектора на Рис. 4. З першого вектора на Рис. 5, видно, що був призначений четвертий доступний квадрат. На Рис. 6 (нижче) наочно показано перше розподілення. Оскільки квадрат 4 знаходиться на четвертій позиції в наземному векторі, він був віднесений до Т2, як показано зеленим кольором на зображенні. Тепер квадрат 5 стає доступним. Крім того, квадрат 4 буде вилучено зі списку всіх квадратів, оскільки його вже було очищено.

З другого вектора на Рис. 5, можна помітити, що другою призначеною технологією є Т3, яка є повітряною технологією, тому призначений квадрат буде обраний з повітряного вектора на Рис. 7. З першого вектора на Рис. 5 можна помітити, що був призначений дев'ятий доступний квадрат. Однак з Рис. 7 ми бачимо, що доступними є лише вісім квадрантів. Таким чином, підрахунок буде виконуватися циклічно, щоб призначити квадрат. На Рис. 8 графічно представлено це друге призначення, виділене зеленим кольором на зображенні. (Див.Рис. 9 та 11).

Тепер квадрат 1 вилучено з кожного списку, тому доступні вектори квадратів модифіковано наступним чином:Третє призначення полягає в наступному (див Рис. 10).Дотримуючись тієї ж логіки, в кінці ми отримаємо наступне призначення:Відсортоване призначення показано Рис. 12.Оскільки хромосоми сконструйовані так, щоб завжди генерувати можливі рішення, процес випадкового створення хромосом стає надзвичайно простим.

5.2. Функція пристосованостіМи визначаємо пристосованість як функцію "сприйнятої корисності" хромосоми. У цьому конкретному випадку пристосованість є нормованою адитивною функцією (вартість + ІБД), що вимагає обчислення вартості та значення ІБД кожного рішення. Розрахунок вартості наведено в Алгоритмі 2. Цей алгоритм проходить через вектор призначення технологій і підсумовує вартість індивідуального використання кожної з технологій, що з'являються у векторі.

При обчисленні значення ІБД хромосоми важливо враховувати, що деяким технологіям може бути призначений квадрат, який не є легкодоступним. Наприклад, розглянемо ситуацію, зображену на Рис. 3, з двома наземними технологіями, T1 і T2.Припустимо, що час очищення дорівнює одиниці часу. Тепер проаналізуємо наступні рандомні призначення, пов'язані з рандомною хромосомою:● T1: 1-2-3-4-8-9● T2: 5-6-7Перше призначення для T2 – квадрат 5, який не доступний по землі в нульовий момент часу. У цьому випадку T2 повинен зачекати, поки T1 закінчить очищення квадратів 1 і 2, щоб почати очищення квадрата 5. Щоб краще це зрозуміти, побудуємо діаграми Ганта для періодів часу від 0 до 2, як показано на Рис. 13–15. Числа на червоному позначають можливі квадрати для очищення на кожному кроці, а вектор внизу показує, чи є квадрат доступним (Acc), недоступним (No. Acc), або вже очищеним (Cln).

• Час = 0-1   – T1: 1-2-3-4-8-9   – T2: 5-6-7• Час = 1-2   – T1: 1-2-3-4-8-9   – T2: 5-6-7• Час = 2-3   – T1: 1-2-3-4-8-9   – T2: 5-6-7Як видно з діаграми Ганта, в моменти часу 0 і 1 квадрат 5 є недоступним, а Т2 не використовується. Лише в момент часу 2 квадрат 5 стає доступним, і Т2 може почати його очищення.На Рис. 16 показано розподіл для решти періодів часу, коли доступні всі квадрати.• Час = 3-6   – T1: 1-2-3-4-8-9   – T2: 5-6-7Щоразу, коли технологія починає очищати квадрант, його ІБД накопичується. Аналогічно, кожного разу, коли квадрат очищується, ІБД всієї мережі оновлюється. Алгоритм обчислення ІБД наступний:

В алгоритмі 3 рядки з 1 по 8 представляють необхідні вхідні дані для розрахунку загального ІБД конкретного рішення. Цикл з передумовою в рядку 10 представляє цикл, який буде продовжуватися до тих пір, поки не будуть призначені всі квадрати. Рядки з 11 по 13, повторити для кожної технології, яка все ще має нерозподілені квадрати у своєму призначенні, і наступний квадрант є доступним. Рядки 14-15, очистити квадрат і накопичити загальний ІБД. У рядках 16-17 виконується повторення для кожного квадрата, суміжного з щойно очищеним, і оновлюється значення ІБД (ІБД зменшується на 𝛽). Нарешті, рядки з 21 по 25 оновлюють наступний призначуваний квадра.т Якщо це остання перевірка для цієї технології, технологія позначається як така, що непідлягає повторній перевірці.Рядки 30-32 перевіряють, чи всі квадрати було очищено, і завершують цикл. Важливо зазначити, що наш алгоритм обчислення ІБД працює для будь-якогоелемента в області допустимих рішень. Однак конструкція нашої хромосоми не дозволяє технології чекати більше двох одиниць часу, щоб виконати очищення (Розділ 5.1).

5.3. КросинговерНаш алгоритм рандомно вибирає дві батьківські хромосоми з підмножини індивідів для створення нової дочірньої хромосоми і працює наступним чином (Див. Рис. 17):● Крок 1. Рандомно обираємо хромосому на основі пристосованості (батьківська 1).● Крок 2. Рандомно обираємо хромосому на основі пристосованості (батьківська 2).● Крок 3. Обираємо вектор квадрата батьківської хромосоми 1, копіюючи цю послідовність у відповідну позицію для побудови вектора квадрата дочірньої хромосоми 1.● Крок 4. Виділяємо вектор технологій батьківської хромосоми 2, копіюючи цю послідовність у відповідні позиції, для побудови вектора технологій дочірньої хромосоми 1.● Крок 5. Обираємо вектор квадрата батьківської хромосоми 2, копіюючи цю послідовність у тих самих відповідних позиціях, щоб побудувати вектор квадрата дочірньої хромосоми 2.● Крок 6. Обираємо вектор технологій батьківської хромосоми 1, копіюючи цю послідовність у відповідних позиціях для побудови вектора технологій дочірньої хромосоми 2.

5.4. МутаціяОперація мутації використовується для модифікації структури особин. Наш підхід використовує чотири процеси мутації, а саме:Мутація 1● Крок 1. Рандомно обираємо дві позиції вектора квадрата обраної хромосоми.● Крок 2. Рандомно переставляємо квадрати між двома позиціями, обраними на кроці 1, щоб згенерувати дочірню хромосому.● Крок 3. Дочірня хромосома успадковує вектор технології без будь-яких змін.Мутація 2Ця техніка мутації схожа на мутацію 1, але замість того, щоб змінювати вектор квадрата, зміни вносяться у вектор технології. Вектор квадрата залишають незмінним для створення нової хромосоми.Мутація 3Знову ж таки, ця техніка мутації подібна до мутацій 1 і 2, але в цьому випадку і вектор квадрата, і вектор технології змінюють місцями свої елементи.Мутація 4Цей процес мутації досліджує нові призначення для вектора технологій, що потенційно може призвести до більш збалансованих рішень, де технології призначаються таким чином, щоб сприяти розподілу квадратів.● Крок 1. Рандомно обираємо дві позиції у векторі технології обраної хромосоми.● Крок 2. Виключаємо елементи у підвекторі вектора технологій між позиціями з кроку 1.● Крок 3. Рандомно переносимо технології назад до підвектора для отримання дочірньої хромосоми.● Крок 4. Залишаємо вектор квадранта незмінним, щоб створити дочірню хромосому.
На Рис. 18 показано приклади запропонованих мутаційних процесів. Сірими клітинками показано рандомні мутації, що виникли на обраній хромосомі.

5.4.1. Нова популяціяНова популяція складається з наступних рішень:● Елітна популяція.● Потомство кросинговера.● Мутовані хромосоми.● Хромосоми, що вижили.● Іммігранти.Елітна популяція визначається шляхом застосування суворого правила домінування, що означає, що хромосома домінує над іншою тільки тоді, коли вона перевершує її в одній з двох цілей і, принаймні, рівна (або краща) в іншій (Вартість та ІБД). Хромосоми, що вижили, відносяться до елементів, відібраних рандомно з попередньої популяції, в той час як елементи-іммігранти – це новостворені елементи, відібрані рандомно.
5.5. Аналіз параметрів ГАДля налаштування параметрів ГА ми провели серію експериментів із метою покращення обчислювального часу, необхідного для досягнення найкращого з відомих розв'язків для множинних рандомних задач.Експерименти складалися з трьох етапів.На кроці 1 ми зафіксували розмір області i = 16, 25, 36 і 49, і рандомно згенерували 30 екземплярів з варіаціями кількості кожного типу технологій, вартості, серед іншого. Потім ми застосували суперевристичний підхід на кроці 2, де ми запустили ГА з перебільшеними параметрами, включаючи ймовірність мутацій та кросинговеру 20% та розмір популяції 500. ГА припинявся лише тоді, коли протягом 100 безперервних поколінь не спостерігалося покращення рішення. Такий підхід дозволив нам знайти еталонне значення для оптимального рішення.На кроці 3 ми змінювали ймовірність мутації (Pm) від 10% до 70% з інтервалом у 20 пунктів, а ймовірність кросинговеру (Pc) - від 10% до 40% з інтервалом у 10 пунктів (щоб підтримувати постійну чисельність популяції, ми переконалися, що 𝑃 𝑚+2 ∗ 𝑃 𝑐 < 1). Потім ми запустили кожен з 30 екземплярів для кожної можливої комбінації Pm і Pc, поки не досягли еталонного значення, отриманого на кроці 2. Нарешті, ми обчислили середню кількість поколінь для 30 запусків для кожної конфігурації. На Рис. 19 (a) показано результати цих експериментів.Виходячи з результатів, показаних на Рис. 19 (а), ми вирішили оцінити значення Pm та Pc для фіксованої кількості поколінь (50), використовуючи найкращі конфігурації, отримані під час попередніх експериментів, а саме Pm = 0.3 та Pc = 0.2, Pm = 0.5 та Pc = 0.2, Pm = 0.1 та Pc = 0.3, Pm = 0.3 та Pc = 0.3, та Pm = 0.1 та Pc = 0.4.
На Рис. 19 (b) показано фронти Парето, знайдені для кожної конфігурації (Pc, Pm) для фіксованої задачі з розміром 49 та 50 ітерацій. Для того, щоб побачити, як далеко розв'язки знаходяться від оптимального значення, ми вирішили послабити задачу, використавши функцію пристосованості як сингулярну цільову функцію та розв'язавши її за допомогою CPLEX (оскільки ми використовуємо єдину цільову функцію, модель CPLEX дає лише один розв'язок). Для цього конкретного випадку задачі ми знайшли розв'язок у (7863, 103). Саме ця точка була частиною критерію Парето для Pm = 30% і Pc = 30%.На Рис. 19 показано, що Pm 30% і Pc 30% швидше приводять нас до кращих рішень.У наступному розділі наведено результати застосування запропонованого підходу з налаштованими параметрами до чисельних експериментів.

6. Обчислювальний досвідУ цьому розділі представлено результати наших обчислювальних експериментів для кількох сценаріїв. Також у цьому розділі ми порівнюємо продуктивність запропонованого нами алгоритму ГА та CPLEX. Оскільки, наскільки нам відомо, конкретна проблема гуманітарного розмінування, що розглядається в цьому документі, раніше не вирішувалася, немає жодних додаткових еталонних або базових підходів для порівняння. Незважаючи на брак доступної інформації, ми вважаємо, що наш підхід і результати є значним внеском у сферу гуманітарного розмінування, і потенційно можуть слугувати орієнтиром для майбутніх досліджень і практичних дій у цій галузі.
6.1. Генерування проблемиДля нашого обчислювального експерименту ми зосередимося на забрудненій ділянці, яку задано прямокутником. Проблема характеризується кількістю квадратів, на які поділена основна територія, та кількістю доступних технологій для процесу очищення. У нашій моделі ми призначаємо фіксовані витрати на використання наземних технологій та фіксовані витрати на використання повітряних технологій. Крім того, ми припускаємо, що вартість повітряних технологій є вищою, ніж вартість наземних технологій. Час, необхідний для очищення певної площі, вважається однаковим для кожного типу технології.
6.2. РезультатиРозв'язність моделі оцінюється за допомогою IBM ILOG CPLEX 12.6.0 на ноутбуці з процесором Intel(R) Core(TM) i5-6200U 2.30 ГГц, 8 ГБ встановленої оперативної пам'яті (7.89 ГБ корисної), 64-розрядною операційною системою, процесором x64 та Windows 10. Набори даних було створено для кожного сценарію шляхом випадкової генерації ознак.Малі та середні варіанти складалися з 9-49 квадратів і запускалися за допомогою оптимізатора CPLEX, тоді як великі варіанти включали сценарії з 64-900 квадратів і запускалися за допомогою Python.Було зафіксовано час розв'язання для кожного сценарію, а результати наведено в Таблиці 1.Експерименти починаються з невеликої області (9 квадратів) і поступово збільшують кількість квадратів до тих пір, поки оптимізатор CPLEX не зможе знайти рішення. Помічено, що CPLEX добре працює для малих і середніх варіантів. Для порівняння результатів було запущено ГА зі 100 реплікаціями для кожного сценарію. У Таблиці 1 порівнюються результати експериментів за трьома критеріями: значення ІБД, вартість очищення та час розв'язання. Часрозв'язання для кожного сценарію розраховувався як середній час 10 ітерацій для фіксованої кількості квадратів та ресурсів очищення.

У цільовій функції 2 видно, що модель приймає рішення про використання лише наземних технологій, коли доступними є як наземні, так і повітряні технології, оскільки вважається, що перші є менш витратними.Варто зазначити, що час розв'язку зростає зі збільшенням кількості квадратів, але збільшення часу розв'язку для ГА значно менше порівняно з оптимізатором CPLEX. Таким чином, ГА виявляється значно ефективнішим за CPLEX з точки зору часу виконання. Однак якість рішень, про які повідомляє CPLEX, або дорівнює, або є кращою за рішення, отримані ГА. У всіх сценаріях ГА зміг отримати оптимальний розв'язок для двох цільових функцій на всіх ітераціях.Важливо зазначити, що подібні тенденції спостерігалися і в менших випадках, коли розглядалися лише наявні наземні технології. Для цільової функції 1 ГА зміг знайти оптимальний розв'язок на всіх 100 ітераціях для сценаріїв з 9 та 16 ділянками . Для сценарію з 25 областями оптимальний розв'язок не було отримано за 3 прогони, при цьому результати відрізнялися від еталонного значення лише на 0,02%. Аналогічно, для сценарію з 36 ділянками оптимальний розв'язок не було отримано в 7 прогонах, при цьому результати відрізнялися від еталонного значення на 0,02%. Для сценарію на 79 ділянок оптимальний розв'язок не було отримано в 5 прогонах, при цьому результати відрізнялися від еталонного значення лише на 0,02%. З іншого боку, для цільової функції 2 (вартість) ГА зміг забезпечити оптимальний розв'язок у всіх сценаріях.
Враховуючи, що оцінка запропонованої метаевристики є сприятливою з точки зору надійності, було проведено експерименти для більших сценаріїв. Результати узагальнено на Рис. 20, з якого видно, що складність задачі за часом є лінійною. Ми побудували графіки часу виконання для декількох сценаріїв, як показано на Рис. 21 (a) та 21 (b).Можна зробити висновок, що час виконання зростає зі збільшенням розміру задачі, особливо коли збільшується кількість доступних технологій, оскільки це пов'язано з більшою кількістю призначень, як показано на рисунку.Результати багатоцільової оптимізації, де обидві цілі мінімізуються, зображено на Рис. 21 (c). Фронти Парето було згенеровано з використанням найкращих розв'язків, отриманих з точної моделі та ГА для 9-квадратної зони.

На рисунку видно, що точна модель домінує над результатами, отриманими за допомогою ГА, оскільки вона генерує рішення з нижчим ІБД та меншими витратами порівняно з усіма рішеннями ГА. Однак, як показано на Рис. 21 (c), якість розв'язків, наданих ГА, близька до якості розв'язків, наданих CPLEX, тоді як різниця у часі розв'язку, що спостерігається на Рис. 21 (a), є значно більшою. Таким чином, можна зробити висновок, що запропонований ГА є більш ефективним, ніж CPLEX у вирішенні поставленої задачі. Крім того, обчислювальні обмеження CPLEX є більш жорсткими, ніж для запропонованого ГА.

7. Висновки
У цій статті ми пропонуємо математичну модель для оптимізації послідовності розмінування для кожного доступного ресурсу при проведенні заходів з гуманітарного розмінування. Найбільш характерною особливістю цієї роботи є те, що вона розглядає безпеку ресурсів розмінування як одну з головних цілей. Запропонована нами модель включає нелінійну цільову функцію, яку ми лінеаризуємо за допомогою змінної, що гарантує, що цільова функція мінімізує ІБД.Це дозволяє розв'язати проблему за допомогою інструментів лінійного програмування, що є додатковим внеском у це дослідження, оскільки такий тип функції не зустрічається в оглянутій літературі. Порівняно з попередніми дослідженнями в літературі, наш підхід зосереджений на оптимізації безпечного логістичного управління ресурсами, доступними для діяльності з розмінування, а не на технологічних питаннях. Зокрема, наш підхід використовує перспективу оптимізації для вирішення проблеми гуманітарного розмінування за допомогою багатоцільової моделі змішаного цілочисельного програмування
Для вирішення великих випадків нашої задачі ми пропонуємо реалізацію алгоритму SPEA II. Ми розробили відповідні хромосоми, функції кросинговеру та мутацій. Хоча для порівняння запропонованих нами методів бракує реальних даних з попередніх досліджень, ми перевірили продуктивність запропонованої моделі за допомогою комп'ютерних експериментів, які дали узгоджені результати.Рішення, отримані за допомогою запропонованої моделі, виявляють цікаві закономірності поведінки різних технологій розмінування. Зокрема, ми помітили, що наземні технології, як правило, демонструють більш скупу поведінкову різноманітність, надаючи перевагу очищенню квадратів з меншим ІБД. Це дає цінну інформацію для розробки більш ефективних евристик з меншим простором рішень. На противагу цьому, технології з повітряним управлінням демонструють дещо складнішу поведінку, надаючи пріоритет зачистці квадратів, які призводять до більшого зниження рівня ІБД на прилеглій території, забезпечуючи при цьому зв'язність очищеної території. Така поведінка свідчить про те, що евристика декомпозиції, яка відокремлює виділення технологій, керованих і не керованих людиною, може бути більш ефективним підходом для вирішення більших випадків проблемиВ якості майбутніх напрямків досліджень ми пропонуємо розглянути додаткові реалістичні параметри, такі як бюджети та пріоритети очищення, специфікації технологій та ймовірність невдач. Крім того, слід розробити детальне дослідження для визначення індексу небезпеки, пов'язаного з очищенням територій, забруднених наземними мінами. Цей показник має ґрунтуватися на ефективності використовуваних технологій і включати повторюваність розмінування для поліпшення показників безпеки.

Заява про авторський внесок CRediTКаролай Камачо-Санчес: концепція та дизайн дослідження, аналіз та/або інтерпретація даних, написання оригінального тексту, рецензування та редагування. Рубен Іє-Пінедо: концепція та дизайн дослідження, аналіз та/або інтерпретація даних, написання оригінального тексту, рецензування та редагування. Джина Галіндо: аналіз та/або інтерпретація даних, написання - оригінальний проект, написання - рецензування та редагування.References[1] Killers Hidden. The global landmine crisis. Washington, DC; 1998, p. 4.[2] Nonami K. Humanitarian mine detection six-legged walking robot. In: Proc. of the third int. conf. on climbing and walking robots. 2000.[3] Wettergreen David Strod. Robotic walking in natural terrain: Gait planning and behavior-based control for statically-stable walking robots. 1996.[4] Portugal David, Marques Lino, Armada Manuel. Deploying field robots for humanitarian demining: Challenges, requirements and research trends. In: Mobile service robotics. World Scientific; 2014, p. 649–56.[5] Cobano Jose A, Estremera Joaquin, de Santos P Gonzalez. Accurate tracking of legged robots on natural terrain. Auton Robots 2010;28(2):231.[6] Colon Eric, Hong Ping, Habumuremyi Jean-Claude, Doroftei Ioan, Baudoin Yvan, Shali Hichem, et al. An integrated robotic system for antipersonnel mines detection. Control Eng Pract 2002;10(11):1283–91.[7] De Santos P Gonzalez, Cobano José A, Garcia E, Estremera J, Armada MA. A six-legged robot-based system for humanitarian demining missions. Mechatronics 2007;17(8):417–30.[8] Freese Marc, Matsuzawa Toshiaki, Oishi Yasuhiro, Debenest Paulo, Takita Kensuke, Fukushima Edwardo F, et al. Robotics-assisted demining with gryphon. Adv Robot 2007;21(15):1763–86.[9] Gonzalez de Santos* Pablo, Garcia Elena, Estremera Joaquin, Armada Manuel A. DYLEMA: Using walking robots for landmine detection and location. Internat J Systems Sci 2005;36(9):545–58.[10] Kato Keisuke, Hirose Shigeo. Development of the quadruped walking robot, TITAN-IX—mechanical design concept and application for the humanitarian de-mining robot. Adv Robot 2001;15(2):191–204.[11] Baer C, Musch T, Schulz C, Rolfes I. A polarimetrie, low ringing UWB antenna for ground penetrating radar operation. In: 2016 IEEE international symposium on antennas and propagation. IEEE; 2016, p. 2121–2.[12] Potin Delphine, Duflos Emmanuel, Vanheeghe Philippe. Landmines groundpenetrating radar signal enhancement by digital filtering. IEEE Trans Geosci Remote Sens 2006;44(9):2393–406.[13] A Marsh Liam, van Verre Wouter, L Davidson John, Gao Xianyang, JW Podd Frank, J Daniels David, et al. Combining electromagnetic spectroscopy and ground-penetrating radar for the detection of anti-personnel landmines. Sensors 2019;19(15):3390.[14] Bruschini Claudio, Gros Bertrand, Guerne Frédéric, Pièce Pierre-Yves, Carmona Olivier. Ground penetrating radar and imaging metal detector for antipersonnel mine detection. J Appl Geophys 1998;40(1–3):59–71.[15] Sato Motoyuki, Fang Guangyou, Zeng Zhaofa. Landmine detection by a broadband GPR system. In: IGARSS 2003. 2003 IEEE international geoscience and remote sensing symposium. Proceedings (IEEE Cat. No. 03CH37477), Vol. 2. IEEE; 2003, p. 758–60.[16] Zhou Haoqiu, Feng Xuan, Dong Zejun, Liu Cai, Liang Wenjing. Multiparameter adaptive target classification using full-polarimetric GPR: A novel approach to landmine detection. IEEE J Sel Top Appl Earth Obs Remote Sens 2022;15:2592–606.[17] Machado Brito-da Costa Andreia, Martins Diana, Rodrigues Diogo, Fernandes Luís, Moura Rui, Madureira-Carvalho Aurea. Ground penetrating radar for buried explosive devices detection: A case studies review. Aust J Forensic Sci 2022;54(4):559–78.[18] Barnawi Ahmed, Budhiraja Ishan, Kumar Krishan, Kumar Neeraj, Alzahrani Bander, Almansour Amal, et al. A comprehensive review on landmine detection using deep learning techniques in 5G environment: Open issues and challenges. Neural Comput Appl 2022;34(24):21657–76.[19] Mahmood Safdar, Scharoba Stefan, Schorlemer Jonas, Schulz Christian, Hübner Michael, Reichenbach Marc. Detecting improvised land-mines using deep neural networks on GPR image dataset targeting FPGAs. In: 2022 IEEE nordic circuits and systems conference. IEEE; 2022, p. 1–7.[20] Faust Anthony A, Rothschild Richard E, Leblanc Philippe, McFee John Elton. Development of a coded aperture X-Ray backscatter imager for explosive device detection. IEEE Trans Nucl Sci 2009;56(1):299–307.[21] Gu Irene Yu-Hua, Tjahjadi Tardi. Detecting and locating landmine fields from vehicle-and air-borne measured IR images. Pattern Recognit 2002;35(12):3001–14.[22] Masuyama Soichi, Yasuda Kenzo, Hirose Akira. Multiple-mode selection of walled-LTSA array elements for high-resolution imaging to visualize antipersonnel plastic landmines. IEEE Geosci Remote Sens Lett 2008;5(4):745–9.[23] Corcelli Angela, Lobasso Simona, Lopalco Patrizia, Dibattista Michele, Araneda Ricardo, Peterlin Zita, et al. Detection of explosives by olfactory sensory neurons. J Hard Mater 2010;175(1–3):1096–100. [24] Marques Lino, Rachkov Michael, De Almeida Anibal T. Mobile pneumatic robot for demining. In: Proceedings 2002 IEEE international conference on robotics and automation (Cat. No. 02CH37292), Vol. 4. IEEE; 2002, p. 3508–13.[25] Baur Jasper, Steinberg Gabriel, Nikulin Alex, Chiu Kenneth, de Smet Timothy S. Applying deep learning to automate UAV-based detection of scatterable landmines. Remote Sens 2020;12(5):859.[26] Habib Maki K. Humanitarian demining: Reality and the challenge of technology–the state of the arts. Int J Adv Robot Syst 2007;4(2):19.[27] Habib Maki K. Humanitarian demining: The problem, difficulties, priorities, demining technology and the challenge for robotics. In: Humanitarian demining. IntechOpen; 2008.[28] Knezic Snjezana, Mladineo Nenad. GIS-based DSS for priority setting in humanitarian mine-action. Int J Geogr Inf Sci 2006;20(05):565–88.[29] Gisslen Linus, Törne Anders. A semantic approach to information management and decision support: An application to humanitarian demining operations. In: 2015 European intelligence and security informatics conference. IEEE; 2015, p. 75–82.[30] Mladineo Marko, Mladineo Nenad, Jajac Niksa. Project management in mine actions using multi-criteria-analysis-based decision support system. Croatian operational research review 2014;415–25.[31] Schultz Craig, Alegría Aura Cecilia, Cornelis Jan, Sahli Hichem. Comparison of spatial and aspatial logistic regression models for landmine risk mapping. Appl Geogr 2016;66:52–63.[32] Hameed Ibrahim A. Motion planning for autonomous landmine detection and clearance robots. In: 2016 International workshop on recent advances in robotics and sensor technology for humanitarian demining and counter-IEDs. IEEE; 2016, p. 1–5.[33] De Carvalho R Neumann, Vidal HA, Vieira P, Ribeiro MI. Complete coverage path planning and guidance for cleaning robots. In: ISIE’97 Proceeding of the IEEE international symposium on industrial electronics, Vol. 2. IEEE; 1997, p. 677–82.[34] Gelenbe Erol, Cao Yonghuan. Autonomous search for mines. European J Oper Res 1998;108(2):319–33.[35] Acar Ercan U, Choset Howie, Zhang Yangang, Schervish Mark. Path planning for robotic demining: Robust sensor-based coverage of unstructured environments and probabilistic methods. Int J Robot Res 2003;22(7–8):441–66.[36] Cassinis R, Bianco G, Cavagnini A, Ransenigo P. Strategies for navigation of robot swarms to be used in landmines detection. In: 1999 Third european workshop on advanced mobile robots (Eurobot’99). Proceedings (Cat. No. 99EX355). IEEE; 1999, p. 211–8.[37] Reyes Carlos José. As´ıson los procesos de desminado en Colombia. 2019,[38] Deb Kalyanmoy, Pratap Amrit, Agarwal Sameer, Meyarivan TAMT. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 2002;6(2):182–97.[39] Dorigo Marco, Di Caro Gianni. Ant colony optimization: A new meta-heuristic. In: Proceedings of the 1999 congress on evolutionary computation-CEC99 (Cat. No. 99TH8406), Vol. 2. IEEE; 1999, p. 1470–7.[40] Zitzler Eckart, Laumanns Marco, Thiele Lothar. SPEA2: Improving the strength Pareto evolutionary algorithm. TIK-Report 2001;103.[41] Otero-Palencia Carlos, Amaya-Mier René, Yie-Pinedo Ruben. A stochastic joint replenishment problem considering transportation and warehouse constraints with gainsharing by Shapley value allocation. Int J Prod Res 2019;57(10):3036–59.