Отыскание кратчайших расстояний и путей между пунктами транспортной сети. Кратчайшая связывающая сеть

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

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

Отыскание кратчайших расстояний между пунктами транспортной сети возможно по методу потенциалов, методу "метлы", динамическому методу, на основе теории графов (метод Флойда) и др.

Например, задача отыскания кратчайших расстояний между пунктами транспортной сети методом потенциалов решается по следующему алгоритму:

1) Начальному пункту, от которого требуется определить кратчайшие расстояния, присваивается потенциал v_i = 0.

2) Находятся все звенья, для которых начальным пунктам i присвоены потенциалы v_i, а конечным пунктам j не присвоены. Если таких звеньев нет, то решение закончено (на п.5), а иначе на следующий п.3.

3) Для найденных звеньев по п.2 рассчитываются значения потенциалов конечных пунктов j по следующей формуле:

u_j(i) = v_i + l_ij,

где u_{j(i) –} потенциал конечного пункта j звена i-j; l_ij – длина звена i-j.

Из всех полученных потенциалов выбирается потенциал с наименьшим значением, т.е. определяется:

,

где { u_j(i) } – множество значений потенциалов конечных пунктов j звеньев i-j, i-м начальным пунктам которых ранее присвоены потенциалы; u_r(s) – потенциал конечного пункта r звена s-r, являющийся наименьшим по значению элементом множества { u_j(i) }.

Потенциал u_r(s) присваивается соответствующему конечному пункту (v_s = u_r(s)), а звено r-s отмечается стрелкой.

В случае если несколько значений потенциалов множества {v_j(i)} окажутся равными и наименьшими, то необходимо установить, относятся они к одному и тому же пункту или нет.

Если наименьшие равные значения потенциалов относятся к различным пунктам (у потенциалов не совпадают цифровые индексы без скобок), эти значения потенциалов присваиваются всем соответствующим конечным пунктам и стрелками отмечаются соответствующие звенья.

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

4) переход на п. 2

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

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

Таблица 3.2 – Кратчайшие расстояния между пунктами транспортной сети (км)

Пример. Необходимо найти кратчайшие расстояния от пункта 1 до остальных пунктов нижеприведенной транспортной сети (рисунок 3.20).

2 5

6км

5км 6 км

3 11

3 км

0 1 4 11

5 км

6 км

5 6

Рисунок 3.20 – Схема транспортной сети

Решение.

Шаг 1. Начальному пункту 1 присваивается потенциал v₁ = 0 (потенциалы указаны в квадратах).

Шаг 2.

1-й этап. Звенья, начальным пунктам i которых присвоен потенциал v_i, а для конечных пунктов j потенциалы не присвоены: 1-2 и 1-5. Рассчитываются значения потенциалов конечных пунктов j:

u₂₍₁₎ = v₁ + l_1-2 =0+5=5

u₅₍₁₎ = v₁ + l_1-5 =0+6=6

Из рассматриваемых на данном этапе потенциалов находится минимальный

.

Потенциал u₂₍₁₎ присваивается соответствующему конечному пункту (v₂ = u₂₍₁₎ =5), а звено 1-2 отмечается стрелкой.

2-й этап. Звенья, начальным пунктам i которых присвоен потенциал v_i, а для конечных пунктов j потенциалы не присвоены: 1-5, 2-3 и 2-4. Рассчитываются значения потенциалов конечных пунктов j:

u₅₍₁₎ = v₁ + l_1-5 =0+6=6

u₃₍₂₎ = v₂ + l_2-3 =5+6=11

u₄₍₂₎ = v₂ + l_2-4 =5+6=11

Из рассматриваемых на данном этапе потенциалов находится минимальный

.

Потенциал u₅₍₁₎ присваивается соответствующему конечному пункту (v₅ = u₅₍₁₎), а звено 1-5 отмечается стрелкой.

3-й этап. Звенья, начальным пунктам i которых присвоен потенциал v_i, а для конечных пунктов j потенциалы не присвоены:, 2-3, 2-4 и 5-4. Рассчитываются значения потенциалов конечных пунктов j:

