Курсовая работа: Организация процессов освоения дальних и пригородных пассажиропотоков

На разветвленном направлении допускаются разные маршруты следования пассажиров между узлами, поэтому сначала необходимо произвести распределение корреспонденций пассажиропотоков между узлами полигона, которое сводится к поиску кратчайших по времени следования путей между ними.

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

Сущность тернарной операции заключается в следующем:

d_ik = d_ij + d_jk , если d_jk > d_ij + d_ik и i¹j¹k, (2.15)

Где d_ik - длина некоторого пути, соединяющего i –й и k-й узлы;

d_ij , d_jk - длины путей, соединяющих соответственно i –й и j-й; и j-й и k-й узлы;

Расчет начинается с построения исходной матрицы Д1, в которой элемент d_jk равен длине дуги (i, k), если такая дуга принадлежит направлению G, т.е. (i, k)ÎG и d_jk = ¥ в противном случае. Одновременно строится матрица В1 с элементами (i, k), равными k.

Пересчет элементов матрицы Д1 в соответствии с тернарной операцией вызывает пересчет элементов матрицы В1 по следующему правилу:

(i, j), если d_jk > d_ij + d_ik (2.17)

(i, k) = (i, k), если d_jk £ d_ij + d_ik (2.18)

Работа алгоритма начинается с применения тернарной операции при j = 1, т.е. пересчета всех элементов матриц Д1 и В1, кроме элементов первой строки и первого столбца. Все остальные элементы матрицы Д1 остаются без изменения. В результате получаются матрицы Д2 и В2. Следующая итерация сводится к пересчету всех элементов матриц Д2 и В2, кроме элементов второго столбца и второй строки, т.е. при j = 2. Продолжая аналогичные вычисления, получают остальные матрицы.

Последняя матрица – матрица длин кратчайших путей между узлами направления. По ней можно определить последовательность узлов и построить любой из кратчайших путей между ними.

Исходные матрицы Д1 и В1:

Матрица Д1

I/k	1	2	3	4	5	6
1	0	977	¥	¥	¥	¥
2	977	0	¥	¥	¥	¥
3	¥	¥	0	¥	¥	¥
4	¥	¥	¥	0	¥	¥
5	¥	¥	¥	595	0	¥
6	¥	¥	¥	552	¥	0

Матрица В1

I/k	1	2	3	4	5	6
1	1	2	3	4	5	6
2	1	2	3	4	5	6
3	1	2	3	4	5	6
4	1	2	3	4	5	6
5	1	2	3	4	5	6
6	1	2	3	4	5	6

Матрица Д2

I/k	1	2	3	4	5	6
1	0	977	¥	¥	¥	¥
2	977	0	2125	935	¥	¥
3	¥	2125	0	1147	¥	¥
4	¥	935	1147	0	595	552
5	¥	¥	¥	595	0	¥
6	¥	¥	¥	552	¥	0

Матрица В2

I/k	1	2	3	4	5	6
1	1	2	3	4	5	6
2	1	2	3	4	5	6
3	1	2	3	4	5	6
4	1	2	3	4	5	6
5	1	2	3	4	5	6
6	1	2	3	4	5	6

Матрица Д3

I/k	1	2	3	4	5	6
1	0	977	3102	1912	¥	¥
2	977	0	2125	935	¥	¥
3	3102	2125	0	1147	¥	¥
4	1912	935	3060	0	595	552
5	¥	¥	¥	595	0	¥
6	¥	¥	¥	552	¥	0

Матрица В3

I/k	1	2	3	4	5	6
1	1	2	2	2	5	6
2	1	2	3	4	5	6
3	2	2	3	4	5	6
4	2	2	2	4	5	6
5	1	2	3	4	5	6
6	1	2	3	4	5	6

Матрица Д4

I/k	1	2	3	4	5	6
1	0	977	3102	1912	¥	¥
2	977	0	2125	935	¥	¥
3	3102	2125	0	1147	¥	¥
4	1912	935	3060	0	595	552
5	¥	¥	¥	595	0	¥
6	¥	¥	¥	552	¥	0

Матрица В4

I/k	1	2	3	4	5	6
1	1	2	2	2	5	6
2	1	2	3	4	5	6
3	2	2	3	4	5	6
4	2	2	2	4	5	6
5	1	1	3	4	5	6
6	1	2	3	4	5	6

Матрица Д5

I/k	1	2	3	4	5	6
1	0	977	3102	1912	2507	2464
2	977	0	2125	935	1530	1487
3	3059	2082	0	1147	1742	1699
4	1912	935	3060	0	595	552
5	2507	1530	3655	595	0	1147
6	2464	1487	3612	552	1147	0

Матрица В5

I/k	1	2	3	4	5	6
1	1	2	2	2	4	4
2	1	2	3	4	4	4
3	4	4	3	4	4	4
4	2	2	2	4	5	6
5	4	4	4	4	5	4
6	4	4	4	4	4	6

Матрица Д6

I/k	1	2	3	4	5	6
1	0	977	3102	1912	2507	2464
2	977	0	2125	935	1530	1487
3	3059	2082	0	1147	1742	1699
4	1912	935	3060	0	595	552
5	2507	1530	3655	595	0	1147
6	2464	1487	3612	552	1147	0

Матрица В6

I/k	1	2	3	4	5	6
1	1	2	2	2	4	4
2	1	2	3	4	4	4
3	4	4	3	4	4	4
4	2	2	2	4	5	6
5	4	4	4	4	5	4
6	4	4	4	4	4	6

Матрица Д7

I/k	1	2	3	4	5	6
1	0	977	3102	1912	2507	2464
2	977	0	2125	935	1530	1487
3	3059	2082	0	1147	1742	1699
4	1912	935	3060	0	595	552
5	2507	1530	3655	595	0	1147
6	2464	1487	3612	552	1147	0

Матрица В7

I/k	1	2	3	4	5	6
1	1	2	2	2	4	4
2	1	2	3	4	4	4
3	4	4	3	4	4	4
4	2	2	2	4	5	6
5	4	4	4	4	5	4
6	4	4	4	4	4	6

Матрица Д7 – матрица кратчайших путей между станциями полигона. По вспомогательной матрице В7 можно построить любую из кратчайших цепей между станциями полигона.

На рисунке 2.3 представлены маршруты следования пассажиропотоков по кратчайшим расстояниям, а также расчет густоты пассажиропотока для каждого участка расчетного полигона.