Курсовая работа Миронович1. Задача организации перевозок Составление моделей транспортной сети Алгоритм расчета кротчайших расстояний Выбор подвижного состава Сравнительная оценка подвижного

Название	Задача организации перевозок Составление моделей транспортной сети Алгоритм расчета кротчайших расстояний Выбор подвижного состава Сравнительная оценка подвижного
Дата	27.04.2021
Размер	1.36 Mb.
Формат файла
Имя файла	Курсовая работа Миронович1.doc
Тип	Задача #199100
страница	2 из 6

1 2 3 4 5 6

3.1 Алгоритм расчета кротчайших расстояний
Как известно, во всех нетривиальных случаях задача выбора кратчайшего пути между вершинами транспортной сети является многовариантной. ее решение путем перебора и сравнения всех возможных маршрутов движения между заданными пунктами неэффективно.

Для определения кратчайших расстояний в настоящее время применяют математические методы. Мы определяем кратчайшие расстояния самым распространенным методом, который называется метод "метлы".

Для расчета кратчайших расстояний необходимы исходные данные: модель транспортной сети, на которой указаны номера вершин длины звеньев; номер вершины, из которой начинается движение (будем называть ее вершиной "от"); номер вершины, до которой (назовем ее вершиной "до") нужно определить кратчайший путь. Рассчитывая последовательно каждый шаг, заполняем специальную таблицу (таблица 3.1).
Таблица 3.1 – Специальная таблица к алгоритму расчета кратчайших расстояний

Номер вершины	Расстояние, км	Условные знак проверки	Номер предыдущей вершины
1	12	1	-
2	12	1	1

Алгоритм состоит из следующих шагов.

Шаг 1. Его можно назвать подготовительным. В первую колонку таблицы 3.1 заносим номер вершины, во вторую - в сторону вершины "от ставим "0" - ноль, во все другие строки запишем заведомо большое число М. В третьей колонке в строке вершины "от" ставим "1" - единицу, т.е. условный знак проверки (см. таблицу 3.2).
Таблица 3.2 - Результат первого шага расчета кратчайших расстояний

Номер вершины	Расстояние, км	Условные знак проверки	Номер предыдущей вершины
1	М	1	2
2	0	0	-
3	М	1	1
…	М	1	…
…	М	1	…
58	М	1	23
59	М	1	24
60	М	1	25

Шаг 2. Выбираем любую строку, где имеется условный знак проверки. Если такой строки нет, переходим к шагу 3. В противном случае (строка с условным знаком проверки есть) выполняем такие операции:

зачеркиваем условный знак проверки;

перебираем все связи вершины с условным знаком проверки с другими вершинами.

Для каждых из таких вершин рассчитываем вариант расстояния от вершины "от" по формуле:
l_k_,_j=l_k_,_I+l_i_,_j , (3.1)
где l_k_,_j;l_k_,_I- расстояния от вершины "от" до j-й, i-й вершины

соответственно

l_j_,_i - расстояние от i-й до j-й вершины.
После этого полученное расстояние l_k_,_j сравниваем с имеющимся в строке j-й вершины (обозначим его l^*_k_,_j).

В противном случае зачеркиваем в строке с вершиной j значение l^*_k_,_j, заносим в эту строку расстояние l_k_,_j, в третьею колонку записываем условный знак проверки, в четвертую колонку - номер предыдущей вершины (см. таблицу 3.3).

Если l_k_,_j≥l^*_k_,_j , то в таблицу 3.1 ничего не записываем.
Шаг 3. Расчет закончен. Во второй колонке таблице 3.1 в каждой строке не зачеркнутая цифра будет являться кратчайшим расстоянием от вершины "от" до вершины, записанной в первой колонке (см. таблицу 3.4).

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

М=500 (Ц₁+Ц₂),

где Ц₁, Ц₂ - последняя и предпоследняя цифры номера зачетной книжки соответственно. Таким образом, каждому сантиметру на рисунке будет соответствовать М метров реальной дорожной сети. Получаем:

М=500 (3+2)=2500 м

Таблица 3.3 - Таблица кратчайших расстояний

№ вершины	Расстояние между вершинами км.	Условный знак проверки	№ предыдущей вершины
1	27,5	1	2
2	26	1	8
3	26,5	1	10
4	28	1	3
5	19,5	1	14
6	19,5	1	15
7	15,75	1	16
8 (Г₁)	22	1	9
9	21	1	18
10	24	1	9
11(Г₂)	26,25	1	10
12	27,27	1	11
13	15,25	1	21
14	17	1	13
15	17	1	16
16(Г₂₀)	13,25	1	22
17(Г₄)	20,5	1	36
18	18,75	1	23
19(Г₃)	22,25	1	18
20	25	1	19
21	11	1	32
22	10,75	1	35
23	17	1	37
24	16	1	28
25(Г₅)	15	1	29
26	15,25	1	27
27	13,25	1	31
28	14,25	1	38
29	12,5	1	39
30(Г₇)	11	1	31
31	10,5	1	32
32(Г₂₁)	9	1	33
33	4,75	1	49
34(Г₁₉)	7,25	1	33
35	9	1	52
36	16	1	42
37	13,5	1	38
38	12	1	39

Окончание таблицы 3.3

