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

Информация » Стратегия управления доставкой груза на транспорте » Определение оптимального замкнутого маршрута

Страница 3

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

Страницы: 1 2 3 4

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

Уровень унификация и стандартизации
Автомобиль Ford Focus предназначен для перевозки пассажиров (не более 5) и грузов (массой не более 100 кг) по дорогам II и III категорий. Так же данный автомобиль может буксировать прицеп, допустимая полная масса которого не более: – не ...

Техника – экономические особенности видов транспорта
В современном мире выделяют шесть видов транспорта: морской, железнодорожный, автомобильный, речной, воздушный и трубопроводный. Виды транспорта подразделяются на водный (морской, речной), наземный (железнодорожный, автомобильный, трубопр ...

Сменная производительность работы агрегатов
Сменная производительность работы разбрасывателя определяется по следующей формуле: W=0.1Bp Vp tp Vp – рабочая скорость движения агрегата, км/ч; Bp – рабочая ширина захвата агрегата, м; tp – чистое рабочее время, ч. Рабочая скорость ...