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

Так как приведенная матрица содержит только неотрицательные элементы, то сумма приводящих констант может служить нижней границей длины цикла при исходной матрице С, т. е. является оценкой исходного множества 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. Проверим условие оптимальности. Если оценка полученного замкнутого маршрута не больше оценок всех допустимых для дальнейшего ветвления подмножеств (висячих вершин дерева), то он является оптимальным. Если существует хотя бы одно подмножество с меньшей оценкой, то построенный цикл запоминается. Процесс ветвления продолжается исходя из множества с меньшей оценкой до тех пор, пока нижние границы новых подмножеств остаются меньше длины выделенного цикла. В ходе ветвления либо будет построен цикл меньшей длины, либо обнаружится, что на новых подмножествах он не существует, т. е. оценка для каждого из них не меньше рекорда (длины кратчайшего из ранее полученных циклов).

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

Схема исполнительной группы
Блоки исполнительной группы соединяются 8 струнами: 1 Контрольно – секционное реле – КС 2,3 Сигнальные реле – С, МС 4,5 Маршрутные реле – 1М, 2М 6 Реле разделки маршрута – Р 7,8 Индикация на пульт-табло 2.5.1 Схема контрольно секцио ...

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

Определение необходимого количества автомобилей и выбор недостающих автомобилей
Потребное количество грузовых автомобилей каждой марки па определяется по наибольшей ординате каждого графика машиноиспользования после корректировки. Списочное число Ncn автомобилей по маркам определяется с учетом простоев автомобилей в ...