2.2. Построение исходной системы (сети) доставки груза по сухопутному участку

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

4.Новоалексеевка

6.Яркое поле

8.Феодосия

2.Мелито

поль

9.Ленино

1.Орехов

12.Керчь

3.Токмак

11.Белогорск

5.Веселое

7.Партизаны

10.Джанкой

Источник – Орехов, сток –Керчь

Бердянск

Пологи

Згуровка

Подол

Керчь Паром

Джанкой

Остер

Керчь

Черкассы

Кировоград

Каховка

Запорожье

Днепропетровск

Кременуг

Источник – Остер, сток – Керчь

Белая Церковь

Умань

Троицкое

Усатово

Киев

Остер

Ильичевск

Кременчуг

Вознесенск

Одесса

55

Источник – Остер, сток – Ильичевск

Каменка

Теплодар

Горское

Остер

Любашевка

Раздельная

Ильичевск

Петровка

Жовтень

Хлебодарское

Источник – Остер, сток - Ильичевск

2.3. Нахождение оптимального маршрута

Задача состоит в отыскании кратчайшего расстояния в транспортных сетях, представленных ранее. Рассматриваемые транспортные сети являются ацикличными, т.е. не содержат циклов.

Представляем найденные расстояния в табличной форме для каждой сети.

В соответствии с формулой (2.1) определяем потенциалы и находим для каждого узла сети.

U_j = min{U_i + d_ij} (2.1)

где d_ij – расстояния между связными узлами i и j;

U_j – кратчайшее расстояние между узлами 1 и j.

Сеть 1. Орехов - Керчь

	1	2	3	4	5	6	7	8	9	10	11	12
1		98	52
2				99
3				148	88
4						166
5							126
6								38
7								213		79
8									46
9												55
10											93
11												168
12

U₁ = 0

U₂ = U1 + d12 = 0 + 98= 98 (из узла 1)

U₃ = U1 + d₁₃ = 0 + 52 = 52 (из узла 1)

U₄ = min{ U₂ + d₂₄ ; U₃+d₃₄} = 98+99=197 (из узла 2)

U₅ = U₃ + d₃₅ = 52+88=140 (из узла 3)

U₆ = U₄ + d₄₆ =197+166=363 (из узла 4)

U₇ = U₅ + d₅₇ = 140+126=266 (из узла 5)

U₈ = min{U₆ + d₆₈; U₇ + d₇₈ } ={363+38;266+213}=401 (из узла 6)

U₉=U₈+d₈₉=401+46=447 (из узла 8)

U₁₀=U₇+d₇₁₀=266+79=345 (из узла 7)

U₁₁=U₁₀+d₁₀₁₁=345+93=438 (из узла 10)

U₁₂=min{U₉+d₉₁₂;U₁₁+d₁₁₁₂}=min{447+55;438+168}=502 (из узла 9)

Применяемый алгоритм нахождения маршрута следования в сетевом варианте позволил определить:

- минимальное расстояние между Ореховом и Керчью;

- построить оптимальный маршрут следования: 1-2-4-6-8-9-12.

Итак, минимальное расстояние составляет 502 км.

Сеть 2. Остер - Керчь

	1	2	3	4	5	6	7	8	9	10	11	12	13	14
1		109	261
2				240
3					134	178
4							394
5								293
6									163
7										124
8												174
9											104
10													206
11												272
12														229
13														15
14

U₁ = 0

U₂ = U₁ + d₁₂ = 0 +109 =109 (из узла 1)

U₃ = U₁ + d₁₃ = 0 +261=261 (из узла 1)

U₄ = U₂ + d₂₄= 109+240=349(из узла 2)

U₅ = U₃+ d₃₅ =261+134 = 395 (из узла 3)

U₆ = U₃+ d₃₆=261+178=439 (из узла 3)

U₇ = U₄+ d₄₇=349+394=743 (из узла 4)

U₈ = U₅+ d₅₈= 395+293= 688 (из узла 5)

U₉= U₆+ d₆₉= 439+163= 602 (из узла 6)

U₁₀ = U₇+ d_{7 10}= 743+124= 867 (из узла 7)

U₁₁ = U₉+ d₉₁₁ =602+104= 706 (из узла 9)

U₁₂ = min{U₈+ d_{8 12}; U₁₁+d_{11 12}}= min{688+174;706+272}= 862 (из узла 8)

U₁₃=U₁₀+d₁₀₁₃=867+206=1073 (из узла 10)

U₁₄= min{U₁₂+d₁₂₁₄;U₁₃+d₁₃₁₄}=min{862+229;1073+15}=1088 (из узла 13)

Применяемый алгоритм нахождения маршрута следования в сетевом варианте позволил определить:

- минимальное расстояние между Остером и Керчью;

- построить оптимальный маршрут следования: 1-2-4-7-10-13-14

Итак, минимальное расстояние составляет 1088 км.

Сеть 3. Остер - Ильичевск

U₁ = 0

U₂ = U₁ + d₁₂ = 0 +71 =71 (из узла 1)

U₃ = U₂ + d₂₃ = 71 +302= 373 (из узла 2)

U₄ = U₂+ d₂₄ = 71+91= 162 (из узла2)

U₅ = U₄ +d₄₅= 162+128 =290 (из узла 4)

U₆ = min{U₃+d₃₆; U₅ + d₅₆}=min{373+287;290+201}=491 (из узла 5)

U₇=U₅+d₅₇=290+98=388 (из узла 5)

U₈=U₆+d₆₈=491+151=642 (из узла 6)

U₉=U₇+d₇₉=388+135=523 (из узла 7)

U₁₀=min{U₈+d₈₁₀;U₉+d₉₁₀}=min{642+27;523+29}=552 (из узла 9)

Применяемый алгоритм нахождения маршрута следования в сетевом варианте позволил определить:

- минимальное расстояние между Остером и Ильичевском;

- построить оптимальный маршрут следования: 1-2-4-5-7-9-10.

Итак, минимальное расстояние составляет 586 км.

Сеть 4 Платоново – Ильичевск

	1	2	3	4	5	6	7	8	9	10
1		71
2			302	91
3						287
4					128
5						201	98
6								151
7									135
8										27
9										29
	1	2	3	4	5	6	7	8	9	10

U₁ = 0

U₂ = U₁ + d₁₂ = 0 +89 =89 (из узла 1)

U₃ = U₁ + d₁₃ = 89 +102= 191 (из узла 1)

U₄ = U₂+ d₂₄ = 89+51= 140 (из узла2)

U₅ = min{U₂ +d₂₅;U₃+d₃₅}= min{89+28;191+127} =117 (из узла 2)

U₆ = U₃+d₃₆=191+71=262 (из узла 3)

U₇=U₄+d₄₇=140+15=155 (из узла 4)

U₈=U₅+d₅₈=117+85=202 (из узла 5)

U₉=U₆+d₆₉=262+93=355 (из узла 6)

U₁₀=min{U₇+d₇₁₀; U₈+d₈₁₀;U₉+d₉₁₀}=min{155+55;202+110;355+25}=210 (из узла 7)

Применяемый алгоритм нахождения маршрута следования в сетевом варианте позволил определить:

- минимальное расстояние между Платоново и Ильичевском (210 км).

- построить оптимальные маршрут следования 1-2-4-7-10.

Итак, минимальное расстояние составляет 210 км.