2.3.2 Пункт d3
Построим маршруты в узел 15 (пункт D3) из узлов 1 (пункт A1), 2 (пункт A2), 3 (пункт A3), 4 (пункт A4).
1). Приближение k=0.
Определим длины прямых (без посещения промежуточных узлов) маршрутов в узел 15. Для каждого j-го узла (j = 10, 12), который соединен дугой с узлом 15 (т.е. имеется прямой маршрут), длина U0j кратчайшего маршрута принимается равной расстоянию Lj-15 между этим узлом и узлом 15; для остальных узлов значения U0j принимаются равными бесконечности:
U010 = L10-15 = 9;
U012 = L12-15 = 9.
Полученные маршруты и значения их длин U0j занесем в таблицу 12.
2). Приближение k=1.
Определим длину L1i-j возможного маршрута из i-го узла в узел 15 (пункт D3), проходящего через j-й узел, с числом промежуточных узлов не более одного как сумму расстояния Li-j от i-го узла до j-го узла и длины U0j прямого маршрута из этого узла в узел 15 (пункт D3):
L1i-j = Li-j + U0j , i = 1, 2, ... 14, j = 1, 2, ... 14, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 15 (пункт D3) принимается минимальное из возможных значений:
U1i = min {L1i-j}.
Таблица 9 – Маршруты в узел 15 с числом промежуточных узлов не более одного
|
Из узла 3 |
j |
L3-j |
U0j |
L13-j |
U13 |
|
3- 10-15 |
10 |
23 |
9 |
32 |
32 |
|
Из узла 4 |
j |
L4-j |
U0j |
L14-j |
U14 |
|
4- 12-15 |
12 |
11 |
9 |
20 |
20 |
|
Из узла 6 |
j |
L6-j |
U0j |
L16-j |
U16 |
|
6- 12-15 |
12 |
56 |
9 |
65 |
65 |
|
Из узла 9 |
j |
L9-j |
U0j |
L19-j |
U19 |
|
9- 10-15 |
10 |
2 |
9 |
11 |
11 |
|
9- 12-15 |
12 |
10 |
9 |
19 |
|
|
Из узла 10 |
j |
L10-j |
U0j |
L110-j |
U110 |
|
10- 15 |
15 |
9 |
|
9 |
9 |
|
Из узла 11 |
j |
L11-j |
U0j |
L111-j |
U111 |
|
11- 12-15 |
12 |
4 |
9 |
13 |
13 |
|
Из узла 12 |
j |
L12-j |
U0j |
L112-j |
U112 |
|
12- 15 |
15 |
9 |
|
9 |
9 |
|
Из узла 13 |
j |
L13-j |
U0j |
L113-j |
U113 |
|
13- 10-15 |
10 |
8 |
9 |
17 |
17 |
|
13- 12-15 |
12 |
9 |
9 |
18 |
|
Полученные кратчайшие маршруты из каждого узла в узел 15 и значения их длин U1j (выделены заливкой) занесем в таблицу 12.
3). Приближение k=2.
Определим длину L2i-j возможного маршрута из i-го узла в узел 15 (пункт D3), проходящего через j-й узел, с числом промежуточных узлов не более двух как сумму расстояния Li-j от i-го узла до j-го узла и длины U1j маршрута из этого узла в узел 15 (пункт D3) с числом узлов не более одного:
L2i-j = Li-j + U1j , i = 1, 2, ... 14, j = 1, 2, ... 14, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 15 (пункт D3) принимается минимальное из возможных значений:
U2i = min {L2i-j}.
Таблица 10 – Маршруты в узел 15 с числом промежуточных узлов не более двух
|
Из узла 2 |
j |
L2-j |
U1j |
L22-j |
U22 |
|
2- 9-10-15 |
9 |
4 |
11 |
15 |
15 |
|
Из узла 3 |
j |
L3-j |
U1j |
L23-j |
U23 |
|
3- 6-12-15 |
6 |
56 |
65 |
121 |
|
|
3- 9-10-15 |
9 |
11 |
11 |
22 |
22 |
|
3- 10-15 |
10 |
23 |
9 |
32 |
|
|
Из узла 4 |
j |
L4-j |
U1j |
L24-j |
U24 |
|
4- 12-15 |
12 |
11 |
9 |
20 |
20 |
|
Из узла 5 |
j |
L5-j |
U1j |
L25-j |
U25 |
|
5- 11-12-15 |
11 |
45 |
13 |
58 |
58 |
|
Из узла 6 |
j |
L6-j |
U1j |
L26-j |
U26 |
|
6- 3-10-15 |
3 |
56 |
32 |
88 |
|
|
6- 9-10-15 |
9 |
68 |
11 |
79 |
|
|
6- 12-15 |
12 |
56 |
9 |
65 |
65 |
|
Из узла 7 |
j |
L7-j |
U1j |
L27-j |
U27 |
|
7- 11-12-15 |
11 |
13 |
13 |
26 |
26 |
|
Из узла 8 |
j |
L8-j |
U1j |
L28-j |
U28 |
|
8- 9-10-15 |
9 |
18 |
11 |
29 |
29 |
|
8- 11-12-15 |
11 |
32 |
13 |
45 |
|
|
Из узла 9 |
j |
L9-j |
U1j |
L29-j |
U29 |
|
9- 3-10-15 |
3 |
11 |
32 |
43 |
|
|
9- 6-12-15 |
6 |
68 |
65 |
133 |
|
|
9- 10-15 |
10 |
2 |
9 |
11 |
11 |
|
9- 12-15 |
12 |
10 |
9 |
19 |
|
|
9- 13-10-15 |
13 |
12 |
17 |
29 |
|
|
Из узла 10 |
j |
L10-j |
U1j |
L210-j |
U210 |
|
10- 15 |
15 |
9 |
|
9 |
9 |
|
Из узла 11 |
j |
L11-j |
U1j |
L211-j |
U211 |
|
11- 12-15 |
12 |
4 |
9 |
13 |
13 |
|
Из узла 12 |
j |
L12-j |
U1j |
L212-j |
U212 |
|
12- 9-10-15 |
9 |
10 |
11 |
21 |
|
|
12- 13-10-15 |
13 |
9 |
17 |
26 |
|
|
12- 15 |
15 |
9 |
|
9 |
9 |
|
Из узла 13 |
j |
L13-j |
U1j |
L213-j |
U213 |
|
13- 9-10-15 |
9 |
12 |
11 |
23 |
|
|
13- 10-15 |
10 |
8 |
9 |
17 |
17 |
|
13- 12-15 |
12 |
9 |
9 |
18 |
|
|
Из узла 14 |
j |
L14-j |
U1j |
L214-j |
U214 |
|
14- 6-12-15 |
6 |
4 |
65 |
69 |
|
|
14- 11-12-15 |
11 |
3 |
13 |
16 |
16 |
Полученные кратчайшие маршруты из каждого узла в узел 15 и значения их длин U2j (выделены заливкой) занесем в таблицу 12.
4). Приближение k=3.
Определим длину L3i-j возможного маршрута из i-го узла в узел 15, проходящего через j-й узел, с числом промежуточных узлов не более трех как сумму расстояния Li-j от i-го узла до j-го узла и длины U2j маршрута из этого узла в узел 15 с числом узлов не более одного:
L3i-j = Li-j + U2j , i = 1, 2, ... 14, j = 1, 2, ... 14, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 15 принимается минимальное из возможных значений:
U3i = min {L3i-j}.
Таблица 11 – Маршруты в узел 15 с числом промежуточных узлов не более трех
|
Из узла 1 |
j |
L1-j |
U2j |
L31-j |
U31 |
|
1- 7-11-12-15 |
7 |
8 |
26 |
34 |
34 |
|
1- 8-9-10-15 |
8 |
34 |
29 |
63 |
|
|
Из узла 2 |
j |
L2-j |
U2j |
L32-j |
U32 |
|
2- 5-11-12-15 |
5 |
5 |
58 |
63 |
|
|
2- 8-9-10-15 |
8 |
44 |
29 |
73 |
|
|
2- 9-10-15 |
9 |
4 |
11 |
15 |
15 |
|
Из узла 3 |
j |
L2-j |
U2j |
L32-j |
U32 |
|
3- 6-12-15 |
6 |
56 |
65 |
121 |
|
|
3- 9-10-15 |
9 |
11 |
11 |
22 |
22 |
|
3- 10-15 |
10 |
23 |
9 |
32 |
|
|
Из узла 4 |
j |
L4-j |
U2j |
L34-j |
U34 |
|
4- 12-15 |
12 |
11 |
9 |
20 |
20 |
|
Из узла 5 |
j |
L5-j |
U2j |
L35-j |
U35 |
|
5- 2-9-10-15 |
2 |
5 |
15 |
20 |
20 |
|
5- 11-12-15 |
11 |
45 |
13 |
58 |
|
|
Из узла 6 |
j |
L6-j |
U2j |
L36-j |
U36 |
|
6- 3-9-10-15 |
3 |
56 |
22 |
78 |
|
|
6- 9-10-15 |
9 |
68 |
11 |
79 |
|
|
6- 12-15 |
12 |
56 |
9 |
65 |
|
|
6- 14-11-12-15 |
14 |
4 |
16 |
20 |
20 |
|
Из узла 7 |
j |
L7-j |
U2j |
L37-j |
U37 |
|
7- 8-9-10-15 |
8 |
12 |
29 |
41 |
|
|
7- 11-12-15 |
11 |
13 |
13 |
26 |
26 |
|
Из узла 8 |
j |
L8-j |
U2j |
L38-j |
U38 |
|
8- 2-9-10-15 |
2 |
44 |
15 |
59 |
|
|
8- 7-11-12-15 |
7 |
12 |
26 |
38 |
|
|
8- 9-10-15 |
9 |
18 |
11 |
29 |
|
|
8- 11-12-15 |
11 |
32 |
13 |
45 |
|
|
8- 14-11-12-15 |
14 |
5 |
16 |
21 |
21 |
|
Из узла 9 |
j |
L9-j |
U2j |
L39-j |
U39 |
|
9- 6-12-15 |
6 |
68 |
65 |
133 |
|
|
9- 10-15 |
10 |
2 |
9 |
11 |
11 |
|
9- 12-15 |
12 |
10 |
9 |
19 |
|
|
9- 13-10-15 |
13 |
12 |
17 |
29 |
|
|
Из узла 10 |
j |
L10-j |
U2j |
L310-j |
U310 |
|
10- 15 |
15 |
9 |
|
9 |
9 |
|
Из узла 11 |
j |
L11-j |
U2j |
L311-j |
U311 |
|
11- 8-9-10-15 |
8 |
32 |
29 |
61 |
|
|
11- 12-15 |
12 |
4 |
9 |
13 |
13 |
|
Из узла 12 |
j |
L12-j |
U2j |
L312-j |
U312 |
|
12- 9-10-15 |
9 |
10 |
11 |
21 |
|
|
12- 13-10-15 |
13 |
9 |
17 |
26 |
|
|
12- 15 |
15 |
9 |
|
9 |
9 |
|
Из узла 13 |
j |
L13-j |
U2j |
L313-j |
U313 |
|
13- 9-10-15 |
9 |
12 |
11 |
23 |
|
|
13- 10-15 |
10 |
8 |
9 |
17 |
17 |
|
13- 12-15 |
12 |
9 |
9 |
18 |
|
|
Из узла 14 |
j |
L14-j |
U2j |
L314-j |
U314 |
|
14- 6-12-15 |
6 |
4 |
65 |
69 |
|
|
14- 8-9-10-15 |
8 |
5 |
29 |
34 |
|
|
14- 11-12-15 |
11 |
3 |
13 |
16 |
16 |
Полученные кратчайшие маршруты из каждого узла в узел 15 и значения их длин U3j (выделены заливкой) занесем в таблицу 12.
5). Приближение k=4
Определим длину L4i-j возможного маршрута из i-го узла в узел 15, проходящего через j-й узел, с числом промежуточных узлов не более четырех как сумму расстояния Li-j от i-го узла до j-го узла и длины U3j маршрута из j-го узла в узел 15 с числом узлов не более трех:
L4i-j = Li-j + U3j , i = 1, 2, ... 14, j = 1, 2, ... 14, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 15 принимается минимальное значение из возможных:
U4i = min {L4i-j}.
Результаты расчетов показывают, что длины кратчайших маршрутов U4i с числом промежуточных узлов не более четырех оказываются равными длинам кратчайших маршрутов U3i с числом промежуточных узлов не более трех. В связи с этим дальнейшие расчеты прекращаются.
В таблице 12 для каждого приближения приведены полученные кратчайшие маршруты в узел 15 и их длины.
Таблица 12– Кратчайшие маршруты в узел 15
|
j |
k=0 |
k=1 |
k=2 |
k=3 |
k=4 | |||||||
|
Маршрут |
U0j |
Маршрут |
U1j |
Маршрут |
U2j |
Маршрут |
U3j |
Маршрут |
U4j | |||
|
1 |
|
|
|
|
|
|
1-7-11-12-15 |
34 |
1-7-11-12-15 |
34 | ||
|
2 |
|
|
|
|
2-9-10-15 |
15 |
2-9-10-15 |
15 |
2-9-10-15 |
15 | ||
|
3 |
|
|
3-10-15 |
32 |
3-9-10-15 |
22 |
3-9-10-15 |
22 |
3-9-10-15 |
22 | ||
|
4 |
|
|
4-12-15 |
20 |
4-12-15 |
20 |
4-12-15 |
20 |
4-12-15 |
20 | ||
|
5 |
|
|
|
|
5-11-12-15 |
58 |
5-2-9-10-15 |
20 |
5-2-9-10-15 |
20 | ||
|
6 |
|
|
6-12-15 |
65 |
6-12-15 |
65 |
6-14-11-12-15 |
20 |
6-14-11-12-15 |
20 | ||
|
7 |
|
|
|
|
7-11-12-15 |
26 |
7-11-12-15 |
26 |
7-11-12-15 |
26 | ||
|
8 |
|
|
|
|
8-9-10-15 |
29 |
8-14-11-12-15 |
21 |
8-14-11-12-15 |
21 | ||
|
9 |
|
|
9-10-15 |
11 |
9-10-15 |
11 |
9-10-15 |
11 |
9-10-15 |
11 | ||
|
10 |
10-15 |
9 |
10-15 |
9 |
10-15 |
9 |
10-15 |
9 |
10-15 |
9 | ||
|
11 |
|
|
11-12-15 |
13 |
11-12-15 |
13 |
11-12-15 |
13 |
11-12-15 |
13 | ||
|
12 |
12-15 |
9 |
12-15 |
9 |
12-15 |
9 |
12-15 |
9 |
12-15 |
9 | ||
|
13 |
|
|
13-10-15 |
17 |
13-10-15 |
17 |
13-10-15 |
17 |
13-10-15 |
17 | ||
|
14 |
|
|
|
|
14-11-12-15 |
16 |
14-11-12-15 |
16 |
14-11-12-15 |
16 | ||
Искомые кратчайшие маршруты в узел 15 (пункт D3)
из узла 1 (пункт А1): 1-7-11-12-15 (А1-Е3-Е7- Е8-D3); расстояние перевозки 34;
из узла 2 (пункт А2): 2-9-10-15 (A2-E5-E6-D3); расстояние перевозки 15;
из узла 3 (пункт А3): 3-9-10-15 (A3- E5-E6-D3); расстояние перевозки 22;
из узла 4 (пункт А4): 4-12-15 (A4-E8- D3); расстояние перевозки 20.
В таблице 13 приведены расстояния между пунктами отправления и пунктами назначения.
Таблица 13 – Расстояния между пунктами
отправления и взаимодействия
|
Расстояние, км |
Пункты взаимодействия | ||
|
D2 |
D3 | ||
|
Пункты отправления |
А1 |
24 |
34 |
|
А2 |
21 |
15 | |
|
А3 |
28 |
22 | |
|
А4 |
18 |
20 | |