Автоматика и телемеханика, № 5, 2020

(Технологический университет, Сидней, Австралия),

А.А. ЛАЗАРЕВ, д-р физ.-мат. наук (jobmath@mail.ru)

(Институт проблем управления им. В.А. Трапезникова РАН, Москва;

Национальный исследовательский университет

“Высшая школа экономики”, Москва),

Е.Г. МУСАТОВА, канд. физ.-мат. наук (nekolyap@mail.ru)

(Институт проблем управления им. В.А. Трапезникова РАН, Москва)

КОРРЕКТИРОВКА РАСПИСАНИЯ ДВИЖЕНИЯ

НА ЧАСТИЧНО ЗАБЛОКИРОВАННОМ СЕГМЕНТЕ

ЖЕЛЕЗНОЙ ДОРОГИ С РАЗЪЕЗДОМ¹

Представлен полиномиальный алгоритм корректировки расписания

движения поездов для случая, когда один из путей двухпутной желез-

ной дороги становится недоступным, оставшийся путь содержит разъ-

езд, а все поезда делятся на две категории: приоритетные поезда, напри-

мер пассажирские, и обычные поезда, к которым относятся большинство

грузовых поездов. Представленный алгоритм минимизирует негативное

влияние, оказываемое блокировкой пути, сначала для приоритетных по-

ездов, а затем для обычных поездов на множестве всех расписаний, оп-

тимальных для приоритетных поездов.

Ключевые слова: однопутная железная дорога, динамическое программи-

рование, перепланирование, полиномиальный алгоритм.

DOI: 10.31857/S0005231020050062

1. Введение

Сбои, такие как аварии или повреждение пути, часто приводят к вре-

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

В таких ситуациях необходимо планировать движение поездов в обоих на-

правлениях на оставшемся пути с целью минимизации влияния блокировки.

Корректировка железнодорожных расписаний является областью активных

исследований в течение нескольких десятилетий [1]. В статье добавляется

к этим исследованиям полиномиальный алгоритм на основе динамического

программирования для случая, когда оставшаяся колея имеет разъезд, а мно-

жество всех поездов разделено на две категории: приоритетные поезда, такие

как пассажирские, и обычные, такие как большинство грузовых поездов.

Более подробно рассмотрим двухпутную железную дорогу между двумя

точками A и B, где один железнодорожный путь заблокирован и движение

¹ Работа выполнена при частичной финансовой поддержке Российского научного фонда

(проект №17-19-01665).

всех поездов должно быть перепланировано на оставшемся пути. Оставшийся

путь имеет разъезд, т.е. участок, позволяющий поезду разминуться со встреч-

ным поездом. В этом случае пропускающий поезд должен стоять в разъезде,

в то время как проходящий поезд не может остановиться в разъезде. В разъ-

езде одновременно может сделать остановку только один поезд. Все поезда

имеют одинаковую постоянную скорость. Время, которое требуется поезду

для прохождения отрезка дороги между точкой s ∈ {A, B} и разъездом, обо-

значим через p_s. Не ограничивая общности, будем полагать, что p_A ≥ p_B.

По соображениям безопасности два поезда не могут прибыть в разъезд

одновременно. Пусть β минимальный временной промежуток между дву-

мя такими прибытиями. По той же причине для каждой конечной точки

рассматриваемого отрезка пути два момента прибытия, два момента отправ-

ления, так же как и момент прибытия и момент отправления двух поездов,

должны отличаться как минимум на величину β. При этом два поезда могут

покинуть разъезд одновременно, если они движутся в разных направлени-

ях. Предположение, что все эти требования безопасности имеют одинаковое

минимальное время β, упрощает изложение материала, но не является суще-

ственным. Также будем полагать, что β < p_B.

Множество поездов состоит из двух категорий: приоритетные поезда и

обычные поезда. Для каждого s ∈ {A, B} пусть s = {A, B} \ {s}. Обозначим

через

s и

множества приоритетных и обычных поездов, которые долж-

ны проходить путь в направлении от точки s к точке s. Будем считать, что

для каждого s ∈ {A, B}

s ∪

= ∅, поскольку в противном случае задача

корректировки расписания не возникает.

Исходное расписание, построенное в предположении, что оба пути нахо-

дятся в рабочем состоянии, выделяет каждому поезду j ∈ N^αs временное окно

[r^s,αj, d^s,αj], в пределах которого поезд j должен пройти через рассматривае-

мый двухпутный участок железнодорожной сети. В соответствии с этим ис-

ходным расписанием один путь выделяется для всех поездов, приоритетных и

обычных, идущих из А в В, а другой путь выделяется для всех поездов, при-

оритетных и обычных, движущихся в противоположном направлении, из В

в А. Следовательно, для любых двух поездов j ∈ N^αs и j^′ ∈ Nα′s, движущихся

из s в s, соответствующие временные окна удовлетворяют условию

(1)

r^s,αj = rs′α′j

и r^s,αj > rs′α′jвлечетdj,α > dj′α′.

В результате корректировки расписания для каждого поезда j ∈ N^αs опре-

деляется момент времени S^s,αj, в который этот поезд должен войти на остав-

шийся путь и который будем называть моментом отправления поезда из точ-

ки s, и момент времени C^s,αj, в который поезд должен покинуть рассматри-

ваемый путь и который будем называть временем прибытия в точку s. Любое

