время–расширенный и время–зависимый [3, 4]. Общее свойство обо-
их подходов заключается в том, что результат вычисляется с помощью
некоторого алгоритма поиска кратчайшего пути к специально постро-
енному графу. Время–расширенный граф конструируется таким обра-
зом, что каждый узел соответствует определенному времени (прибы-
тия или отправления) на станцию, а ребра между узлами представляют
либо элементарные соединения между двумя событиями, либо время
ожидания на станции. На практике это приводит к созданиюочень
большого (хотя и разреженного) графа. Что касается время-зависимого
подхода, то идея состоит в том, чтобы избежать создания узлов графа
для каждого события. Вместо этого время-зависимый граф строит-
ся так, что каждый узел представляет станциюи два узла считаются
связанными ребром, если соответствующие станции связаны элемен-
тарным соединением. Вес ребра присваивается “на лету” и зависит
от времени, когда конкретное ребро будет использовано алгоритмом
поиска кратчайшего пути.
Задача поиска формулируется следующим образом. Расписание со-
стоит из следующих данных:
станции
(либо остановки, порты и др.),
маршруты
(поезда, автобусы, курсирующие между станциями),
вре-
мя
отправления и прибытия маршрутов на станции, и
дни
курсиро-
вания. В математических терминах это можно записать так: имеет-
ся набор маршрутов
Z
, набор станций
B
и набор элементарных со-
единений
С
, элементы которого
с
— кортеж пяти величин в форме
c
= (
Z, S
1
, S
2
, t
d
, t
a
)
. Каждое элементарное соединение понимается
как маршрут
Z
, отправляющийся со станции
S
1
во время
t
d
, следу-
ющая станция маршрута
S
2
, время прибытия на которую
t
a
. Длина
элементарного соединения
с
обозначается length(
c
). Это время между
прибытием и отправлением
с
. Расписание действует для числа
N
дней
курсирования. Каждому маршруту соответствует битовое поле из
N
битов, определяющих, в какие дни маршрут курсирует. На станции
S
∈
B
возможна пересадка с одного маршрута на другой только в
случае, если время между отправлением и прибытием на станцию
S
больше либо равно минимальному времени пересадки для этой стан-
ции (
S
). Для станций, расположенных близко друг к другу, возможно
прохождение пешком. Это можно описать введя так называемые
пе-
шие ребера
между станциями. Формально, мы рассматриваем пешее
ребро как элементарное соединение
с
, где маршрут
Z
, времена отпра-
вления и прибытия
t
d
и
t
a
не определены, но length(
c
) определено и
равно времени пешего перехода.
Пусть
P
= (
c
1
, . . . , c
k
)
— последовательность элементарных соеди-
нений (включая пешие ребра), с заданными отправлениями
dep
i
(
P
)
и прибытиями
arr
i
(
P
)
для каждого элементарного соединения
c
i
,
1
i k
. Полагаем, что время прибытия и отправления включают
100 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 4
