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