такое новое расписание должно удовлетворять следующему условию, которое

диктует наличие исходных временных окон:

(s1) для любого s ∈ {A, B}, любого α ∈ {p, o} и любого поезда j ∈ N^αs вре-

мя отправления S^s,αj этого поезда удовлетворяет неравенству S^s,αj ≥

≥r^s,αj.

Требуется построить расписание, минимизирующее целевую функцию

(2)

max max

[C^s,pj - d^s,pj]

s∈{A,B} j∈N^s

и которое минимизирует целевую функцию

∑ ∑

(3)

[C^s,oj - r^s,oj]

s∈{A,B} j∈

на множестве всех расписаний, оптимальных для (2).

Целевая функция (3) является лишь одним из возможных показателей

влияния блокировки одного из путей на обычные поезда. Так, приведенная

далее оптимизационная процедура может быть легко модифицирована для

случая, когда вместо (3) используется

(4)

max

max[C^s,oj - d^s,oj

s∈{A,B}

j∈N^os

Существует множество публикаций по планированию и корректировке

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

[1, 2]). Среди них публикации [3-5] наиболее тесно связаны с данной статьей.

Как и настоящая статья, [3] касается корректировки расписания в случае,

когда первоначальное расписание полностью функционирующего двухпутно-

го участка железнодорожной сети определяет временное окно для каждого

поезда и рассматривает несколько категорий поездов. В отличие от данной

статьи [3] предполагает отсутствие разъезда и отражает существование раз-

личных типов поездов путем введения весов в целевую функцию.

Другой близкой публикацией является [5], которая касается оптимизации

упорядоченных целевых функций, но в отличие от данной статьи предполага-

ет, что все поезда доступны одновременно (такая ситуация может возникнуть

после полной блокировки рассматриваемого участка железной дороги). Кро-

ме того, [5] предполагает, что на оставшемся пути нет разъезда.

И, наконец, [4] касается планирования на однопутной железной дороге,

которая имеет разъезд, но аналогично [5] подразумевает, что все поезда име-

ются в наличии одновременно. Кроме того, в отличие от приведенной далее

процедуры оптимизации, которая предназначена для двух категорий поездов

и упорядоченных целевых функций, все алгоритмы, представленные в [4], бы-

ли разработаны для случаев одной целевой функции и подразумевают, что

все поезда имеют одинаковый тип. Несмотря на упомянутые существенные

различия между [4] и данной статьей, некоторые результаты относительно

структуры оптимальных расписаний, полученные в [4], могут быть непосред-

ственно обобщены на случай, когда исходное расписание задает временное

окно для каждого поезда. Кроме того, основная идея из [4], что существует

вложенный Беллмановский процесс принятия решений, связанный с момен-

тами отправления определенных поездов, остается в силе для данной статьи,

хотя набор состояний и реализация общей схемы динамического программи-

рования различны.

2. Экспрессы и неэкспрессы

Рассмотрим произвольное расписание для пути, который остался доступ-

ным после блокировки. Как и в [4], поезд, который не останавливается в

разъезде, будет называться экспрессом, тогда как поезд, который делает оста-

новку в разъезде, будет называться неэкспрессом. Понятия экспресса и неэкс-

пресса не связаны с понятиями приоритетных и обычных поездов. Другими

словами, любой приоритетный поезд, так же как и любой обычный поезд, мо-

жет быть как экспрессом, так и неэкспрессом в зависимости от расписания.

Множество всех экспрессов, которым уступает путь один и тот же неэкспресс,

будем называть пакетом. Для любого момента времени t поезд j ∈ N^αs будет

называться активным в t, если

S^s,αj ≤ t ≤ C^s,αj.

Если поезда j ∈ N^αs и j^′ ∈ Nα′s, т.е. два поезда, движущиеся в противопо-

ложных направлениях, одновременно активны в некоторый момент времени,

′

]. Сле-

довательно, один из этих двух поездов должен быть экспрессом, а другой

неэкспрессом, который пропускает этот экспресс в разъезде.

Поскольку в любой момент времени в разъезде может стоять не более

одного поезда, если поезд j ∈ N^αs обгоняет поезд j^′, который движется по

пути в том же направлении, что и j, т.е. из s в s, то во временном интер-

вале [S^s,αj, C^s,αj] нет активных поездов, движущихся из s в s. Следовательно,

вместо ожидания j поезд j^′ может покинуть разъезд по крайней мере в мо-

мент времени S^s,αj + p_s - β, что может только улучшить значение целевой

функции, поскольку она неубывающая.

Поскольку обе целевые функции (2) и (3) являются неубывающими, при-

веденные выше рассуждения означают, что без ограничения общности доста-

точно рассмотреть только расписания, которые в дополнение к (s1) удовле-

творяют следующим условиям:

(s2) для каждого s ∈ {A, B} и каждого α ∈ {p, o}, для любых двух поездов

j ∈ N^αs и j^′ ∈ N^αs неравенство r^s,αj > rs,αj′ влечет S^s,αj > Ss,αj′;

(s3) для любого неэкспресса существует как минимум один экспресс, кото-

рый данный неэкспресс пропускает;

(s4) все экспрессы, которые пропускает один и тот же неэкспресс, движутся

в направлении, противоположном направлению движения этого неэкс-

пресса;

(s5) неэкспресс покидает разъезд одновременно с последним экспрессом,

