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