XLV международная научная студенческая конференция «Студент и научно-технический прогресс», г. Новосибирск, 10–12 апреля 2007 г.
Авторы: Костюк Ю. Л. Пожидаев М. С.
Отличие сбалансированной задачи k коммивояжеров (СЗkК) от известной задачи коммивояжера (ЗК) состоит в следующем:
Самый простой способ состоит в разрезании маршрута, полученного решением ЗК. Как известно, точное решение ЗК удается найти только для небольшого числа городов, поэтому приходится использовать приближенные алгоритмы. После разрезания маршрутов на k групп в каждую группу добавляется база, после чего решается простая ЗК для каждой из групп.
Второй способ состоит в последовательном распределении городов на две группы по принципу близости к двум наиболее удаленных друг от друга городам. После разделения городов на две группы каждая из групп снова разделяется на две группы и т. д. При этом возможно несколько вариантов разделения, отличающихся способами оценки близости городов.
Был проведен численный эксперимент, в котором города генерировались как случайные точки с равномерным распределением внутри единичного квадрата, а расстояние вычислялось, как евклидово. Количество городов n задавалось в пределах от 32 до 1024, а число коммивояжеров k — от 2 до 64. В качестве приближенного алгоритма решения простой ЗК использовался алгоритм Лина-кернигана.
Для оценки качества работы различных алгоритмов вычислялась длина минимального остова по всем n+1 городам, как нижняя граница ЗК.
Моделирование показало, что алгоритм последовательного распределения городов по двум группам имеет существенное преимущество перед алгоритмом разрезания маршрута.