The Metric Travelling Salesman Problem: the experiment on Pareto-optimal algorithms

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