ВИКОРИСТАННЯ АЛГОРИТМУ ВЕЛЬЦЛЯ ДЛЯ РОЗВ’ЯЗАННЯ ЗАДАЧІ КОМІВОЯЖЕРА

Анотація

Стаття присвячена вирішенню однієї з NP-задач, а саме пошуку оптимального маршруту комівояжера для відвідання кожного із n заданих міст. Ефективні алгоритми розв’язання даної задачі дозволяють знаходити оптимальні маршрути навіть для великих наборів міст, що зменшує витрати часу, пального та ресурсів. Поєднання високої точності з малою обчислювальною складністю робить такі методи придатними для використання в реальних системах, де рішення потрібно приймати швидко.Мета роботи – вдосконалення методу гілок та меж для розв’язання задачі комівояжера за рахунок застосування алгоритму Вельцля та використання мінімального охоплюючого кола (Minimum Enclosing Circle, МЕС) як евристики для підсилення відсікаючих правил у даному методі.Методологія. Алгоритм Вельцля – це класичний приклад ефективного геометричного методу з відсіками та евристикою, який можна легко включати до більш складних алгоритмів. У задачах розміщення, пакування, колізій, кластеризації тощо, алгоритм Вельцля може бути використаний як частина оціночної або відсікаючої функції: обчислити мінімальне коло, що містить підмножину об’єктів-міст, щоб оцінити обсяг/простір і якщо коло з новою точкою виходить за дозволені межі – відсікати гілку. Наукова новизна. Автором запропоновано використання алгоритму Вельцля для прискорення точного алгоритму розв’язання задачі комівояжера. Вигода у знаходженні мінімального кола, що охоплює множину точок-міст на площині, полягає у отриманні більш тісної нижньої межі гілки в методі гілок та меж, у збільшенні кількості гілок у дереві пошуку, які відсічуться раніше, і як наслідок метод запрацює швидше. MEC відсікає ті гілки, у яких невідвідані міста лежать на великій відстані одне від одного, і навіть найоптимальніший добудований маршрут буде занадто дорогим. Це зменшує простір пошуку і прискорює алгоритм.Висновки. Метод гілок та меж із використанням мінімального охоплюючого кола MEC має широкий спектр практичного застосування у задачах, де необхідно швидко отримати якісний маршрут з мінімальними обчислювальними витратами, якщо допускається невелике відхилення від оптимального розв’язку. Таким чином, використання MEC у поєднанні з методом гілок та меж є універсальним підходом, що поєднує точність математичної оптимізації та швидкість евристичних методів і може бути впроваджене в будь-якій сфері, де маршрутизація має велике практичне значення.