Седьмая всероссийская конференция с международным участием "Информационные технологии и математическое моделирование", г. Анжеро-Судженск, 14 ноября 2008 г.
Авторы: Костюк Ю. Л. Пожидаев М. С.
ВНИМАНИЕ! Эта страница содержит неполный вариант документа. В pdf-версии приводятся точные таблицы с результатами сравнительного тестирования.
В задаче k коммивояжёров на множестве из n + 1 городов строится k замкнутых маршрутов по следующим правилам:
В [1] рассматривается сбалансированная задача k коммивояжёров, в которой число городов в каждом из маршрутов различается не более чем на один. В [1] с помощью вычислительного эксперимента исследуется ряд приближённых алгоритмов построения таких маршрутов, при этом в большинстве случаев наименьшую суммарную длину всех маршрутов давал алгоритм последовательного дихотомического разделения городов на группы с выбором разности минимальных расстояний.
В докладе рассматривается обобщение сбалансированной задачи k коммивояжёров на случай более чем одной базы. Здесь предполагается, что задано n + m городов, из которых m являются базами. При этом с каждой базой связывается набор из k / m маршрутов, а в каждый из маршрутов входит по n / k + 1 городов, из которых один город — база.
Для решения этой задачи предлагается следующий приближённый алгоритм. Для простоты далее предполагается, что k делится нацело на m, а n делится нацело на k.
Этап 1. Разделение n + m городов на m непересекающихся множеств таким образом, чтобы в каждое множество входило по n / m + 1 городов, из которых один город — база.
Этап 2. В каждом из полученном на первом этапе множестве разделение n / m + 1 городов на k / m групп так, как это делается в задаче k коммивояжёров с одной базой.
Этап 3. Для каждой из полученных на втором этапе групп городов выполняется вычисление простого маршрута коммивояжера.
Разделение на этапе один проводится в несколько шагов. В начале базы делятся на два множества, отличающихся по количеству баз не более чем на одну. При этом минимальное расстояние между парами баз из разных множеств должно быть максимальным. Затем все остальные города делятся между этими двумя множествами с выборам по разности минимальных расстояний. Если в каком-то из полученных множеств имеется более одной базы, то производится дальнейшее деление таким же способом.
Для оценки качества окончательно был проведён численный эксперимент, в котором города генерировались как случайные точки с равномерным распределением внутри единичного квадрата, а расстояние вычислялось как евклидово. В случае двух баз они располагались по углам диагонали квадрата, а в случае четырёх баз — во всех четырёх углах. Количество городов n задавалось в пределах от 16 до 1024, а число коммивояжёров k — от 2 до 128. Для сравнения был рассмотрен случай одной базы, располагавшейся в центре квадрата. Вычисление простых маршрутов коммивояжеров на третьем этапе производилось алгоритмом Лина-Кернигана.