Авторы: Костюк Ю. Л., Пожидаев М. С.}
"Вестник ТГУ", 2008 г., №1(2)
Рассматривается задача построения на множестве из n+1 города k замкнутых маршрутов коммивояжера с минимальной суммарной длиной и с одинаковым (с точностью до 1) числом городов в маршрутах. При этом один город (база) должен входить во все маршруты, а каждый из остальных городов должен войти только в один из маршрутов. Предлагается и экспериментально исследуется ряд приближенных алгоритмов решения этой задачи.
Задача коммивояжера (ЗК) имеет множество модификаций, в частности, для k коммивояжеров, когда на множестве из n+1 города строится k замкнутых маршрутов по следующим правилам:
Для многих практических приложений необходимым является дополнительное условие сбалансированности маршрутов, в частности, по числу городов, входящих в маршруты. Такая задача, являясь обобщением ЗК, также является NP-трудной, поэтому актуальными являются приближенные алгоритмы ее решения. Известен приближённый алгоритм решения несбалансированной задачи, который для метрических расстояний имеет точность 2 по сравнению с оптимальным алгоритмом. Однако для сбалансированного случая приближенных алгоритмов с гарантированной точностью не известно.
В статье предлагается ряд эвристических приближенных алгоритмов решения рассматриваемой задачи. Для этих алгоритмов приводятся результаты вычислительного эксперимента, позволяющие сравнить их между собой по качеству получаемого решения.