который он пропускает.

Два экспресса, движущиеся в противоположных направлениях, не могут

быть активными одновременно. Более того, два экспресса, движущиеся в од-

ном направлении, скажем, из s в s, могут отправиться из s только в моменты

времени, различающиеся не менее чем на β. Следовательно, все моменты

отправления экспрессов различны.

Минимально возможная разница между двумя последовательными време-

нами отправления экспрессов определяется несколькими факторами. Если,

как и в [4], все поезда имеются в наличии одновременно, то этими фактора-

ми являются направления, в которых движутся экспрессы по рассматривае-

мому участку, и ситуации в разъезде, когда эти экспрессы его проходят. Все

возможные комбинации этих факторов определены в [4] путем приписывания

каждому экспрессу пары (s, b), называемой его типом. Здесь s указывает, что

экспресс движется в направлении из s в s, тогда как b отражает ситуацию в

разъезде и принимает следующие значения:

• 0, если экспресс проходит через пустой разъезд;

• 1, если экспресс является частью пакета и не является последним в этом

пакете;

• 2, если экспресс является последним в пакете.

Пусть i ∈ N^αs и i^′ ∈ Nα′s′^{двапоследовательныхэкспрессатипов(s,b)и}

(s^′, b^′) соответственно. Пусть время отправления экспресса i равно t. Пред-

положим, что b = 1, b^′ = 0 и некоторый неэкспресс g^′ ∈ N^γ¯

пропускает i^′. Со-

s^′

гласно [4] время отправления экспресса i определяет минимально возможное

время отправления неэкспресса g^′:



t + p_A + p_B + β, если s = s^′;





t+β,

если s = s^′, b = 0;

(5)

τ=



 t + 2p_s + β,

если s = s^′, b = 2.

Действительно, если s = s^′, то g^′ движется из s в s. В силу того что b = 1, по-

езда g^′ и i не могут быть активными одновременно. Следовательно, g^′ может

отправиться из s только через β после прибытия поезда i, который прибыва-

ет в s в момент t + p_A + p_B. Если s = s^′, то оба поезда, i и g^′, движутся из s

в s. Тогда если b = 0, то времена отправления поездов g^′ и i могут отличаться

только на β, в то время как при b = 2 поезд g^′ может покинуть точку s только

через β после прибытия в точку s поезда, который пропускает i в разъезде.

Поезд g^′ покидает разъезд одновременно с i, т.е. в момент времени t + p_s, и

после этого ему требуется p_s временных единиц, чтобы достичь s.

В отличие от [4], где предполагается, что все поезда одновременно нахо-

дятся в соответствующих конечных точках пути, данная статья посвящена

задаче корректировки расписания, которая учитывает временные окна, опре-

деленные для каждого поезда исходным расписанием. Таким образом, суще-

ствует еще одно ограничение на самое раннее возможное время отправления,

наложенное исходным временным окном поезда. Следовательно, самое ран-

нее возможное время отправления поезда g^′ из соответствующей конечной

точки рассматриваемого участка пути равно

{

}

s^′,γ

(6)

τ = max

τ, r

g^′

Если временное окно для поезда i^′ не учитывать, то согласно [4] времена

отправлений t и τ (если поезд g^′ существует) определяют следующее самое

раннее возможное время отправления поезда i^′:



t+β,

если s = s^′ и b = 1;



t+β,

если s = s^′ и b = b^′ = 0;



max{t + 2ps + β, τ +

+ β - p_s′},

если s = s^′, b = 2, b^′ = 0;

s^′

(7)

t + 2p_s + β,

если s = s^′, b = 2, b^′ = 0;



τ+

+ β - p_s′,

если s = s^′, b = 0, b^′ = 0;



s^′



t+pA +pB +β,

если s = s^′, b^′ = 0;



max{t + p_A + p_B + β, τ +

+ β - p_s′}, если s = s^′, b^′ = 0.

s^′

Принимая во внимание ограничение, накладываемое временным окном для

поезда i^′, его самое раннее возможное время отправления равно

{

}

(8)

max

′

Пусть экспресс i типа (s, b) имеет самое раннее время отправления среди

всех экспрессов. Пусть g поезд, который отправляется раньше i. Тогда g

является неэкспрессом. Это в силу условий (s3) и (s4) означает, что g от-

правляется из s и пропускает i в разъезде. Следовательно, i первый поезд,

отправляющийся из s. Кроме того, поскольку только один неэкспресс может

пропускать экспресс в разъезде, g первый поезд, отправляющийся из s.

Для каждого s ∈ {A, B} и для каждого α ∈ {p, o} определим n^αs как мощ-

ность множества N^αs и пронумеруем все поезда j ∈ N^αs в порядке убыва-

ния r^s,αj или, что эквивалентно, в порядке убывания d^s,αj. Пусть первый экс-

пресс в последовательности экспрессов имеет тип (s, b) и является поездом

категории α, который разъезжается с неэкспрессом категории γ (если такой

существует). Тогда, принимая во внимание условие (s2), время отправления

этого первого экспресса равно



 rnα,

если b = 0;

(9)

{

}

maxrs,α

+p_s+β-p_s

, если b = 0.

n^αs ,rnγ

Используя те же рассуждения, что и выше, легко видеть, что если экс-

пресс i типа (s, b) имеет самое позднее время отправления среди всех экс-

