Скрыть
Раскрыть

ISSN 1998-0663 (print),
ISSN 2587-8166 (online)

English version: ISSN 2587-814X (print),
ISSN 2587-8158 (online)

Жукова Г. Н. 1, Ульянов М. В. 2, Фомичев М. И. 1,3
  • 1 НИУ ВШЭ, 101000, Россия, Москва, ул. Мясницкая, д.20
  • 2 Институт проблем управления им В.А. Трапезникова РАН, 117997, г. Москва, ул. Профсоюзная, д. 65
  • 3 Национальный исследовательский университет «Высшая школа экономики». , 101000, г. Москва, ул. Мясницкая, д. 20.

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

2018. № 3(45). С. 20–28 [содержание номера]

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

Библиографическое описание:

Жукова Г.Н., Ульянов М.В., Фомичев М.И. Эффективный по времени точный комбинированный алгоритм для асимметричной задачи коммивояжера// Бизнес-информатика. 2018. № 3 (45). С. 20–28. DOI: 10.17323/1998-0663.2018.3.20.28.

doi
BiBTeX
RIS
 
 
Rambler's Top100 rss