Управління розвитком

Комп’ютерні інструменти для вирішення завдання комівояжера

Завдання комівояжера, яка полягає у пошуку найкоротшого або найменш витратного кругового маршруту, є однією з найпоширеніших оптимізаційних задач, які потребують вирішення в різних сферах практичної діяльності. У статті проаналізовані і на конкретному прикладі продемонстровані різні методи вирішення даного завдання: евристичні (метод найближчого сусіда, метод найбільш вигідного сусіда), метаевристичні (еволюційний алгоритм), методи математичного програмування. На додаток до класичних точних методів (які для великомасштабних завдань на основі наявного програмного забезпечення важко використовувати) і евристичним методам в статті запропоновано використовувати інноваційні можливості комерційно доступного програмного продукту MS Excel на основі метаеврістіческой бази. Для пошуку оптимального рішення точними методами був використаний пакет програм Excel (Solver), а також спеціалізований пакет програмного забезпечення GAMS. Порівняння різних підходів до вирішення завдання комівояжера на практичному прикладі показало, що використання традиційних евристичних підходів (метод найближчого сусіда або метод найбільш вигідного сусіда) є не складним з обчислювальної точки зору, але не дає рішень, які були б прийнятні в сучасних умовах. Застосування MS Excel для вирішення завдання методами математичного програмування і метаевристики дозволило отримати оптимальне рішення, що призвело до висновку про те, що сучасні інструменти є підходящим доповненням до вирішення завдання комівояжера при збереженні якості рішення

задача комівояжера, евристичні методи, метаевристичні методи, оптимальне рішення, субоптимальное рішення, GAMS, Excel