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

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

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

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

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