Определение оптимального замкнутого маршрута

Так как приведенная матрица содержит только неотрицательные элементы, то сумма приводящих констант может служить нижней границей длины цикла при исходной матрице С, т. е. является оценкой исходного множества G0: ξ(G0)=hΣ.

3. Произведем ветвление множества G0 на два непересекающихся подмножества G1 и G2:

· подмножество G1 получается из множества G0 при добавлении следующего условия: из пункта r следует непосредственно идти в пункт s;

· подмножество G2 получается из множества G0 при добавлении условия: из пункта r запрещается непосредственный переход в пункт s.

При этом пару городов (r, s) выбирают так, чтобы множество G1 с наибольшей вероятностью содержало оптимальный цикл, а множество G2 – не содержало. Следовательно, пара (r, s) выбирается из множества пар претендентов (i, j), которым соответствуют нулевые элементы матрицы С, то есть Сij=0, таким образом, чтобы циклам, входящим в подмножество G2, соответствовали как можно более длинные пути. Так как по определению подмножества G2 путь по любому из этих циклов переходит из города r в некоторый промежуточный пункт j (j¹s), а в город s коммивояжер приезжает из некоторого пункта i (i¹r), длина этого пути будет не меньше чем

Θ(r, s)=

Поэтому необходимо выбрать пару (r, s) так, чтобы Θ(r, s) было максимально, т. е.

Θ(r,s)= (2.3)

при условии, что Сij=0.

4. Выполним преобразование матрицы расстояний при ветвлении и пересчитаем оценки. Каждому подмножеству, полученному в результате ветвление, будет соответствовать своя приведенная матрица и своя оценка. Матрица С2, соответствующая подмножеству G2, получается из матрицы С в результате следующих преобразований:

· запрещается переезд из города r в город s: Сrs→¥;

· проводится процедура приведения матрицы. Оценка подмножества G2 равна оценке исходного множества G0 и Θ(r, s):

ξ(G2)=ξ(G0)+Θ(r, s).

Для построения матрицы С1 соответствующей подмножеству G1 выполняются следующие преобразования матрицы С:

· вычеркивается строка r и столбец s из матрицы С, так как из каждого города можно выезжать только один раз и в каждый город можно въезжать только один раз;

· запрещается переезд из города s в город r (Сsr→¥), а также все другие переезды, которые приводят к образованию замкнутых подциклов;

· выполняется процесс приведения матрицы С.

Оценка подмножества G1 равна оценке исходного множества G0 и сумме приводящих констант:

ξ( G1)=ξ( G0) +.

грузопоток транспортный сеть маршрут

Для дальнейшего ветвления на следующем шаге выбирается то из двух полученных подмножеств G1 и G2, которое имеет наименьшую оценку. Процесс построения и оценивания подмножеств продолжается до тех пор, пока не будет получена матрица размерности 2´2, которая содержит только две допустимые пары городов. Эти пары являются замыкающими для некоторого маршрута без петель.

5. Проверим условие оптимальности. Если оценка полученного замкнутого маршрута не больше оценок всех допустимых для дальнейшего ветвления подмножеств (висячих вершин дерева), то он является оптимальным. Если существует хотя бы одно подмножество с меньшей оценкой, то построенный цикл запоминается. Процесс ветвления продолжается исходя из множества с меньшей оценкой до тех пор, пока нижние границы новых подмножеств остаются меньше длины выделенного цикла. В ходе ветвления либо будет построен цикл меньшей длины, либо обнаружится, что на новых подмножествах он не существует, т. е. оценка для каждого из них не меньше рекорда (длины кратчайшего из ранее полученных циклов).

Популярные материалы:

Основные плановые показатели работы предприятия
Плановый отдел занимается планированием и анализом работы автотракторной техники. Структура планового отдела: экономист. Плановый отдел изучает: - проверка технологических табелей; - рассчитывает коэффициент технической готовности на ...

Внешняя торговля России. Запасы угля в России
Россия располагает разнообразными типами углей — бурыми, каменными, антрацитами — и по запасам занимает одно из ведущих мест в мире. Общие геологические запасы угля составляют 6421 млрд. т, из них кондиционные — 5334 млрд. т. Свыше 2/3 об ...

Расчет модернизированной крыши на прочность и устойчивость. Анализ результатов
Предел текучести для стали Ст3СП ГОСТ 16523-97 при толщине листов до 10 мм принимается: [σ]т = 255 МПа Для первого расчетного режима при действие двух сил по 1 кН каждая, приложенных на площадке 0,25х0,25 м и приложенных на расстоян ...