прессов и g поезд, который отправляется позже i, то i последний поезд,

отправляющийся из s, g последний поезд, отправляющийся из s, и g про-

пускает поезд i в разъезде.

Пусть i и i^′ два последовательных экспресса типов (s, b) и (s^′, b^′), соот-

ветственно, таких, что время отправления i^′ больше времени отправления i.

Как было показано выше, типы этих экспрессов вместе со временем отправле-

ния i полностью определяют самое раннее возможное время отправления i^′.

Кроме того, если некоторый неэкспресс g пропускает i и b = 2, то тип (s, b) и

время отправления i полностью определяют время, когда g прибывает в s; и

если некоторый неэкспресс g^′ пропускает i^′ и b = 1, то время отправления i

и типы этих двух экспрессов полностью определяют самое раннее время от-

правления g^′ и

s^′. Более того, как было показано выше, тип первого экспрес-

са полностью определяет самое раннее время отправления этого экспресса и

самое раннее время отправления поезда, с которым этот экспресс расходится

в разъезде, если такой поезд существует. Эти наблюдения позволяют постро-

ить искомое расписание, учитывая только времена отправления экспрессов

и назначая каждому поезду самое раннее возможное время отправления из

соответствующей точки пути.

3. Минимизация максимального временного смещения

В данном разделе показано, как найти оптимальное значение целевой

функции (2). Целевая функция (2) включает в себя только одну категорию

поездов, и, следовательно, эта оптимизационная задача сходна с задачей, рас-

смотренной в [4], с одним существенным отличием рассматриваемая здесь

задача корректировки расписания учитывает временные окна, назначенные

поездам до возникновения блокировки. Это требует включения времени в

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

туры динамического программирования для решения задачи минимизации

максимального временного смещения.

Рассмотрим произвольное расписание (напомним, что данный раздел ка-

сается только приоритетных поездов, а существование всех обычных поездов

игнорируется) и произвольный экспресс в этом расписании. Пусть (s, b)

тип этого экспресса и t время его отправления. Количество приоритетных

поездов, которые отправляются из s в s в момент времени t или после этого

момента, будем обозначать через k_s. Пусть k_s количество приоритетных

поездов, каждый из которых является либо поездом, который пропускает

рассматриваемый экспресс в разъезде, либо поездом, который отправляется

из s в s в момент времени t или позже, либо поездом, для которого выпол-

нены оба условия. Отправлению рассматриваемого экспресса соответствует

набор (t, k_A, k_B , s, b). Согласно терминологии динамического программирова-

ния этот набор будет называться состоянием. Легко видеть, что если отправ-

лению экспресса соответствует состояние (t, k_A, k_B, s, b), то данный экспресс

принадлежит множеству

s и в силу (s2) и введенной нумерации поездов

имеет номер k_s.

Состояние (t, k_A, k_B, s, b) позволяет вычислить

C^s,pk

-d^s,pk

=t+p_A +p_B -d^s,pk

и в случае b = 2

C^s,pk

-d^s,pk

= t + 2p_s - d^s,p._k

Введем обозначение

{

}

s,p

max

t+p_A +p_B -d

,t + 2p_s - d^s,p

, если b = 2;

L(t, k_A, k_B, s, b) =

t+p_A +p_B -d^s,p

иначе.

Каждое расписание индуцирует последовательность состояний, в кото-

рой состояния перечислены в порядке возрастания соответствующего вре-

мени отправления. Рассмотрим все расписания, в которых последовательно-

сти состояний содержат (t, k_A, k_B, s, b). Пусть F (t, k_A, k_B, s, b) минимальное

значение величины

max

[C^s,pj - d^s,pj]

s∈{A,B}

j∈{1,...,ks}

на множестве всех таких расписаний. Обозначим через Ω(t, k_A, k_B , s, b)

множество всех состояний, таких что каждое из них следует сразу за

(t, k_A, k_B, s, b) по крайней мере в одной из упомянутых выше последователь-

ностей.

Согласно разделу 2 последний экспресс также является последним поез-

дом, проходящим железнодорожный путь в соответствующем направлении.

Более того, после отправления этого экспресса максимум один поезд может

двигаться в противоположном направлении, и этот поезд должен пропускать

данный экспресс. Следовательно, если состояние (t, k_A, k_B, s, b) соответствует

отправлению последнего экспресса, то k_x в (t, k_A, k_B , s, b) равен



1 для x = s;

(10)

k_x =

для x = s и b = 2;



для x = s и b = 2.

Это означает, что

(11)

F (t, k_A, k_B , s, b) = L(t, k_A, k_B

,s,b).

Если в некотором расписании, у которого последовательность состояний

содержит (t, k_A, k_B, s, b), экспресс k_s ∈

s не является последним экспрессом

в расписании, то он не является последним экспрессом во всех расписаниях,

чьи последовательности состояний содержат (t, k_A, k_B , s, b). Поэтому

F (t, k_A, k_B , s, b) =

{

}

(12)

= max L(t,k_A,k_B,s,b),

min

F (t^′,kA,kB, s^′, b^′)

(t^′ ,kA,kB,s^′,b^′)∈Ω(t,k_A,k_B,s,b)

Как уже отмечалось в разделе 2, первый экспресс также является пер-

вым поездом, отправляющимся в соответствующем направлении, и время

его отправления можно вычислить с помощью (9). Пусть X множество

