Конкурс по реализации эвристик для задачи коммивояжера

Постановка задачи

Восьмой конкурс DIMACS по реализации алгоритмов, проведенный DIMACS – Центром дискретной математики и теории вычислительных систем (Center for Discrete Mathematics and Theoretical Computer Science), был посвящен эвристикам для симметричной задачи коммивояжера. Организаторами конкурса, начавшегося в июне 2000 года, стали Дэвид Джонсон, Лайл Макгиох, Фред Гловер и Сезар Рего. В его рамках изучалось современное состояние дел в области эвристик для задачи коммивояжера, а исследователи протестировали широкий спектр реализаций на общем (и крайней разнообразном) наборе экземпляров входных данных. Конкурс продолжался вплоть до 2007 года, а новые результаты все еще принимаются на сайте http://www.research.att.com/~dsj/chtsp. Обзор результатов по состоянию на 2002 год был приведен в книге Джонсона и Макгиоха [5].

Участники тестировали свои эвристики на четырех типах экземпляров, выбранных для проверки надежности и масштабируемости различных подходов:

1. 34 экземпляра, содержащие не менее 1000 городов, из TSPLIB – библиотеки экземпляров под управлением Герда Райнельта.

2. Набор из 26 экземпляров, состоящий из точек, равномерно распределенных по единичной площади, размер которых составляет от 1000 до 10 000 000 городов.

3. Набор из 23 экземпляров со случайно сгенерированными кластерами, размер которых составляет от 1000 до 316 000 городов.

4. Набор из 7 экземпляров на основе случайных матриц расстояния, размер которых составляет от 1000 до 10 000 городов.

Экземпляры и генераторы библиотеки TSPLIB для случайных распределений доступны на сайте конкурса. Кроме того, на нем можно найти набор экземпляров для асимметричной задачи коммивояжера.

Для каждого экземпляра, на котором тестировалась эвристика, участники сообщали название используемой машины, полученную длину маршрута, пользовательское время процесса и, при наличии таких данных, объем использованной памяти. Некоторые эвристики невозможно было применить ко всем экземплярам – либо в силу исходно геометрической природы этих эвристик, либо из-за чрезмерно большого размера экземпляра. Чтобы получить возможность сравнения времени выполнения эвристик на разных машинах, участники выполняли эталонную эвристику (предоставленную организаторами) на экземплярах разных размеров. Затем время выполнения эталонного образца использовалось для нормализации (хотя бы приблизительной) наблюдаемого времени выполнения эвристик участников.

Качество маршрута вычислялось на основе представленной длины маршрута двумя способами: как отношение полученной длины маршрута к оптимальной для данного экземпляра (если таковая была известна), а также как отношение к нижней границе Хельда-Карпа для этого экземпляра. Оптимизированный пакет Concorde Эпплгейта и др. [1] обеспечил оптимальный результат для 58 экземпляров за разумное время. Concorde использовался также для вычисления нижней границы Хельда-Карпа для всех экземпляров, кроме трех самых крупных. Третий алгоритм, основанный на лагранжевой релаксации, использовался для вычисления приблизительной границы Хельда-Карпа для оставшихся экземпляров. На сайте конкурса приведен отчет о работе каждого из трех алгоритмов, включающий время выполнения и сравнение границ, полученных для каждого экземпляра.

Сайт конкурса позволяет создавать множество разных отчетов:

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

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

3. Для каждой пары эвристик можно сгенерировать таблицы и графы со сравнением качества маршрута и времени выполнения для экземпляров различных типов и размеров.

Эвристики, результаты для которых были представлены на конкурс, относятся к нескольким общим категориям:

Эвристики, ориентированные на скорость. Все эти эвристики рассчитаны на геометрические образцы, а время выполнения лишь ненамного превышает время чтения экземпляра входных данных. В числе примеров можно упомянуть разделение на полосы и кривую Пеано. Требование высокой скорости радикально влияет на качество маршрута. Два из этих алгоритмов нашли маршрут с длиной на 14% выше нижней границы Хельда-Карпа для конкретного экземпляра TSPLIB, но ни одному не удалось попасть в диапазон 25% на остальных 89 экземплярах.

