Анотация: В статье предложен алгоритм решения NP-полной задачи нескольких коммивояжеров без депо, которая является обобщением “стандартной” задачи коммивояжера. В основу алгоритма положена метаэвристика муравьиной коло-нии – муравьи, используя различные типы феромонов, пытаются оптимально разбить граф на кластеры и оптимизи-ровать маршрут внутри каждого кластера. Приведены результаты эксперимента, проведенного на графах с 15 и 30 узлами для решения задачи с тремя коммивояжерами. Разработанный алгоритм демонстрирует возможность обоб-щения оптимизации муравьиных колоний на задачи с дополнительными условиями.
Ключевые слова:
задача коммивояжера, задача нескольких коммивояжеров без депо, муравьиный алгоритм, TSP, mTSP, ACO.
ENG
