Решение задачи коммивояжера больших размеров в контексте логистической стратегии предприятия

Abstract

Описан подход, основанный на редукции большой задачи коммивояжера к множеству более простых. Представлен алгоритм решения этой задачи с подробной иллюстрацией и описанием логики выполняемых шагов. Алгоритм допускает повторное посещение городов, что для практических целей приемлемо, поскольку основная задача – поиск маршрута минимальной общей длины с заходом в каждый город как минимум единожды. Новизной является учет внутри- и межкластерных связей через пересчет матрицы попарных кратчайших расстояний между населенными пунктами. При этом исходная сеть населенных пунктов разбивается на кластеры. В пределах каждого кластера отыскивается оптимальный маршрут, проходящий через все его узлы без возврата в стартовый узел. После чего ищется кратчайший маршрут, связывающий кластеры. Учет этого фактора более четко «разводит» пары населенных пунктов в результирующей кластерной структуре, что способствует получению качественных решений.