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

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