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

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

О.С. Тимчук, Я.А. Проценко, А.І. Парамонов
Системи обробки інформації. — 2019. — № 3(158). – С. 73-78.
УДК 4.891
Мова статті: українська
Анотації на мовах:


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


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

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

Інформація про авторів публікації:
Бібліографічний опис для цитування:
Тимчук О. С. Застосування алгоритму мурашиної колонії до вирішення задачі декількох комівояжерів без депо / О.С. Тимчук, Я.А. Проценко, А.І. Парамонов  // Системи обробки інформації. – 2019. – № 3(158). – С. 73-78. https://doi.org/10.30748/soi.2019.158.08.