Сборники трудов ИСП РАН


Метрическая задача коммивояжера: экспериментальное исследование Парето-оптимальных алгоритмов

С.М. Авдошин (ВШЭ, Москва, Россия)
Е.Н. Береснева (ВШЭ, Москва, Россия)

Аннотация

Задача коммивояжера — одна из важнейших задач теории графов и комбинаторной оптимизации, суть которой состоит в нахождении гамильтонова цикла наименьшей длины. Разработка методов для решения задачи коммивояжера осуществляется на протяжении многих лет, и, по-прежнему, остается актуальной, поскольку задача является NP-трудной. Решения применяются, в основном, для минимизации производственных и логистических затрат и издержек. В работе рассматривается частный случай общей постановки задачи коммивояжера, в котором выполняется свойство метрики — метрическая задача коммивояжера. Целью данной работы является определение группы Парето оптимальных алгоритмов решения метрической задачи коммивояжера по критериям времени работы и точности решения в ходе экспериментального исследования. В связи с тем, что задача коммивояжера является NP-трудной, в работе рассматриваются только эвристические алгоритмы, позволяющие получить приближенные решения за полиномиальное время. В статье представлено краткое описание используемых алгоритмов решения метрической задачи коммивояжера, указаны их априорные точностные и временные оценки. Приведено описание плана эксперимента. Данными для экспериментального исследования послужили два набора из открытой библиотеки данных для метрической задачи коммивояжера, основанные на высоко-интегральных вычислительных схемах (VLSI Data Sets) и географических координатах (высоте и широте) городов в различных странах (National TSPs). В результате исследований выявлены оптимальные по Парето алгоритмы для наборов данных различных размерностей — до 700 тысяч вершин. Для каждого N в число Парето-оптимальных алгоритмов входят некоторые из алгоритмов MC, SC, NN, DENN, CI, GRD, CI + 2-Opt,  GRD + 2-Opt, CHR и LKH. Приведена таблица, содержащая информацию о результатах экспериментов.

Ключевые слова

метрическая задача коммивояжера, эвристический алгоритм, оптимальность по Парето

Издание

Труды Института системного программирования РАН, том 29, вып. 4, 2017, стр. 123-138.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2017-29(4)-8

Полный текст статьи в формате pdf (на английском) Вернуться к содержанию тома