Жихарев С. А., Костюк Ю. Л.

Локальный поиск в метрической задаче коммивояжера // Геоинформатика. Теория и практика. Вып.1 - Томск: Изд-во Томск. ун-та, 1998, с.84-95,
http://www.inf.tsu.ru/Library/Publications/1999/Zhikharev_1999_1.pdf
Электронная библиотека:




Рассматривается задача коммивояжера. Применительно к некоторым алгоритмам ее решения – алгоритму дерева, алгоритмам, основанным на паросочетаниях, – рассматривается метод локального поиска, использующий переборные методы по некоторому “окну”. Предлагается ряд модификаций известных алгоритмов. Для некоторых из них отдельно рассматривается влияние переборных методов, примененных к еще не построенному маршруту, на качество решения. В работе приводятся данные, полученные в результате статистического моделирования на евклидовой плоскости. На их основании делаются выводы о преимуществах одного алгоритма перед другим. Приведены результаты попарного сравнения наиболее близких друг к другу алгоритмов.
Библ. 6, ил. 5, табл.3.


Формат: Текст PDF Размер: 150 Кбайт