Пункты отправления – пункты назначения (первый вид транспорта)

Как следует из исходных данных, каждый пункт назначения связан с каждым пунктом отправления единственным прямым маршрутом. Следовательно, время следования транспорта между этими пунктами совпадают со значениями, приведенными в матрице времён следования между пунктами (таблица 5.1 в приложении).

Пункты взаимодействия – пункты назначения (второй вид транспорта)

Как следует из исходных данных, каждый пункт назначения связан с каждым пунктом взаимодействия единственным прямым маршрутом. Следовательно, время следования транспорта между этими пунктами совпадают со значениями, приведенными в матрице времён следования между пунктами (таблица 5.2 в приложении).

Пункты отправления - пункты взаимодействия (первый вид транспорта)

Из матрицы времён следования транспорта видно, что существуют прямые маршруты между пунктами Ak (k=1 5) отправления и пунктами Di (i=1 3) взаимодействия (таблица 5.3 в приложении). Эти маршруты также учитываются при выборе расстояний с наименьшим временем следования между пунктами отправления Ak (k=1 5) и пунктами взаимодействия Di (i=1 3).

Необходимо определить, является ли время следования на прямых маршрутах оптимальным, построить маршруты с наименьшим временем следования, пролегающие через промежуточные пункты Es (s=1 9), и определить время движения по этим маршрутам.

Сформируем матрицу времён следования между пунктами Ak отправления, промежуточными пунктами Es, пунктами Di взаимодействия; введем сквозную нумерацию узлов (таблица 5.4 в приложении).

Пункт D3

Построим маршруты в узел 17 (пункт D3) из узлов 1 (пункт А1), 2 (пункт А2), 3 (пункт А3), 4 (пункт А4), 5 (пункт А5).

Приближение k = 0.

Определим время движения по прямым (без посещения промежуточных узлов) маршрутам в узел 17. Для каждого j-го узла (j=5, 11, 13), который связан дугой с узлом 17 (т.е. имеется прямой маршрут), время следования по маршруту с наименьшим временем следования принимается равным времени следования между этим узлом и узлом 17; для остальных узлов значения принимаются равными бесконечности:

;

;

.

Полученные маршруты и значения времени следования между ними занесем в таблицу 5.8.

Приближение k = 1.

Определим время движения по возможному маршруту из i-го узла в узел 17, проходящий через j-й узел, с числом промежуточных узлов не более одного как сумму времён от i-го узла до j-го узла и времени следования по прямому маршруту из этого узла в узел 17:

, i=1,2, …16, j=1,2, …16, .

В качестве наименьшего времени следования из i-го узла в узел 17 принимается минимальное из возможных значений:

.

Полученные маршруты с наименьшим временем следования из каждого узла в узел 17 и значения времён занесем в таблицу 5.8 (приложение).