49582

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Exact time-efficient combined algorithm for solving the asymmetric traveling salesman problem

ISBN/ISSN: 

1998-0663

DOI: 

10.17323/1998-0663.2018.3.20.28

Наименование источника: 

  • Бизнес-информатика

Обозначение и номер тома: 

№ 3 (45)

Город: 

  • Москва

Издательство: 

  • НИУ ВШЭ

Год издания: 

2018

Страницы: 

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

Библиографическая ссылка: 

Жукова Г.Н., Ульянов М.В., Фомичев М.И. Exact time-efficient combined algorithm for solving the asymmetric traveling salesman problem // Бизнес-информатика. 2018. № 3 (45). С. 20–28.