@ARTICLE{26583204_228869874_2018, 
	author = {Г. Н. Жукова and М. В. Ульянов and М. И. Фомичев}, 
	keywords = {, задача коммивояжера, метод ветвей и границ, комбинированный алгоритм, временная эффективностьэкспериментальное исследование},
	title = {<p class="text">Эффективный по времени точный комбинированный алгоритм для асимметричной задачи коммивояжера</p>},
	journal = {Бизнес-информатика},
	year = {2018},
	number = {3(45)},
	pages = {20-28},
	url = {https://bijournal.hse.ru/2018--3(45)/228869874.html},
	publisher = {},
	abstract = {&nbsp; &nbsp; &nbsp; Для практически значимых оптимизационных задач в области экономики и логистики, а также в ряде технических приложений возникает необходимость решения задачи коммивояжера (traveling salesman problem, TSP). Достаточно часто особенности этих задач приводят к задаче коммивояжера в асимметричной постановке (asymmetric traveling salesman problem, ATSP). Более того, в некоторых практических применениях желательно получение точного решения. Одним из известных точных алгоритмов решения задачи ATSP является алгоритм, реализующий известный метод ветвей и границ. Известные экспериментально полученные оценки его сложности в среднем экспоненциальные. Однако это не означает, что для небольших размерностей задачи (в настоящее время - не более 70-75) ожидаемое время решения индивидуальной задачи неприемлемо велико. Диктуемая практикой необходимость сокращения времени решения индивидуальных задач связана с использованием различных модификаций этого алгоритма, из которых модификация, предполагающая хранение усеченных матриц в поисковом дереве решений, - одна из наиболее эффективных. В рамках данной статьи авторы опираются именно на эту модификацию. Другие возможные улучшения временной эффективности программной реализации метода ветвей и границ связаны, в том числе, с получением начального приближения эвристическими алгоритмами. В результате получается комбинированный алгоритм, в котором на первом этапе работает некоторая эвристика для получения начального решения, с которого и стартует метод ветвей и границ. Эта идея обсуждается достаточно давно, однако проблема заключается в том, что для сокращения времени необходим такой эвристический алгоритм, который позволяет получить решение, близкое к оптимальному, с небольшими временными затратами. Одному из возможных решений этой задачи и посвящена данная статья.&nbsp; &nbsp; &nbsp; Предметом исследования в данной статье является выбор наилучшего эвристического алгоритма, применение которого приводит к повышению временной эффективности в комбинации с алгоритмом метода ветвей и границ, а также экспериментальное исследование его программной реализации с целью выявления среднего времени решения индивидуальных задач. На основе полученных результатов даются рекомендации по предельным размерностям задачи, допускающим приемлемое время решения, что представляет интерес в практическом применении этого комбинированного алгоритма в задачах бизнес-информатики и логистики.},
	annote = {&nbsp; &nbsp; &nbsp; Для практически значимых оптимизационных задач в области экономики и логистики, а также в ряде технических приложений возникает необходимость решения задачи коммивояжера (traveling salesman problem, TSP). Достаточно часто особенности этих задач приводят к задаче коммивояжера в асимметричной постановке (asymmetric traveling salesman problem, ATSP). Более того, в некоторых практических применениях желательно получение точного решения. Одним из известных точных алгоритмов решения задачи ATSP является алгоритм, реализующий известный метод ветвей и границ. Известные экспериментально полученные оценки его сложности в среднем экспоненциальные. Однако это не означает, что для небольших размерностей задачи (в настоящее время - не более 70-75) ожидаемое время решения индивидуальной задачи неприемлемо велико. Диктуемая практикой необходимость сокращения времени решения индивидуальных задач связана с использованием различных модификаций этого алгоритма, из которых модификация, предполагающая хранение усеченных матриц в поисковом дереве решений, - одна из наиболее эффективных. В рамках данной статьи авторы опираются именно на эту модификацию. Другие возможные улучшения временной эффективности программной реализации метода ветвей и границ связаны, в том числе, с получением начального приближения эвристическими алгоритмами. В результате получается комбинированный алгоритм, в котором на первом этапе работает некоторая эвристика для получения начального решения, с которого и стартует метод ветвей и границ. Эта идея обсуждается достаточно давно, однако проблема заключается в том, что для сокращения времени необходим такой эвристический алгоритм, который позволяет получить решение, близкое к оптимальному, с небольшими временными затратами. Одному из возможных решений этой задачи и посвящена данная статья.&nbsp; &nbsp; &nbsp; Предметом исследования в данной статье является выбор наилучшего эвристического алгоритма, применение которого приводит к повышению временной эффективности в комбинации с алгоритмом метода ветвей и границ, а также экспериментальное исследование его программной реализации с целью выявления среднего времени решения индивидуальных задач. На основе полученных результатов даются рекомендации по предельным размерностям задачи, допускающим приемлемое время решения, что представляет интерес в практическом применении этого комбинированного алгоритма в задачах бизнес-информатики и логистики.}
}