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

Аннотация

      Для практически значимых оптимизационных задач в области экономики и логистики, а также в ряде технических приложений возникает необходимость решения задачи коммивояжера (traveling salesman problem, TSP). Достаточно часто особенности этих задач приводят к задаче коммивояжера в асимметричной постановке (asymmetric traveling salesman problem, ATSP). Более того, в некоторых практических применениях желательно получение точного решения. Одним из известных точных алгоритмов решения задачи ATSP является алгоритм, реализующий известный метод ветвей и границ. Известные экспериментально полученные оценки его сложности в среднем экспоненциальные. Однако это не означает, что для небольших размерностей задачи (в настоящее время – не более 70–75) ожидаемое время решения индивидуальной задачи неприемлемо велико. Диктуемая практикой необходимость сокращения времени решения индивидуальных задач связана с использованием различных модификаций этого алгоритма, из которых модификация, предполагающая хранение усеченных матриц в поисковом дереве решений, – одна из наиболее эффективных. В рамках данной статьи авторы опираются именно на эту модификацию. Другие возможные улучшения временной эффективности программной реализации метода ветвей и границ связаны, в том числе, с получением начального приближения эвристическими алгоритмами. В результате получается комбинированный алгоритм, в котором на первом этапе работает некоторая эвристика для получения начального решения, с которого и стартует метод ветвей и границ. Эта идея обсуждается достаточно давно, однако проблема заключается в том, что для сокращения времени необходим такой эвристический алгоритм, который позволяет получить решение, близкое к оптимальному, с небольшими временными затратами. Одному из возможных решений этой задачи и посвящена данная статья.
      Предметом исследования в данной статье является выбор наилучшего эвристического алгоритма, применение которого приводит к повышению временной эффективности в комбинации с алгоритмом метода ветвей и границ, а также экспериментальное исследование его программной реализации с целью выявления среднего времени решения индивидуальных задач. На основе полученных результатов даются рекомендации по предельным размерностям задачи, допускающим приемлемое время решения, что представляет интерес в практическом применении этого комбинированного алгоритма в задачах бизнес-информатики и логистики.