всех состояний, соответствующих всем возможным вариантам выбора пер-

вого экспресса и его типа. Тогда оптимальное значение функции (2) может

быть записано в виде

(13)

min

F (t, n^pA, n^pB

,s,b).

(t,n^pA,n^pB,s,b)∈X

Таким образом, принимая во внимание (11), (12) и (13), оптимальное зна-

чение (2) может быть получено с помощью динамического программирова-

ния. Более подробная информация по реализации вычислений будет пред-

ставлена в разделе 5.

4. Минимизация суммарного времени нахождения в системе

В данном разделе рассматривается задача минимизации (3) на множестве

всех расписаний, оптимальных для (2). Пусть F^∗ оптимальное значение

для (2). Любое расписание оптимально для (2) тогда и только тогда, когда

(14)

C^s,pi ≤ d^s,pi + F^∗ для любого s ∈ {A,B} и любого i ∈

Другими словами, необходимо найти расписание, доставляющее наименьшее

значение для (3) среди всех расписаний, удовлетворяющих условию (14). Сле-

довательно, в данном разделе будут рассматриваться только расписания, для

которых выполнено (14).

В отличие от раздела 3, который касался только приоритетных поез-

дов, теперь рассматриваются все поезда. Таким образом, с отправлением

каждого экспресса связано больше информации, что ведет к соответствую-

щему изменению определения состояния. Теперь состояние

это набор

(t, k^pA, k^oA, k^pB , k^oB, s, b, α, γ), где, как и в разделе 3, t и пара (s, b)

время от-

правления и тип соответствующего экспресса. Кроме того, α

категория

экспресса и γ категория поезда (если такой поезд существует), который

пропускает данный экспресс в разъезде. Если такой поезд не существует, то

γ принимает любое значение из {p, o}. Независимо от того, пропускает ли

какой-либо поезд данный экспресс или нет, k^γ¯s это количество поездов в

подмножестве множества N^γ¯s, которое состоит из всех поездов, прибываю-

щих в s после t. Каждое другое значение k^ux в (t, k^pA, k^oA, k^pB, k^oB , s, b, α, γ)

это количество поездов, которые отправляются из x в момент времени t или

позже. В частности, в силу (s2) состояние (t, k^pA, k^oA, k^pB , k^oB, s, b, α, γ) соответ-

ствует отправлению поезда, принадлежащего множеству N^αs, номер которого

равен k^αs.

Если α = o, то состояние (t, k^pA, k^oA, k^pB , k^oB, s, b, α, γ) предоставляет инфор-

мацию для вычисления

C^s,ok

-r^s,ok

=t+p_A +p_B -r^s,o,_k

а если γ = o и b = 2, то это состояние позволяет также вычислить

C^s,ok

-r^s,ok

= t + 2p_s - r^s,o._k

Следовательно, вклад в значение целевой функции (3) экспресса, отправ-

лению которого соответствует состояние (t, k^pA, k^oA, k^pB, k^oB , s, b, α, γ), и поезда,

который пропускает данный экспресс в разъезде (если такой поезд существу-

ет), равен

R(t, k^pA, k^oA, k^pB , k^oB, s, b, α, γ) =





2t + 3p_s + p_s - r^s,ok

- r^s,o для α = o,b = 2,γ = o;_k



t+p_A +p_B -r^s,o

для α = o, b = 2, γ = o;



(15)

t+p_A +p_B -r^s,o

для α = o, b = 2;

=



t + 2p_s - r^s,ok

для α = o, b = 2, γ = o;



 0

иначе.

Основываясь на одних и тех же концепциях динамического программиро-

вания, процедуры оптимизации для (2) и (3) имеют много общего, несмотря

на несколько важных отличий разные целевые функции; условие (14); и

разные множества поездов. Кроме того, оптимизационный подход, описанный

в этом разделе, применяется только после процедуры минимизации (2). По-

этому использование далее тех же обозначений Ω и F не вызовет путаницы,

а скорее подчеркнет сходство и облегчит изложение в разделе 5.

Рассмотрим все расписания, в которых индуцированные последовательно-

сти состояний содержат некоторое состояние (t, k^pA, k^oA, k^pB, k^oB, s, b, α, γ). На-

помним, что в этом разделе рассматриваются только расписания, удовле-

творяющие (14). Как и прежде, в каждой индуцированной последователь-

ности состояний состояния перечислены в порядке возрастания соответ-

ствующих времен отправления. Обозначим через Ω(t, k^pA, k^oA, k^pB, k^oB, s, b, α, γ)

множество всех состояний таких, что каждое из них сразу следу-

ет за (t, k^pA, k^oA, k^pB, k^oB , s, b, α, γ) по крайней мере в одной из упо-

мянутых выше последовательностей. Если k^oA + k^oB > 0, то определим

F (t, k^pA, k^oA, k^pB , k^oB, s, b, α, γ) как минимальное значение

∑ ∑

(16)

[C^s,oj - r^s,oj]

s∈{A,B} j≤k^s

на множестве рассматриваемых расписаний. Если k^oA + k^oB = 0, то положим

F (t, k^pA, k^oA, k^pB, k^oB, s, b, α, γ) = 0.

Далее для любых α ∈ {p, o} удобно использовать обозначение α = {p, o} \ {α}.

Если состояние (t, k^pA, k^oA, k^pB, k^oB , s, b, α, γ) соответствует отправлению послед-

него экспресса, то согласно разделу 2 k^ux в (t, k^pA, k^oA, k^pB, k^oB , s, b, α, γ) опреде-

ляется как



для x = s и u = α;





для x = s и u = α;

(17)

k^ux =

для x = s и u = γ;



0 для x = s,u = γ и b = 2;

для x = s, u = γ и b = 2.

Это означает, что

(18)

F (t, k^pA, k^oA, k^pB, k^oB, s, b, α, γ) = R(t, k^pA, k^oA, k^pB , k^oB

,s,b,α,γ).

Если экспресс, которому соответствует состояние (t, k^pA, k^oA, k^pB , k^oB, s, b, α, γ),

не является последним экспрессом в расписании, то

(19)

F (t, k^pA, k^oA, k^pB, k^oB, s, b, α, γ) = R(t, k^pA, k^oA, k^pB , k^oB

,s,b,α,γ) +

min

F (t^′,kpA,koA,kpB,koB, s^′, b^′, α^′, γ^′).

(t^′,kpA,koA,kpB,koB,s^′,b^′,α^′,γ^′)∈Ω(t,k^pA,k^oA,k^pB,k^oB,s,b,α,γ)

100

Обозначим через Y множество всех состояний, которые являются первы-

ми по крайней мере в одной последовательности состояний, индуцирован-

ной расписанием, удовлетворяющим (14). Тогда минимальное значение (3)

на множестве всех расписаний, оптимальных для (2), равно

(20)

min

F (t, n^pA, n^oA, n^pB, n^oB

,s,b,α,γ).

(t,n^pA,n^oA,n^pB,n^oB,s,b,α,γ)∈Y

Заметим, что (13) и (20) существенно различны. Действительно, чтобы пере-

числить все состояния в X, достаточно знать только n^pA, n^pA, rnpp

иrnpp

, в то

время как перечисление всех состояний в Y может потребовать значительно

более сложную вычислительную процедуру. Эта процедура представлена в

разделе 5.

5. Динамическое программирование

Для приведенной ниже оптимизационной процедуры требуется множе-

ство T моментов времени, которое содержит все времена отправления экс-

прессов во всех расписаниях, в которых каждый экспресс отправляется в

самый ранний возможный момент времени для экспресса этого типа. Такое

множество описано ниже.

Принимая во внимание (5)-(9), легко видеть, что время отправления лю-

бого экспресса представимо в виде

(21)

t=r^s,αi +m₁p_A +m₂p_B +m₃β

для некоторого α ∈ {p, o}, s ∈ {A, B}, i ∈ N^αs, и некоторых целых чисел m₁,

m₂ и m₃. Введем обозначение

n=n^pA +n^pB +n^oA +n^oB.

Отметим, что s и α в выражении (21) не обязательно совпадают с соответ-

ствующими параметрами рассматриваемого экспресса. Если для двух после-

довательных экспрессов α, s и i в выражении (21) остаются теми же самыми,

то согласно (7) и (9) m₁ и m₂ не могут увеличиться больше чем на 3 и не могут

уменьшиться больше чем на 1, тогда как m₃ не может увеличиться больше

чем на 2. Таким образом, m₁ и m₂ не превосходят 3n и не меньше (-n), а

m₃ не превосходит 2n. Следовательно, все возможные моменты отправления

экспресса принадлежат множеству

{

t| t ≥ 0, t = r^s,αi + m₁p_A + m₂p_B + m₃β,

i ∈ Nαs , s ∈ {A,B}, α ∈ {p,o}, m₁ ∈ {-n,...,0,1,... ,3n},

(22)

}

m₂ ∈ {-n,... ,0,1,... ,3n},m₃ ∈ {0,1,... ,2n}

мощности O(n⁴).

101

Рассмотрим задачу минимизации (2) и предположим, что n^pA > 0 и n^pB > 0,

поскольку в противном случае минимизация (2) тривиальна. Поскольку дан-

ная задача включает только приоритетные поезда, то, следуя подходу, при-

нятому в разделе 3, можно рассматривать только приоритетные поезда. Сле-

довательно, вместо (22) можно использовать в качестве T его подмножество

{

t| t ≥ 0, t = r^s,pi + m₁p_A + m₂p_B + m₃β, i ∈ N^ps, s ∈ {A,B},

m₁ ∈ {-(n^pA + n^pB),... ,0,1,... ,3(n^pA + n^pB)},

(23)

m₂ ∈ {-(n^pA + n^pB),... ,0,1,... ,3(n^pA + n^pB)},

}

m₃ ∈ {0,1,... ,2(n^pA + n^pB)}

Оптимизационная процедура, представленная в данном разделе, получает

оптимальное значение для (2) путем генерации последовательности множеств

V₁, ..., V_np

+n^p . Следовательно, количество множеств в этой последователь-_B

ности равно количеству поездов, поскольку, как и в разделе 3, рассматри-

ваются только приоритетные поезда. Каждое множество состоит из наборов

(t, k_A, k_B, s, b), которые являются кандидатами на состояния в оптимальном

для (2) расписании.

В каждом множестве V_k, 1≤ k ≤ n^pA + n^pB, содержатся только кандидаты,

удовлетворяющие условию

k^pA + k^pB = k.

Таким образом, ввиду (10) все кандидаты на состояние, соответствующее по-

следнему экспрессу, могут быть только в множествах V₁ и V₂. Множество V₁

содержит только таких кандидатов. Более точно, это множество состоит из

всех наборов вида (t, 1, 0, A, 0), где t ∈ T и t ≥ r^A,p1, и всех наборов вида

(t, 0, 1, B, 0), где t ∈ T и t ≥ r^B,p1.

Множество V₂ содержит всех кандидатов на состояние, соответствую-

щее последнему экспрессу и удовлетворяющее равенству k_A + k_B = 2, а

также других кандидатов, удовлетворяющих этому равенству. Подмноже-

ство V₂ всех кандидатов на последнее состояние состоит из всех наборов типа

(t, 1, 1, A, 2), где t ∈ T и t ≥ r^A,p1, и всех наборов типа (t, 1, 1, B, 2), где t ∈ T и

t≥r^B,p1.

Множества V₁, . . . , V_np

генерируются одно за другим в порядке воз-

+n^p

растания их индексов. После включения всех кандидатов на состояние, со-

ответствующее последнему экспрессу, анализируются наборы для каждого

множества один за другим. Чтобы быть включенным в множество V_k, на-

бор (t, k_A, k_B, s, b), для которого выполняется k_A + k_B = k, должен обладать

несколькими свойствами. Эти свойства включают:

(p1) k_s ≤ n^s,p для s ∈ {A, B};

(p2) r^s,p ≤ t для t ∈ T ;_k

(p3) если b = 0, то k_s ≥ 1;

102

(p4) если b = 1, то k_s ≥ 2;

(p5) если k^pA = n^pA и k^pB = n^pB, то t вычисляется по (9).

Более того, рассматриваемый набор (t, k_A, k_B , s, b), удовлетворяющий

свойствам (p1)-(p5), включается в множество VkA+k_B , если только существу-

ет набор (t^′,kA,kB, s^′, b^′), который включен в одно из ранее сгенерированных

множеств, и имеет t^′, которое можно вычислить по формулам (5)-(8); имеет

kA иkB, удовлетворяющие (24) и (25), приведённым ниже; и удовлетворяет

условию (26), приведённому ниже:

(24)

ks = ks

− 1,

