53951

Автор(ы): 

Автор(ов): 

3

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

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

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

Название: 

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

DOI: 

10.1134/S0005231019110096

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

  • Автоматика и телемеханика

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

№ 11

Город: 

  • Москва

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

  • ИПУ РАН

Год издания: 

2019

Страницы: 

155-172
Аннотация
Приведены результаты сравнительного статистического анализа времени решения несимметричной задачи коммивояжера (NTSP) методом ветвей и границ (без предвычисления тура) и комбинированным методом. Комбинированный метод состоит из приближенного алгоритма Lin-Kernighan-Helsgaun, используемого для вычисления начального тура, и метода ветвей и границ. Показано, что использование приближенного решения, найденного с помощью алгоритма Lin-Kernighan-Helsgaun, позволяет существенно уменьшить время поиска точного решения задачи коммивояжера методом ветвей и границ для задач из некоторого класса. Построен прогноз времени поиска точного решения методом ветвей и границ и комбинированным алгоритмом. Вычислительный эксперимент показал, что доля задач, которые комбинированным алгоритмом были решены быстрее,чем методом ветвей и границ, растет с ростом размерности задачи.

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

Жукова Г.Н., Ульянов М.В., Фомичев М.И. Комбинированный точный алгоритм для асимметричной задачи коммивояжера: построение и статистическое исследование временной эффективности // Автоматика и телемеханика. 2019. № 11. С. 155-172.