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

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

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

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

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

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

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

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