- •Кафедра организации и управления перевозками на транспорте пояснительная записка
- •1 Постановка задачи
- •2 Определение расстояний перевозки
- •2.1 Пункты отправления – пункты назначения (первый вид транспорта)
- •2.2 Пункты взаимодействия – пункты назначения (второй вид транспорта)
- •2.3 Пункты отправления – пункты взаимодействия (первый вид транспорта)
- •2.3.1 Пункт d4
- •2.3.2 Пункт d3
- •3Определение стоимости перевозки
- •3.1 Первый вид транспорта
- •3.2 Второй вид транспорта
- •4 Решение задачи
- •Заключение
- •Список литературы
2.3.2 Пункт d3
Построим маршруты в узел 18 (пункт D3) из узлов 1 (пункт A1), 2 (пункт A2), 3 (пункт A3),4 (пуект A4) .
Приближение k=0.
Определим длины прямых (без посещения промежуточных узлов) маршрутов в узел 18. Для каждого j-го узла (j = 13, 15), который соединен дугой с узлом 18 (т.е. имеется прямой маршрут), длина U0j кратчайшего маршрута принимается равной расстоянию Lj-18 между этим узлом и узлом 18; для остальных узлов значения U0j принимаются равными бесконечности:
U08 = L13-18 = 12;
U09 = L15-18 = 22.
Полученные маршруты и значения их длин U0j занесем в таблицу 11.
Приближение k=1.
Определим длину L1i-j возможного маршрута из i-го узла в узел 18 (пункт D3), проходящего через j-й узел, с числом промежуточных узлов не более одного как сумму расстояния Li-j от i-го узла до j-го узла и длины U0j прямого маршрута из этого узла в узел 18 (пункт D3):
L1i-j = Li-j + U0j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ≠ 18, j ≠ 18, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 18 (пункт D3) принимается минимальное из возможных значений:
U1i = min {L1i-j}.
Таблица 8 – Маршруты в узел 18 с числом промежуточных узлов не более одного
Из узла 14 |
j |
L14-j |
U0j |
L114-j |
U114 |
14- 13-18 |
13 |
9 |
12 |
21 |
21 |
14-15-18 |
15 |
15 |
22 |
37 |
|
Из узла 17 |
j |
L17-j |
U0j |
L117-j |
U117 |
17- 15-18 |
15 |
7 |
22 |
29 |
29 |
Из узла 12 |
j |
L6-j |
U0j |
L16-j |
U16 |
12-13-18 |
13 |
6 |
12 |
18 |
18 |
12-15-18 |
15 |
2 |
22 |
24 |
|
Из узла 11 |
j |
L11-j |
U0j |
L111-j |
U111 |
11-15-18 |
15 |
9 |
22 |
31 |
31 |
Из узла 9 |
j |
L9-j |
U0j |
L19-j |
U19 |
9-13-18 |
13 |
40 |
12 |
52 |
52 |
Из узла 10 |
j |
L10-j |
U0j |
L110-j |
U110 |
10-15-18 |
15 |
10 |
22 |
32 |
32 |
Из узла 8 |
j |
L8-j |
U0j |
L18-j |
U18 |
8-13-18 |
13 |
12 |
12 |
24 |
24 |
Полученные кратчайшие маршруты из каждого узла в узел 18 и значения их длин U1j (выделены заливкой) занесем в таблицу 11.
Приближение k=2.
Определим длину L2i-j возможного маршрута из i-го узла в узел 18 (пункт D3), проходящего через j-й узел, с числом промежуточных узлов не более двух как сумму расстояния Li-j от i-го узла до j-го узла и длины U1j маршрута из этого узла в узел 18 (пункт D3) с числом узлов не более одного:
L2i-j = Li-j + U1j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ≠ 18, j ≠ 18, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 18 (пункт D3) принимается минимальное из возможных значений:
U2i = min {L2i-j}.
Таблица 9 – Маршруты в узел 18 с числом промежуточных узлов не более двух
Из узла 1 |
j |
L1-j |
U1j |
L21-j |
U21 |
1-10-15-18 |
10 |
16 |
32 |
48 |
48 |
1-9-13-18 |
9 |
5 |
52 |
57 |
|
Из узла 2 |
j |
L2-j |
U1j |
L22-j |
U22 |
2-11-15-18 |
11 |
44 |
31 |
75 |
|
2-10-15-18 |
10 |
9 |
32 |
41 |
41 |
Из узла 3 |
j |
L3-j |
U1j |
L23-j |
U23 |
3-12-13-18 |
12 |
20 |
18 |
38 |
38 |
3-11-15-18 |
11 |
9 |
31 |
40 |
|
Из узла 4 |
j |
L4-j |
U1j |
L24-j |
U24 |
4-12-13-18 |
12 |
11 |
18 |
29 |
29 |
Из узла 7 |
j |
L7-j |
U1j |
L27-j |
U27 |
7-8-13-18 |
8 |
3 |
24 |
27 |
27 |
Из узла 8 |
j |
L8-j |
U1j |
L28-j |
U28 |
8-9-13-18 |
9 |
9 |
52 |
61 |
|
8-13-18 |
13 |
12 |
12 |
24 |
24 |
Из узла 9 |
j |
L9-j |
U1j |
L29-j |
U29 |
9-10-15-18 |
10 |
11 |
32 |
43 |
|
9-13-18 |
13 |
40 |
12 |
52 |
|
9-8-13-18 |
9 |
24 |
33 |
33 |
33 |
Из узла 10 |
j |
L10-j |
U1j |
L210-j |
U210 |
10-15-18 |
15 |
10 |
22 |
32 |
32 |
10-11-15-18 |
11 |
4 |
31 |
34 |
|
10-14-13-18 |
14 |
12 |
21 |
33 |
|
Из узла 15 |
j |
L15-j |
U1j |
L215-j |
U215 |
15-12-13-18 |
12 |
2 |
18 |
20 |
20 |
Из узла 14 |
j |
L14-j |
U1j |
L214-j |
U214 |
14-13-18 |
13 |
9 |
12 |
21 |
21 |
Из узла 12 |
j |
L12-j |
U1j |
L212-j |
U212 |
12-13-18 |
13 |
6 |
12 |
18 |
18 |
Из узла 11 |
j |
L11-j |
U1j |
L211-j |
U211 |
11-15-18 |
15 |
9 |
22 |
31 |
31 |
Полученные кратчайшие маршруты из каждого узла в узел 18 и значения их длин U2j (выделены заливкой) занесем в таблицу 11.
Приближение k=3.
Определим длину L3i-j возможного маршрута из i-го узла в узел 18, проходящего через j-й узел, с числом промежуточных узлов не более трех как сумму расстояния Li-j от i-го узла до j-го узла и длины U2j маршрута из этого узла в узел 18 с числом узлов не более одного:
L3i-j = Li-j + U2j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ≠ 18, j ≠ 18, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 18 принимается минимальное из возможных значений:
U3i= min {L3i-j
Таблица 10 – Маршруты в узел 18 с числом промежуточных узлов не более трех
Из узла 1 |
j |
L1-j |
U2j |
L31-j |
U31 |
1-10-15-18 |
10 |
16 |
32 |
48 |
|
1-9-8-13-18 |
9 |
5 |
33 |
38 |
38 |
Из узла 2 |
j |
L2-j |
U2j |
L32-j |
U32 |
2-10-15-18 |
10 |
9 |
32 |
41 |
41 |
2-10-14-13-18 |
10 |
9 |
33 |
42 |
|
Из узла 3 |
j |
L2-j |
U2j |
L32-j |
U32 |
3-12-13-18 |
12 |
20 |
18 |
38 |
38 |
Из узла 4 |
j |
L4-j |
U2j |
L34-j |
U34 |
4-12-13-18 |
12 |
11 |
18 |
29 |
29 |
Из узла 7 |
j |
L7-j |
U1j |
L27-j |
U27 |
7-8-13-18 |
8 |
3 |
24 |
27 |
27 |
Из узла 8 |
j |
L8-j |
U1j |
L28-j |
U28 |
8-13-18 |
13 |
12 |
12 |
24 |
24 |
Из узла 9 |
j |
L9-j |
U1j |
L29-j |
U29 |
9-8-13-18 |
9 |
24 |
33 |
33 |
33 |
Из узла 10 |
j |
L10-j |
U1j |
L210-j |
U210 |
10-15-12-13-18 |
15 |
10 |
20 |
30 |
30 |
10-15-18 |
15 |
10 |
22 |
32 |
|
Из узла 11 |
j |
L11-j |
U1j |
L211-j |
U211 |
11-15-18 |
15 |
9 |
22 |
31 |
31 |
11-10-14-13-18 |
10 |
4 |
33 |
37 |
|
Из узла 12 |
j |
L12-j |
U1j |
L212-j |
U212 |
12-13-18 |
13 |
6 |
12 |
18 |
18 |
Из узла 15 |
j |
L15-j |
U1j |
L215-j |
U215 |
15-12-13-18 |
12 |
2 |
18 |
20 |
20 |
Полученные кратчайшие маршруты из каждого узла в узел 18 и значения их длин U3j (выделены заливкой) занесем в таблицу 11.
Приближение k=4
Определим длину L4i-j возможного маршрута из i-го узла в узел 18, проходящего через j-й узел, с числом промежуточных узлов не более четырех как сумму расстояния Li-j от i-го узла до j-го узла и длины U3j маршрута из j-го узла в узел 18 с числом узлов не более трех:
L4i-j = Li-j + U3j , i = 1, 2, ... 17, j = 1, 2, ... 17, i ≠ 18, j ≠ 18, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 18 принимается минимальное значение из возможных:
U4i = min {L4i-j}.
Результаты расчетов показывают, что длины кратчайших маршрутов U4i с числом промежуточных узлов не более четырех оказываются равными длинам кратчайших маршрутов U3i с числом промежуточных узлов не более трех. В связи с этим дальнейшие расчеты прекращаются.
В таблице 11 для каждого приближения приведены полученные кратчайшие маршруты в узел 18 и их длины.
Таблица 11 – Кратчайшие маршруты в узел 18
J |
k=0 |
k=1 |
K=2 |
k=3 |
k=4 | |||||
Маршрут |
U0j |
Маршрут |
U1j |
Маршрут |
U2j |
Маршрут |
U3j |
Маршрут |
U4j | |
1 |
|
|
|
|
1-10-15-18 |
48 |
1-9-8-13-18 |
38 |
1-9-8-13-18 |
38 |
2 |
|
|
|
|
2-10-15-18 |
41 |
2-10-15-18 |
41 |
2-10-15-12-13-18 |
39 |
3 |
|
|
|
|
3-12-13-18 |
38 |
3-12-13-18 |
38 |
3-12-13-18 |
38 |
4 |
|
|
|
|
4-12-13-18 |
29 |
4-12-13-18 |
29 |
4-12-13-18 |
29 |
5 |
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
7-8-13-18 |
27 |
7-8-13-18 |
27 |
7-8-13-18 |
27 |
8 |
|
|
8-13-18 |
24 |
8-13-18 |
24 |
8-13-18 |
24 |
8-13-18 |
24 |
9 |
|
|
9-13-18 |
52 |
9-8-13-18 |
33 |
9-8-13-18 |
33 |
9-8-13-18 |
33 |
10 |
|
|
10-15-18 |
32 |
10-15-18 |
32 |
10-15-12-13-18 |
30 |
10-15-12-13-18 |
30 |
11 |
|
|
11-15-18 |
31 |
11-15-18 |
31 |
11-15-18 |
31 |
11-15-18 |
31 |
12 |
|
|
12-13-18 |
18 |
12-13-18 |
18 |
12-13-18 |
18 |
12-13-18 |
18 |
13 |
13-18 |
12 |
13-18 |
12 |
13-18 |
12 |
13-18 |
12 |
13-18 |
12 |
14 |
|
|
14-13-18 |
21 |
14-13-18 |
21 |
14-13-18 |
21 |
14-13-18 |
21 |
15 |
15-18 |
22 |
15-18 |
22 |
15-12-13-18 |
20 |
15-12-13-18 |
20 |
15-12-13-18 |
20 |
16 |
|
|
|
|
|
|
|
|
|
|
17 |
|
|
|
|
|
|
|
|
|
|
Искомые кратчайшие маршруты в узел 18 (пункт D3)
из узла 1 (пункт А1): 1-9-8-13-18 (А1-Е3-Е2- Е7-D3); расстояние перевозки 38;
из узла 2 (пункт А2): 2-10-15-12-13-18 (A2-E4-E9-E6- E7-D3); расстояние перевозки 39;
из узла 3 (пункт А3): 3-12-13-18 (A3-E6-E7-D3); расстояние перевозки 38;
из узла 4 (пункт А4): 4-12-13-18 (A4-E6-E7-D3); расстояние перевозки 29.
В таблице 12 приведены расстояния между пунктами отправления и пунктами назначения.
Таблица 12 – Расстояния между пунктами
отправления и взаимодействия
|
Пункты | |||||
Расстояние, км |
взаимодействия | |||||
|
D1 |
D2 |
D3 |
D4 | ||
Пункт отправления |
A1 |
96 |
33 |
38 |
37 | |
A2 |
75 |
26 |
39 |
30 | ||
A3 |
36 |
25 |
38 |
34 | ||
A4 |
20 |
20 |
29 |
35 | ||
A5 |
80 |
23 |
48 |
120 | ||
A6 |
140 |
92 |
26 |
54 |