u₃₍₂₎ = v₂ + l_2-3 =5+6=11

u₄₍₂₎ = v₂ + l_2-4 =5+6=11

u₄₍₅₎ = v₄ + l_5-4 =6+5=11

Из рассматриваемых на данном этапе потенциалов находится минимальный

.

Минимальное значение потенциалов, равное 11, присваивается соответствующим конечным пунктам v₃=11 и v₄ =11 (первый частный случай), и звено 2-3, а также, например, 2-4 (одно из двух 2-4 и 5-4 – второй частный случай) отмечаются стрелкой.

4-й этап. Так как потенциалы присвоены всем пунктам, то решение закончено.

Алгоритм метода отыскания кратчайших расстояний, который легко реализуется на компьютере, и поясняющая схема приведены на рисунке 3.21. Реализация данного алгоритма в виде компьютерной программы приведено в приложении 7.

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

Один из алгоритмов отыскания кратчайшей связывающей сети следующий:

1) находится звено минимальной длины и включается в КСС;

2) последовательно включаются звенья в КСС:

2.1) находятся звенья, соединенные только одним своим концом с имеющейся частью КСС. Если нет ни одного такого звена, то решение закончено. Иначе переход на следующий пункт 2.2;

2.2) из найденных по п. 2.1 звеньев определяется звено минимальной длины и включается в КСС;

2.3) переход на 2.1.

Кратчайшая связывающая сеть включает ровно m-1 звеньев при числе вершин m.

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

Решение.

1) находим из всех звеньев звено минимальной длины и включаем в КСС сеть (звено 3-4);

2) последовательно включаем звенья в КСС:

1-итерация

2.1.1) выбираем звенья, соединенные только одним своим концом с имеющейся частью КСС. Это звенья 3-2, 4-2 и 4-5.

2.2.1) из выбранных звеньев находим звено минимальной длины и включаем в КСС. Это звено 4-5;

2.3.1) переход на 2.1.2.

2- итерация

2.1.2) выбираем звенья, соединенные только одним своим концом с имеющейся частью КСС. Это звенья 3-2, 4-2 и 5-1.

2.2.2) из выбранных звеньев находим звено минимальной длины и включаем в КСС. Поскольку все звенья равной минимальной длины, то выбираем любое из них, например звено 5 - 1;

2.3.2) переход на 2.1.3.

3- итерация

2.1.3) выбираем звенья, соединенные только одним своим концом с имеющейся частью КСС. Это звенья 3-2, 4-2 и 1-2.

2.2.3) из выбранных звеньев находим звено минимальной длины и включаем в КСС. Это звено 1-2;

переход на 2.1.4.

4- итерация

2.1.4) выбираем звенья, соединенные только одним своим концом с имеющейся частью КСС. Таких звеньев нет. Решение закончено.

Звенья КСС выделены линиями большей толщины (рисунок 3.22).

Пуск

2

Ввод n, ip n – число вершин транспортной сети

ip – признак одностороннего движения (0 – нет, 1 – да);

3 5

ip=1 Нет Ввод s_ij, s_ij –длина звеньев (вводится

; 1Е20, если звена нет)

Да

4 6

s_ij, s_ji =s_ji,

; ,i¹j ;

s_ij=0, i = j

8 16 s_ij –расстояние между пунктами i и j

Вывод s _{i j}, p _{i j} p_ij – промежуточный пункт на пути

; между i и j

9 17

Останов

10 Да S_jk k

s_{j i} > 1E19 S_ik

j S_ji i

Нет

Да 12 Нет 13

s _{i k} > 1E19 c = s _ji + s _{i k}

15 Да 14

s _{j k} = c c < s _jk

p _{j k} = i

Нет Рисунок 3.21 – Алгоритм метода поиска

кратчайших расстояний между пунктами транспортной сети

2

6км

5км 6 км

3 км

1 4

5 км

6 км

Рисунок 3.22 – Схема кратчайшей связывающей сети (жирные линии)

Поиск по сайту: