- •Кафедра организации и управления перевозками на транспорте пояснительная записка
- •1.Постановка задачи
- •2 Определение расстояний перевозки
- •2.1 Пункты отправления – пункты назначения (первый вид транспорта)
- •2.2 Пункты взаимодействия – пункты назначения (второй вид транспорта)
- •2.3 Пункты отправления – пункты взаимодействия (первый вид транспорта)
- •2.3.1 ПунктD4
- •2.3.2 ПунктD1
- •3 Определение стоимости перевозки
- •3.2 Второй вид транспорта
- •4 Решение задачи
- •Заключение
- •Список литературы
2 Определение расстояний перевозки
2.1 Пункты отправления – пункты назначения (первый вид транспорта)
Как следует из исходных данных, каждый пункт назначения связан с каждым пунктом отправления единственным прямым маршрутом. Следовательно, расстояния между этими пунктами совпадают с расстояниями, приведенными в матрице расстояний между пунктами (таблица 1).
Таблица 1 – Расстояния между пунктами
отправления и назначения
|
Пункты | ||
Расстояние, км |
назначения | ||
|
В1 |
В2 | |
Пункты отправления |
А1 |
24 |
60 |
А2 |
14 |
30 | |
А3 |
56 |
17 | |
A4 |
98 |
68 | |
A5 |
140 |
119 | |
A6 |
182 |
170 |
2.2 Пункты взаимодействия – пункты назначения (второй вид транспорта)
Как следует из исходных данных, каждый пункт назначения связан с каждым пунктом взаимодействия единственным прямым маршрутом. Следовательно, расстояния между этими пунктами совпадают с расстояниями, приведенными в матрице расстояний между пунктами (таблица 2).
Таблица 2 – Расстояния между пунктами
взаимодействия и назначения
|
Пункты | ||
Расстояние, км |
назначения | ||
|
В1 |
В2 | |
Пункты взаимодействия |
D1 |
84 |
51 |
D2 |
126 |
102 | |
D3 |
186 |
153 | |
D4 |
210 |
204 |
2.3 Пункты отправления – пункты взаимодействия (первый вид транспорта)
Из матрицы расстояний видно, что прямых маршрутов между пунктами Ak (k = 1...4) отправления и пунктами Di (i = 3...4) взаимодействия нет. Между пунктами Ak (k = 1...6) отправления и пунктами Di (i = 1...2) взаимодействия есть, пока его учитывать не будем. Необходимо построить кратчайшие маршруты, пролегающие через промежуточные пункты Es (s = 1...9), и определить длины этих маршрутов.
Сформируем матрицу расстояний между пунктами Ak отправления, промежуточными пунктами Es, пунктами Di взаимодействия; введем сквозную нумерацию узлов (таблица 3).
2.3.1 ПунктD4
Построим маршруты в узел 19 (пункт D4) из узлов 1 (пункт A1), 2 (пункт A2), 3 (пункт A3),4 (пункт A4) .
1). Приближение k=0.
Определим длины прямых (без посещения промежуточных узлов) маршрутов в узел 19. Для каждого j-го узла (j = 12, 14), который соединен дугой с узлом 19 (т.е. имеется прямой маршрут), длина U0j кратчайшего маршрута принимается равной расстоянию Lj-19 между этим узлом и узлом 19; для остальных узлов значения U0j принимаются равными бесконечности:
U09 = L12-19 = 33;
U010 = L14-19 = 9.
Полученные маршруты и значения их длин U0j занесем в таблицу 7.
Таблица 3 – Матрица расстояний между пунктами отправления, взаимодействия и промежуточными пунктами
Пункты |
А1 |
А2 |
А3 |
А4 |
А5 |
А6 |
E1 |
E2 |
E3 |
E4 |
E5 |
E6 |
E7 |
E8 |
E9 |
D1 |
D2 |
D3 |
D4 | |
|
Узлы |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
А1 |
1 |
|
|
|
|
|
|
|
|
5 |
16 |
|
|
|
|
|
96 |
33 |
|
|
А2 |
2 |
|
|
|
|
|
|
|
|
|
9 |
44 |
|
|
|
|
75 |
26 |
|
|
А3 |
3 |
|
|
|
|
|
|
|
|
|
|
9 |
20 |
|
|
|
36 |
25 |
|
|
А4 |
4 |
|
|
|
|
|
|
|
|
|
|
|
11 |
|
|
|
20 |
20 |
|
|
А5 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
80 |
23 |
48 |
120 |
А6 |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
140 |
92 |
26 |
54 |
E1 |
7 |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
E2 |
8 |
|
|
|
|
|
|
3 |
|
9 |
|
|
|
12 |
|
|
|
|
|
|
E3 |
9 |
5 |
|
|
|
|
|
|
9 |
|
11 |
|
|
40 |
|
|
|
|
|
|
E4 |
10 |
16 |
9 |
|
|
|
|
|
|
11 |
|
4 |
|
|
12 |
10 |
|
|
|
|
E5 |
11 |
|
44 |
9 |
|
|
|
|
|
|
4 |
|
|
|
|
9 |
|
|
|
|
E6 |
12 |
|
|
20 |
11 |
|
|
|
|
|
|
|
|
6 |
|
2 |
|
|
|
33 |
E7 |
13 |
|
|
|
|
|
|
|
12 |
40 |
|
|
6 |
|
9 |
|
|
|
12 |
|
E8 |
14 |
|
|
|
|
|
|
|
|
|
12 |
|
|
9 |
|
15 |
|
|
|
9 |
E9 |
15 |
|
|
|
|
|
|
|
|
|
10 |
9 |
2 |
|
15 |
|
|
|
|
|
D1 |
16 |
96 |
75 |
36 |
20 |
80 |
140 |
|
|
|
|
|
|
|
|
|
|
|
|
|
D2 |
17 |
33 |
26 |
25 |
20 |
23 |
92 |
|
|
|
|
|
|
|
|
7 |
|
|
|
|
D3 |
18 |
|
|
|
|
48 |
26 |
|
|
|
|
|
|
12 |
|
22 |
|
|
|
|
D4 |
19 |
|
|
|
|
120 |
54 |
|
|
|
|
|
33 |
|
9 |
|
|
|
|
|
2) Приближение k=1.
Определим длину L1i-j возможного маршрута из i-го узла в узел 19, проходящего через j-й узел, с числом промежуточных узлов не более одного как сумму расстояния Li-j от i-го узла до j-го узла и длины U0j прямого маршрута из этого узла в узел 19:
L1i-j = Li-j + U0j , i = 1, 2, ... 18, j = 1, 2, ... 19, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 19 принимается минимальное из возможных значений:
U1i = min {L1i-j}.
Таблица 4 – Маршруты в узел 19 с числом промежуточных узлов не более одного
Из узла 13 |
j |
L13-j |
U0j |
L113-j |
U113 |
13-14-19 |
14 |
9 |
9 |
18 |
18 |
13-12-19 |
12 |
6 |
33 |
39 |
|
Из узла 15 |
j |
L15-j |
U0j |
L115-j |
U115 |
15-14-19 |
14 |
15 |
9 |
24 |
24 |
15-12-19 |
12 |
2 |
33 |
35 |
|
Из узла 10 |
j |
L10-j |
U0j |
L110-j |
U110 |
10-14-12 |
14 |
12 |
9 |
21 |
21 |
Из узла 3 |
j |
L3-j |
U0j |
L13-j |
U13 |
3-12-19 |
12 |
20 |
33 |
53 |
53 |
Из узла 4 |
j |
L4-j |
U0j |
L14-j |
U14 |
4-12-19 |
12 |
11 |
33 |
44 |
44 |
Полученные кратчайшие маршруты из каждого узла в узел 19 и значения их длин U1j (выделены заливкой) занесем в таблицу 7.
3) Приближение k=2.
Определим длину L2i-j возможного маршрута из i-го узла в узел 19, проходящего через j-й узел, с числом промежуточных узлов не более двух как сумму расстояния Li-j от i-го узла до j-го узла и длины U1j маршрута из j-го узла в узел 19 с числом узлов не более одного:
L2i-j = Li-j + U1j , i = 1, 2, ... 18, j = 1, 2, ... 19, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 19 принимается минимальное значение из возможных:
U2i = min {L2i-j}.
Таблица 5 – Маршруты в узел 19 с числом промежуточных узлов не более двух
Из узла 8 |
j |
L8-j |
U1j |
L28-j |
U28 |
8-13-14-19 |
13 |
12 |
18 |
30 |
30 |
8-13-12-19 |
13 |
12 |
39 |
51 |
|
Из узла 9 |
j |
L9-j |
U1j |
L29-j |
U29 |
9-13-12-19 |
13 |
40 |
39 |
79 |
|
9-13-14-19 |
13 |
40 |
18 |
58 |
58 |
Из узла 10 |
j |
L10-j |
U1j |
L210-j |
U210 |
Продолжение таблицы 5- Маршруты в узел 19 с числом узлов не более двух
| |||||
10-15-12-19 |
15 |
10 |
35 |
45 |
|
10-15-14-19 |
15 |
10 |
24 |
34 |
34 |
10-14-19 |
14 |
|
21 |
21 |
21 |
Из узла 11 |
j |
L11-j |
U1j |
L211-j |
U211 |
11-15-14-19 |
15 |
9 |
24 |
33 |
|
11-10-14-19 |
10 |
4 |
21 |
25 |
25 |
Из узла 12 |
j |
L12-j |
U1j |
L212-j |
U212 |
12-19 |
12 |
|
|
33 |
|
12-15-14-19 |
15 |
2 |
24 |
26 |
|
12-13-14-19 |
13 |
6 |
18 |
24 |
24 |
Из узла 1 |
j |
L1-j |
U1j |
L21-j |
U21 |
1-10-14-19 |
10 |
16 |
21 |
37 |
37 |
Из узла 2 |
j |
L2-j |
U1j |
L22-j |
U22 |
2-10-14-19 |
10 |
9 |
21 |
30 |
30 |
|
Полученные кратчайшие маршруты из каждого узла в узел 19 и значения их длин U2j (выделены заливкой) занесем в таблицу 7.
4) Приближение k=3.
Определим длину L3i-j возможного маршрута из i-го узла в узел 19, проходящего через j-й узел, с числом промежуточных узлов не более трех как сумму расстояния Li-j от i-го узла до j-го узла и длины U2j маршрута из j-го узла в узел 19 с числом узлов не более двух:
L3i-j = Li-j + U2j , i = 1, 2, ... 18, j = 1, 2, ... 19, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 19 принимается минимальное из возможных значение:
U3i = min {L3i-j}.
Таблица 6 – Маршруты в узел 19 с числом промежуточных узлов не более трех
Из узла 1 |
j |
L1-j |
U2j |
L31-j |
U31 |
1- 10-14-19 |
10 |
16 |
21 |
37 |
37 |
1-9-13-14-19 |
9 |
5 |
58 |
63 |
|
1-10-15-14-19 |
10 |
16 |
34 |
50 |
|
Продолжение таблицы 6- Маршруты в узел 19 с числом узлов не более трех
Из узла 2 |
j |
L2-j |
U2j |
L32-j |
U32 |
2- 10-14-19 |
10 |
9 |
21 |
30 |
30 |
2-10-15-14-19 |
10 |
9 |
34 |
43 |
|
2-11-10-14-19 |
11 |
44 |
25 |
69 |
|
Из узла 3 |
j |
L3-j |
U2j |
L33-j |
U33 |
3-12-19 |
12 |
20 |
33 |
53 |
|
3-11-10-14-19 |
11 |
9 |
25 |
34 |
34 |
Из узла 4 |
j |
L4-j |
U2j |
L34-j |
U34 |
4-12-19 |
12 |
11 |
33 |
44 |
|
4-12-15-14-19 |
12 |
11 |
26 |
37 |
|
4-12-13-14-19 |
12 |
11 |
24 |
35 |
35 |
Из узла 8 |
j |
L8-j |
U1j |
L28-j |
U28 |
8-13-14-19 |
13 |
12 |
18 |
30 |
30 |
8-13-12-19 |
13 |
12 |
39 |
51 |
|
Из узла 9 |
j |
L9-j |
U1j |
L29-j |
U29 |
9-13-12-19 |
13 |
40 |
39 |
79 |
|
9-13-14-19 |
13 |
40 |
18 |
58 |
58 |
Из узла 10 |
j |
L10-j |
U1j |
L210-j |
U210 |
10-15-14-19 |
15 |
10 |
24 |
34 |
|
10-14-19 |
14 |
|
21 |
21 |
21 |
Из узла 11 |
j |
L11-j |
U1j |
L211-j |
U211 |
11-15-14-19 |
15 |
9 |
24 |
33 |
|
11-10-14-19 |
10 |
4 |
21 |
25 |
25 |
Из узла 12 |
j |
L12-j |
U1j |
L212-j |
U212 |
12-13-14-19 |
13 |
6 |
18 |
24 |
24 |
Полученные кратчайшие маршруты из каждого узла в узел 19 и значения их длин U3j (выделены заливкой) занесем в таблицу 7.
5) Приближение k=4.
Определим длину L4i-j возможного маршрута из i-го узла в узел 19, проходящего через j-й узел, с числом промежуточных узлов не более четырех как сумму расстояния Li-j от i-го узла до j-го узла и длины U3j маршрута из j-го узла в узел 12 с числом узлов не более трех:
L4i-j = Li-j + U3j , i = 1, 2, ... 18, j = 1, 2, ... 19, j ≠ i.
В качестве длины кратчайшего маршрута из i-го узла в узел 19 принимается минимальное значение из возможных:
U4i = min {L4i-j}.
Результаты расчетов показывают, что длины кратчайших маршрутов U4i с числом промежуточных узлов не более четырех оказываются равными длинам кратчайших маршрутов U3i с числом промежуточных узлов не более трех. В связи с этим дальнейшие расчеты прекращаются.
В таблице 7 для каждого приближения приведены полученные кратчайшие маршруты в узел 19 и их длины.
Таблица 7 – Кратчайшие маршруты в узел 19
J |
k=0 |
k=1 |
K=2 |
k=3 |
k=4 | ||||||||
Маршрут |
U0j |
Маршрут |
U1j |
Маршрут |
U2j |
Маршрут |
U3j |
Маршрут |
U4j | ||||
1 |
|
|
|
|
1-10-14-19 |
37 |
1-10-14-19 |
37 |
1-10-14-19 |
37 | |||
2 |
|
|
|
|
2-10-14-19 |
30 |
2-10-14-19 |
30 |
2-10-14-19 |
30 | |||
3 |
|
|
3-12-19 |
53 |
3-12-19 |
53 |
3-11-10-14-19 |
34 |
3-11-10-14-19 |
34 | |||
4 |
|
|
4-12-19 |
44 |
4-12-19 |
44 |
4-12-13-14-19 |
35 |
4-12-13-14-19 |
35 | |||
5 |
|
|
|
|
|
|
|
|
|
| |||
6 |
|
|
|
|
|
|
|
|
|
| |||
7 |
|
|
|
|
|
|
|
|
|
| |||
8 |
|
|
|
|
8-13-14-19 |
30 |
8-13-14-19 |
30 |
8-13-14-19 |
30 | |||
9 |
|
|
|
|
9-13-14-19 |
58 |
9-13-14-19 |
58 |
9-13-14-19 |
58 | |||
10 |
|
|
10-14-19 |
21 |
10-14-19 |
21 |
10-14-19 |
21 |
10-14-19 |
21 | |||
11 |
|
|
|
|
11-10-14-19 |
25 |
11-10-14-19 |
25 |
11-10-14-19 |
25 | |||
12 |
12-19 |
33 |
12-19 |
33 |
12-13-14-19 |
24 |
12-13-14-19 |
24 |
12-13-14-19 |
24 | |||
13 |
|
|
13-14-19 |
18 |
13-14-19 |
18 |
13-14-19 |
18 |
13-14-19 |
18 | |||
14 |
14-19 |
9 |
14-19 |
9 |
14-19 |
9 |
14-19 |
9 |
14-19 |
9 | |||
15 |
|
|
15-14-19 |
24 |
15-14-19 |
24 |
15-14-19 |
24 |
15-14-19 |
24 | |||
16 |
|
|
|
|
|
|
|
|
|
| |||
17 |
|
|
|
|
|
|
|
|
|
| |||
18 |
|
|
|
|
|
|
|
|
|
|
Искомые кратчайшие маршруты в узел 19 (пункт D4)
из узла 1 (пункт А1): 1-10-14-19 (А1-Е4-Е8-D4); расстояние перевозки 37;
из узла 2 (пункт А2): 2-10-14-19 (A2-E4-E8-D4); расстояние перевозки 30;
из узла 3 (пункт А3): 3-11-10-14-19 (A3-E5-E4-E8-D4); расстояние перевозки34;
из узла 4 (пункт А4 ): 4-12-13-14-19 (A4-E6-E7-E8-D4 ); расстояние перевозки 35.