|
Эта публикация цитируется в 3 научных статьях (всего в 3 статьях)
Оптимизация, системный анализ и исследование операций
Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности
Г. Н. Жуковаa, М. В. Ульяновbc, М. И. Фомичевa a Национальный исследовательский университет
«Высшая школа экономики», Москва
b ВМК МГУ им. Ломоносова
c Институт проблем управления РАН им. В.А. Трапезникова, Москва
Аннотация:
Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin-Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного решения задачи коммивояжера методом ветвей и границ для задач из некоторого класса. Построен прогноз времени поиска точного решения методом ветвей и границ и комбинированным алгоритмом. Вычислительный эксперимент показал, что доля задач, которые комбинированным алгоритмом были решены быстрее,чем методом ветвей и границ, растет с ростом размерности задачи.
Ключевые слова:
задача коммивояжера, метод ветвей и границ, аппроксимация вероятностного распределения, квантиль вероятностного распределения, вероятностный прогноз времени.
Поступила в редакцию: 14.12.2018 После доработки: 04.04.2019 Принята к публикации: 25.04.2019
Образец цитирования:
Г. Н. Жукова, М. В. Ульянов, М. И. Фомичев, “Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности”, Автомат. и телемех., 2019, № 11, 155–172; Autom. Remote Control, 80:11 (2019), 2054–2067
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/at15165 https://www.mathnet.ru/rus/at/y2019/i11/p155
|
Статистика просмотров: |
Страница аннотации: | 210 | PDF полного текста: | 39 | Список литературы: | 31 | Первая страница: | 19 |
|