Застосування алгоритму мурашиної колонії до вирішення задачі декількох комівояжерів без депо

Abstract

У статті запропоновано алгоритм вирішення NP-повної задачі декількох комівояжерів без депо, яка є узагальненням “стандартної” задачі комівояжера. В основу алгоритму покладено метаевристику мурашиної колонії – мурахи, використовуючи різні типи феромонів, намагаються оптимально розбити граф на кластери і оптимізувати маршрут всередині кожного кластера. Наведено результати експерименту, який було проведено на графах з 15 та 30 вузлами для вирішення задачі з трьома комівояжерами. Розроблений алгоритм демонструє можливість узагальнення оптимізацій мурашиних колоній на задачі з додатковими умовами.

Keywords

• задача комівояжера
• задача декількох комівояжерів без депо
• мурашиний алгоритм
• TSP
• mTSP
• ACO.