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