Исследования алгоритмов приближённого решения сбалансированной задачи k коммивояжеров

Шестая международная научно-практическая конференция "Информационные технологии и математическое моделирование", г. Анжеро-Судженск, 9 ноября 2007 г.

• Тезисы в формате PDF
• Презентация в формате PPT

Отличие сбалансированной задачи k коммивояжёров (СЗkК) от известной задачи коммивояжёра (ЗК) состоит в следующем:

1. Должно быть построено k (k > 1) замкнутых маршрутов, по одному для каждого коммивояжёра.
2. Задаётся n + 1 город, причём один из них, называемый базой, должен входить в один из маршрутов.
3. Количество городов в маршрутах должно отличаться друг от друга не больше чем на единицу.
4. Суммарная стоимость всех маршрутов должна быть минимальной.

Самый простой способ состоит в разрезании маршрута, полученного решением ЗК. Как известно, точное решение ЗК удаётся найти только для небольшого числа городов, поэтому приходится использовать приближённые алгоритмы. После разрезания маршрута на k групп в каждую группу добавляется база, после чего решается простая ЗК для каждой из групп.

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

Был проведён численный эксперимент, в котором города генерировались как случайные точки с равномерным распределением внутри единичного квадрата, а расстояние вычислялось как евклидово. Количество городов n задавалось в пределах от 32 до 1024, а число коммивояжёров k — от 2 до 64. В качестве приближённого алгоритма решения простой ЗК использовался алгоритм Лина-Кернигана.

Для оценки качества работы различных алгоритмов вычислялась длина минимального остова по всем n + 1 городам, как нижняя граница ЗК.

Моделирование показало, что алгоритм последовательного распределения городов по двум группам имеет существенное преимущество перед алгоритмом разрезания маршрута.

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