Спосіб та програмне забезпечення для оптимізації маршрутів комівояжера
Вантажиться...
Дата
2024
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
КПІ ім. Ігоря Сікорського
Анотація
На сьогодні задача комівояжера є однією з ключових у галузі
комбінаторної оптимізації, яка знаходить застосування у таких сферах, як
логістика, планування маршрутів, навігація та інші. Незважаючи на численні
існуючі алгоритми, проблема ефективного вирішення задачі для великих
наборів даних з нерівномірним розподілом точок залишається актуальною.
У даній роботі запропоновано новий комбінований підхід до розв’язання
задачі комівояжера, що поєднує геометричну евристику та локальну
оптимізацію. Основна ідея полягає у побудові початкового маршруту на основі
крайніх точок (північ, південь, захід, схід) із подальшою динамічною
обробкою відкритих міст за допомогою черги пріоритетів і багатокрокової
реінсерції для локальної оптимізації маршруту. Такий підхід забезпечує
покращення довжини маршруту в середньому на 2,91%, а на окремих наборах
даних — до 4,30% у порівнянні з кращими аналогами.
Для реалізації розробленого методу створено десктопний застосунок з
використанням мови програмування C#, фреймворків WPF, OxyPlot, що
дозволяє виконувати інтерактивне моделювання, візуалізацію та оптимізацію
маршрутів. Результати дослідження підтверджують високу ефективність
запропонованого алгоритму та його потенціал для застосування у практичних
сценаріях, таких як транспортна логістика, оптимізація поставок та інші
завдання маршрутизації.
Опис
Ключові слова
задача комівояжера, оптимізація, користувацький алгоритм, маршрут, локальна оптимізація, оптимізація повторної вставки, комбінаторна оптимізація, програмне забезпечення
Бібліографічний опис
Маховой, М. В. Спосіб та програмне забезпечення для оптимізації маршрутів комівояжера : магістерська дис. : 121 Інженерія програмного забезпечення / Маховой Олександр Вікторович. – Київ, 2024. – 162 с.