Методы оптимизации и теория управления

Научная статья

Приближённый и точный алгоритмы задачи нескольких коммивояжёров

Олег Александрович Клименко

	Южный Федеральный Университет, Ростов-на-Дону, Россия
	oleg.klimenko.math@mail.ru

Аннотация. Рассматривается задача нескольких коммивояжёров в минимаксной постановке без депо, которая состоит в том, чтобы на графе со взвешенными рёбрами найти набор заранее заданного количества непересекающихся циклов, покрывающих все вершины, у которого сумма весов рёбер наибольшего цикла минимальна.

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

Разработана параллельная версия полученного алгоритма, а также разработана модификация, позволяющая находить приближённое решение с заданной точностью.

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

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

Благодарности: Работа поддержана грантом № FENW-2026-0031

Для цитирования: Клименко О. А. Приближённый и точный алгоритмы задачи нескольких коммивояжёров // Программные системы: теория и приложения. 2026. Т. 17. № 4. С. 137–158. https://psta.psiras.ru/2026/4_137-158.

Полный текст статьи (PDF): https://psta.psiras.ru/read/psta2026_4_137-158.pdf.

Статья поступила в редакцию 15.07.2026; одобрена после рецензирования 06.09.2026; принята к публикации 24.10.2026; опубликована онлайн 02.11.2026.