{

k_s - 1, если b = 2,

k_¯

(25)

s =

k_s

иначе,

(26)

если b = 1, то s = s^′ и b^′

= 0.

Для каждого набора (t, k_A, k_B, s, b), обладающего требуемыми свойствами

и, следовательно, принадлежащего VkA+k_B , обозначим через W (t, kA, kB , s, b)

множество всех наборов (t^′,kA,kB , s^′, b^′) в ранее сгенерированных множествах

таких, что t^′ совпадает с моментом времени, вычисленным по формуле (8);

kA иkB удовлетворяют (24) и (25); и выполняется (26). Если (t, kA, kB , s, b)

выбирается в качестве состояния, то

W (t, k_A, k_B, s, b) = Ω(t, k_A, k_B, s, b).

Тогда с учетом (13) оптимальное значение (2) равно

min

f (t, k_A, k_B, s, b),

(t,n_A,n_B ,s,b)∈Vnp

где f определяется подобно F в (11) и (12), т.е. для каждого кандидата

(t, k_A, k_B, s, b) на состояние, соответствующее последнему экспрессу,

(27)

f (t, k_A, k_B, s, b) = L(t, k_A, k_B

,s,b),

и для любого другого (t, k_A, k_B , s, b) в V₂ ∪ . . . ∪ V_np

+n^pB

f (t, k_A, k_B, s, b) =

{

}

(28)

= max L(t,k_A,k_B,s,b),

min

f (t^′,kA,kB, s^′, b^′)

(t^′,kA,kB,s^′,b^′)∈W (t,k_A,k_B,s,b)

Учитывая мощность множества T (см. (23)), сложность данной оптимизаци-

онной процедуры составляет O((n^pA + n^pB)⁶).

Процедура построения расписания, доставляющего минимальное значе-

ние для (3) среди всех расписаний, оптимальных для (2), сходна с описан-

ной процедурой минимизации (2) с одним важным отличием: чтобы гаран-

тировать (14), каждый набор должен удовлетворять дополнительным усло-

виям (см. (g6) и (g7) ниже). Согласно этой процедуре n множеств V₁, . . . , V_n

103

генерируются одно за другим в порядке возрастания их индексов. Анало-

гично описанному выше множество V_k, 1 ≤ k ≤ n, содержит только наборы

(t, k^pA, k^oA, k^pB , k^oB, s, b, α, γ), удовлетворяющие условию

k^pA + k^oA + k^pB + k^oB = k.

Каждый набор в множествах V₁, . . . , V_n является кандидатом на состоя-

ние в искомом расписании. Чтобы быть включенным в множество, набор

(t, k^pA, k^oA, k^pB , k^oB, s, b, α, γ) должен обладать несколькими свойствами. Первая

группа свойств:

(g1) k^εs ≤ n^s,ε для ε ∈ {p, o} и s ∈ {A, B};

(g2) r^s,α ≤ t и t ∈ T ;_k

(g3) если b = 0, то k^γ¯s ≥ 1;

(g4) если b = 1, то k^αs + k^αs ≥ 2;

(g5) если k^pA = n^pA, k^oA = n^oA, k^pB = n^pB, и k^oB = n^oB, то t вычисляется по (9).

Эти свойства аналогичны (p1)-(p5). Вторая группа свойств:

(g6) если α = p, то t + p_A + p_B ≤ dspp

+F^∗;

(g7) если γ = p и b = 2, то t + 2p_s ≤ dspp

+F^∗

гарантирует, что полученное расписание будет удовлетворять (14).

Для того чтобы (t, k^pA, k^oA, k^pB, k^oB , s, b, α, γ) был выбран в качестве

кандидата на состояние, должен существовать уже выбранный набор

(t^′,kpA,koA,kpB,koB, s^′, b^′, α^′, γ^′) такой, что

kα

k^γ

(29)

= k^αs - 1,

=k^αs и

=k^γ¯s,

{

k^γ¯s - 1, если b = 2,

k^γ

(30)

k^γ¯s

иначе.

Равенства

(29) и (30) выполняют ту же роль, что (24) и (25) ра-

нее. Более точно, набор (t, k^pA, k^oA, k^pB, k^oB , s, b, α, γ), удовлетворяющий (g1)-

(g7), включается в множество V_kp+koA+kpB+ko , если только существует наборB

(t^′,kpA,koA,kpB,koB, s^′, b^′, α^′, γ^′), который уже включен в одно из ранее сгенери-

рованных множеств и для которого t^′ совпадает с моментом времени, вы-

численным по формулам (5)-(8);kpA,koA,kpB,koB удовлетворяют (29) и (30);

и выполняется (26). Обозначим через W (t, k^pA, k^oA, k^pB, k^oB , s, b, α, γ) множество

всех таких наборов (t^′,kpA,koA,kpB,koB , s^′, b^′, α^′, γ^′). Тогда минимальное значе-

ние (3) на множестве всех расписаний, оптимальных для (2), может быть

записано как

min

f (t, k^pA, k^oA, k^pB, k^oB, s, b, α, γ),

(t,k^pA,k^oA,k^p

,k^oB,s,b,α,γ)∈Vn

где f определяется следующим образом.

Для каждого кандидата (t, k^pA, k^oA, k^pB, k^oB, s, b, α, γ) на состояние, соответ-

ствующее последнему экспрессу,

f (t, k^pA, k^oA, k^pB , k^oB, s, b, α, γ) = R(t, k^pA, k^oA, k^pB, k^oB , s, b, α, γ).

104

Для каждого элемента V₂ ∪ . . . ∪ V_n, который не является кандидатом на

состояние, соответствующее последнему экспрессу,

f (t, k^pA, k^oA, k^pB , k^oB, s, b, α, γ) = R(t, k^pA, k^oA, k^pB, k^oB , s, b, α, γ) +

min

f (t^′,kpA,koA,kpB,koB , s^′, b^′, α^′, γ^′).

(t^′,kpA,koA,kpB,koB,s^′,b^′,α^′,γ^′)∈W (t,k^pA,k^oA,k^pB,k^oB,s,b,α,γ)

Принимая во внимание мощность множества T (см. (22)), данная оптимиза-

ционная процедура имеет временную сложность O(n⁸).

6. Заключение

Полиномиальные алгоритмы, представленные в статье, направлены на

уменьшение прямого воздействия блокировки одного из путей на двухпутном

участке дороги, измеряемого максимальным временным смещением приори-

тетных поездов и общим (а значит, и средним) временем нахождения в систе-

ме для обычных поездов. Направления дальнейшего обобщения представлен-

ного подхода могут включать минимизацию других мер влияния блокировки;

уменьшение влияния блокировки на более широкие участки железнодорож-

ной сети; планирование работ по техническому обслуживанию, требующих

временного закрытия некоторых сегментов железнодорожной сети, и разра-

ботка быстрых аппроксимационных алгоритмов.

СПИСОК ЛИТЕРАТУРЫ

1. Cacchiani V., Huisman D., Kidd M., Kroon L., Toth P., Veelenturf L., Wagenaar J.

An Overview of Recovery Models and Algorithms for Real-Time Railway Reschedul-

ing // Transport. Res. Part B. 2014. V. 63. P. 15-37.

2. Lusby R., Larsen J., Ehrgott M., Ryan D. Railway Track Allocation: Models and

Methods // OR Spectrum. 2011. V. 33. No. 4. P. 843-883.

3. Brucker P., Heitmann S., Knust S. Scheduling Railway Traffic at a Construction

Site // OR Spectrum. 2002. V. 24. No. 1. P. 19-30.

4. Зиндер Я., Лазарев А.А., Мусатова Е.Г., Тарасов И.А. Построение расписаний

двухстороннего движения на однопутной железной дороге с разъездом // АиТ.

2018. № 3. С. 144-166.

Zinder Y., Lazarev A.A., Musatova E.G., Taracov I.A. Scheduling the Two-Way

Traffic on a Single-Track Railway With a Siding // Autom. Remote Control. 2018.

V. 79. No. 3. P. 506-523.

5. Zinder Y., Lazarev A., Musatova E.,Taracov I., Khusnullin N. Two-Station Single

Track Scheduling Problem // IFAC-PapersOnLine. 2016. V. 49. No. 12. P. 231-236.

Статья представлена к публикации членом редколлегии Ф.Т. Алескеровым.

Поступила в редакцию 02.07.2019

После доработки 15.10.2019

Принята к публикации 28.11.2019

105