даты прибытия и отправления и учитывается также время, прошед-
шее с первого дня поездки. Время
t
=
a
·
1440 +
b
, где
a
∈
[0
,
364]
и
b
∈
[0
,
1439]
. Такая последовательность
P
называется
постоянным
соединением
станций
A
=
S
1
(
c
1
)
и
A
=
S
2
(
c
k
)
. Формально постоянное
соединение удовлетворяет следующим условиям:
c
i
действует 1 день
[
dep
i
(
P
)
/
1440]
,
S
2
(
c
i
) =
S
1
(
c
i
+1
)
,
dep
i
(
P
)
≡
t
d
(
c
i
)(mod 1440)
,
arr
i
(
P
) =
dep
i
(
P
) +
length
(
c
i
)
,
dep
i
+1
(
P
)
−
arr
i
(
P
)
≤
⎧⎨
⎩
0
,
если
Z
(
c
i
+1
) =
Z
(
c
i
)
или
c
i
— пешее
ребро
;
transfer
(
S
2
(
c
i
))
,
иначе
.
Наиболее известная частная задача о расписаниях называется так-
же
задачей наискорейшего прибытия.
Запрос
(
A, B, t
0
)
определяет
станциюотправления
A
, станциюприбытия
B
и время отправления
t
0
. Соединение допустимо, если отправление из пункта
А
не проис-
ходит раньше заданного времени
t
0
. Критерий оптимизации — мини-
мизировать разницу между временем прибытия и заданным временем
отправления. В другой задаче —
задаче минимального числа переса-
док
необходимо отыскать путь с наименьшим числом пересадок для
станций
А
и
B
, вообще не принимая во внимание время прибытия и
отправления.
Представленные подходы могут быть использованы для модели-
рования реальной задачи, например, учитывающей время пересадок.
Чтобы учесть время пересадки во время–расширенной модели, на гра-
фе создается копия всех узлов прибытия и отправления со станции,
которые назовем
узлами пересадки
. Для каждого узла прибытия су-
ществует два исходящих ребра: одно ребро — к отправлениютого же
маршрута, другое ребро — к узлу пересадки со временем, б ´ольшим
или равным сумме времени прибытия в узел и минимального време-
ни, требуемого для пересадки на данной станции.
Часто пассажиры бывают заинтересованы в том, чтобы найти са-
мый дешевый путь из пункта
А
в пункт
B
в заданном интервале
времени. К сожалению, тарифная система в большинстве стран на-
столько сложна, что практически невозможно решить такуюзадачу
поиска и точно и быстро. Даже в стандартных тарифах стоимость
проезда обычно неаддитивна. Еще хуже обстоит дело, если требуется
учесть специальные тарифы.
Многокритериальная оптимизация
по нескольким критериям
необходима, когда пассажиру требуется найти путь с минимальным
числом пересадок, который начинается после заданного момента вре-
мени и не заканчивается слишком поздно. Вычисление оптимального
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 4 101