№ вершины	Расстояние между вершинами км.	Условный знак проверки	№ предыдущей вершины
39	10,25	1	40
40	8,5	1	41
41	6,5	1	47
42	14,25	1	43
43(Г₆)	12	1	44
44	11,5	1	45
45	10,75	1	46
46(Г₉)	9,5	1	47
47(Г₁₁)	4,25	1	48
48	2,25	1	49
49(Г₁₅)	0		-
50	2,25	1	49
51	3,25	1	50
52(Г₁₈)	5,25	1	51
53	10,25	1	54
54	8,5	1	55
55(Г₁₂)	6	1	56
56	4	1	48
57(Г₈)	15,25	1	58
58(Г₁₀)	12,75	1	59
59	11,25	1	60
60	9,5	1	61
61	7,25	1	62
62	5,25	1	56
63(Г₁₄)	3,25	1	49
64(Г₁₇)	5,25	1	63
65	7,5	1	64
66	16,25	1	67
67	14,25	1	68
68	12,75	1	69
69(Г₁₃)	11	1	70
70	8,5	1	71
71	6,75	1	72
72	5	1	63
73(Г₁₆)	7,5	1	72
74	9,75	1	73
75	11,25	1	74

Таблица 3.4 - Соответствие точек графа нумерации грузовых пунктов

№ Вершины	8	11	19	43	30	58	47	49	73	64	52	34	16	32
№ Пункта	Г₁	Г₂	Г₃	Г₆	Г₇	Г₁₀	Г₁₁	Г₁₅	Г₁₆	Г₁₇	Г₁₈	Г₁₉	Г₂₀	Г₂₁

Таблица 3.5 - Матрица кратчайших расстояний без учета знаков, установленных на дорожной сети

	Г₁	Г₂	Г₃	Г₆	Г₇	Г₁₀	Г₁₁	Г₁₅	Г₁₆	Г₁₇	Г₁₈	Г₁₉	Г₂₀	Г₂₁
Г₁	0	6,25	6,75	10,75	13,25	14	15,5	19,75	26,25	24,25	25	22	28,25	15,25
Г₂	6,25	0	5,25	15	17,5	18,5	19,75	24	30,5	28,5	29,25	26,25	32,5	19,5
Г₃	6,75	5,25	0	11	13,5	14,5	15,75	20	26,5	24,5	25,25	22,25	28,5	15,5
Г₆	10,75	15	11	0	9,25	3,5	4,75	9	15,5	13,5	14,25	16,25	22,25	9,5
Г₇	13,25	17,5	13,5	9,25	0	11,75	6,75	11	17,5	15,5	14,75	8,75	15	2
Г₁₀	14	18,5	14,5	3,5	11,75	0	6,75	11	13,25	11,25	16,25	18,25	24,25	11,5
Г₁₁	15,5	19,75	15,75	4,75	6,75	6,75	0	4,25	10,75	8,75	9,5	11,5	17,5	4,75
Г₁₅	19,75	24	20	9	11	11	4,25	0	7,5	5,25	5,25	7,25	13,25	9
Г₁₆	26,25	30,5	26,5	15,5	17,5	13,25	10,75	7,5	0	6,25	12,75	14,75	20,75	15,5
Г₁₇	24,25	28,5	24,5	13,5	15,5	11,25	8,75	5,25	6,25	0	6,75	8,75	14,75	13,5
Г₁₈	25	29,25	25,25	14,25	14,75	16,25	9,5	5,25	12,75	6,75	0	6	8	12,75
Г₁₉	22	26,25	22,25	16,25	8,75	18,25	11,5	7,25	14,75	8,75	6	0	6,5	6,75
Г₂₀	28,25	32,5	28,5	22,25	15	24,25	17,5	13,25	20,75	14,75	8	6,5	0	13
Г₂₁	15,25	19,5	15,5	9,5	2	11,5	4,75	9	15,5	13,5	12,75	6,75	13	0

Таблица 3.6 - Матрица кратчайших расстояний с учетом знаков, установленных на дорожной сети

	Г₁	Г₂	Г₃	Г₆	Г₇	Г₁₀	Г₁₁	Г₁₅	Г₁₆	Г₁₇	Г₁₈	Г₁₉	Г₂₀	Г₂₁
Г₁	0	6,25	6,75	11,25	17,5	14	16	20,25	27	24,75	31,75	26,25	32,75	19,5
Г₂	6,25	0	5,75	17,5	23,75	20,25	22,25	26,5	33,25	31	38	32,5	39	25,75
Г₃	6,75	5,75	0	18	24,25	20,75	22,75	27	33,75	31,5	38,5	33	39,5	26,25
Г₆	11,25	17,5	18	0	11,5	7	4,75	9	15,75	13,5	20,5	16,25	22,75	9,5
Г₇	17,5	23,75	24,25	11,5	0	13,5	6,75	11	17,75	15,5	14,75	8,75	15,25	2
Г₁₀	14	20,25	20,75	7	13,5	0	6,75	11	13,5	11,25	18,25	18,25	24,75	11,5
Г₁₁	16	22,25	22,75	4,75	6,75	6,75	0	4,25	11	8,75	15,75	11,5	18	4,75
Г₁₅	20,25	26,5	27	9	11	11	4,25	0	7,5	5,25	12,25	7,25	13,75	9
Г₁₆	27	33,25	33,75	15,75	17,75	13,5	11	7,5	0	6,25	12,75	14,75	20,75	15,5
Г₁₇	24,75	31	31,5	13,5	15,5	11,25	8,75	5,25	6,25	0	7	12,5	15	13,5
Г₁₈	31,75	38	38,5	20,5	14,75	18,25	15,75	12,25	12,75	7	0	6	8	12,75
Г₁₉	26,25	32,5	33	16,25	8,75	18,25	11,5	7,25	14,75	12,5	6	0	6,5	6,75
Г₂₀	32,75	39	39,5	22,75	15,25	24,75	18	13,75	20,75	15	8	6,5	0	15
Г₂₁	19,5	25,75	26,25	9,5	2	11,5	4,75	9	15,5	13,5	12,75	6,75	15	0

1 2 3 4 5 6