Эффективный алгоритм приближенного решения метрической задачи коммивояжера

Abstract

В данной статье предлагаются алгоритмы приближенного решения задачи коммивояжера. Первый алгоритм развивает известную идею построения маршрута по остовному дереву минимального веса. Дерево дополняется ребрами, соответствующими вторым ближайшим расстояниям для висячих вершин. Затем циклы в графе последовательно соединяются в единый маршрут. На промежуточных шагах используется локальный поиск. Готовый маршрут подвергается анализу с целью выявления путей его улучшения. Второй алгоритм ограниченной области предлагает способ быстрого и эффективного построения маршрута. Образование начального контура происходит путем включения крайних вершин (если проводить аналогию с картой и городами: самый северный, самый южный, самый восточный и самый западный город), не принадлежащих маршруту. Приведены результаты численного эксперимента сравнения двух вышеуказанных методов, которые подтвердили уникальность обоих алгоритмов с точки зрения максимальной оптимизации длины маршрута (первый метод) и скоростью выполнения (второй метод), необходимой для быстрого решения масштабных задач.