Реализация и оценка качества ресурсно-эффективных алгоритмов для метрической задачи коммивояжера

Задача коммивояжера – одна из важнейших задач теории графов и комбинаторной оптимизации, суть которой состоит в нахождении гамильтонова цикла наименьшей длины. Разработка методов для решения задачи коммивояжера осуществляется на протяжении многих лет, и, по-прежнему, остается актуальной, поскольку задача является NP-трудной. Решения применяются, в основном, для минимизации производственных и логистических затрат и издержек. В работе рассматривается частный случай общей постановки задачи коммивояжера – метрическая задача коммивояжера, в которой выполняется свойство метрики. Целью данной работы является определение группы Парето оптимальных алгоритмов решения метрической задачи коммивояжера по критериям времени работы и точности решения в ходе экспериментального исследования. В связи с тем, что задача коммивояжера является NP-трудной, в работе рассматриваются только эвристические алгоритмы, позволяющие получить приближенные решения за полиномиальное время. В статье представлена классификация алгоритмов решения метрической задачи коммивояжера. Реализованы существующие алгоритмы, предложены модификации некоторых из них. Приведено описание используемой структуры хранения данных и методики эксперимента. Данными для экспериментального исследования послужили два набора из открытой библиотеки данных для метрической задачи коммивояжера, основанные на высоко-интегральных вычислительных схемах и географических координатах (высоте и широте) городов в различных странах. В результате исследований выявлены оптимальные по Парето алгоритмы. Описаны направления дальнейшей работы Работа содержит 113 страниц, 5 глав, 13 рисунков, 7 таблиц, 14 схем, 67 источников, 11 приложения. Ключевые слова—метрическая задача коммивояжера, ресурсно-эффективные алгоритм, эвристический алгоритм, вычислительный эксперимент.