Алгоритм поиска точного решения задачи нескольких коммивояжёров
Аннотация:
В работе рассмотрена задача нескольких коммивояжеров. Задача состоит в том, чтобы на графе со взвешенными дугами найти набор из заранее заданного количества непересекающихся циклов, у которого вес (сумма весов дуг) наибольшего цикла минимален. Разработан точный, основанный на методе ветвей и границ алгоритм решения поставленной задачи. В построенном алгоритме, как и в известном алгоритме Балаша-Кристофидеса решения задачи одного коммивояжера, используется венгерский алгоритм решения задачи о назначениях. Проведены численные эксперименты со случайными графами большой размерности.
Ключевые слова:
задача коммивояжёра, задача о назначениях, венгерский алгоритм, метод ветвей и границ