Эвристики построения маршрута. Эти эвристики строят маршруты различными способами, не стремясь найти улучшений после того, как найден один маршрут, проходящий через все города. Некоторые из них (такие как эвристики поиска ближайшего соседа и жадные эвристики) достаточно просты; другие – например, знаменитая эвристика Кристофидеса – намного сложнее. Эти алгоритмы позволяют выбирать различные соотношения между временем выполнения и качеством маршрута, а некоторые из них находят маршруты с длиной на 15% выше нижней границы Хельда-Карпа для большинства экземпляров за разумное время. Лучший из них, вариант эвристики Кристофидеса, выдает маршрут в пределах 8% на однородных экземплярах, однако требует намного больше времени, чем другие алгоритмы.

Простые эвристики локального улучшения. В их число входят хорошо известные эвристики 2-opt и 3-opt, а также их варианты. По качеству маршрута эти эвристики превосходят эвристики построения маршрута на большинстве типов образцов. К примеру, эвристика 3-opt находит маршрут в пределах 3% от нижней границы Хельда-Карпа на большинстве однородных экземпляров. Работы, представленные в этой категории, исследовали различные способы реализации, влияющие на соотношение времени и качества.

Эвристика Лина-Кернигана и ее варианты. Эти эвристики расширяют понятие окрестности для локального поиска, использовавшееся в эвристике 3-opt. Эвристика Лина-Кернигана способна выдавать высококачественные пути (например, в пределах 2% от границы Хельда-Карпа на однородных экземплярах) за разумное время. Вариант, предложенный Хельсгауном [3], позволяет получать маршруты в пределах 1% на широком спектре экземпляров, хотя время выполнения может быть достаточно большим.

Итеративные эвристики локального поиска. Алгоритмы этой категории основаны на неоднократном выполнении таких эвристик, как алгоритм Лина-Кернигана, с применением к маршруту случайных отклонений после нахождения локального оптимума. Эти алгоритмы позволяют получить высококачественные маршруты за счет увеличения времени выполнения.

Эвристики, начинающие работу с итеративного локального поиска. В качестве примера можно привести эвристику со слиянием маршрутов [2], которая выполняет несколько проходов локального поиска, строит граф, содержащий ребра, найденные на лучших маршрутах, и производит поиск полным перебором на полученном графе. Для некоторых экземпляров входных данных конкурса этот алгоритм нашел лучшие известные маршруты.

Работы, представленные на конкурс, продемонстрировали выдающуюся эффективность эвристик при решении задачи коммивояжера. Они также показали, что такие детали реализации, как выбор структуры данных или использование приближенных аспектов некоторых вычислений, способны значительно повлиять на время выполнения и/или качество решения. Результаты для любой конкретной эвристики в огромной степени зависели от типа образца, к которому она применялась.

Ссылка на код

www.research.att.com/~dsj/chtsp

См. также

• Реконструкция кривых в задаче коммивояжера

Литература

1. Applegate, D., Bixby, R., Chvatal, V., Cook, W.: On the solution of traveling salesman problems. Documenta Mathematica, Extra Volume Proceedings ICM III:645-656. Deutsche Mathematiker-Vereinigung, Berlin (1998)

2. Applegate, D., Bixby, R., Chvatal, V., Cook, W.: Finding tours in the TSP. Technical Report 99885, Research Institute for Discrete Mathematics, Universitat Bonn (1999)

3. Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106-130 (2000)

4. Johnson, D.S., McGeoch, L.A.: The traveling salesman problem: A case study. In: Aarts, E., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 215-310. Wiley, Chicester (1997)

5. Johnson, D.S., McGeoch, L.A.: Experimental analysis of heuristics for the STSP. In: Gutin, G., Punnen, A.P. (eds.) The Traveling Salesman Problem and Its Variants, pp. 369-443, Kluwer, Dordrecht (2002)