1. Наука
  2. Видання
  3. Системи обробки інформації
  4. 3(158)'2019
  5. Применение алгоритма муравьиной колонии к решению задачи нескольких коммивояжеров без депо

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

О.С. Тимчук, Я.А. Проценко, А.И. Парамонов
Аннотации на языках:


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


Ключевые слова: задача коммивояжера, задача нескольких коммивояжеров без депо, муравьиный алгоритм, TSP, mTSP, ACO.

Список литературы