Привет. Я Артур Саакян, главный специалист по анализу данных и машинному обучению в ПГК Диджитал. Мы разрабатываем уникальные цифровые продукты для железнодорожных перевозок, такие как оптимизация ЖД перевозок, навигатор, ЖД карты, цифровой вагон и так далее.
В этой статье опишу подход к оптимизации расписания поездов в реальном времени при помощи обучения с подкреплением (RL), который применим и к российским грузовым ж/д перевозкам, но пока не используется. Тезисы статьи:
-
Перепланирование расписания движения поездов (Train Timetable Rescheduling)
-
Коротко об RL и Q-learning
-
Моделирование железнодорожной среды
-
Заключение
Перепланирование расписания движения поездов (Train Timetable Rescheduling)
Управление железнодорожным движением в режиме реального времени (Real-time railway traffic management) является важной частью логистики. Оно включает в себя планирование, контроль и организацию транспортных услуг, необходимых для перемещения транспортных средств (например, подвижного состава) и грузов.
Железнодорожные операции базируются на расписании, которое устанавливает время прибытия и отправления каждого поезда на каждой станции, учитывая множество эксплуатационных требований. В идеальном мире поезда следуют строго по графику. Однако на практике ежедневно возникают различные изменения и нарушения.
Когда возникают такие ситуации, поезд отправляется со станции с первичной задержкой (primary delay). Если задержка значительная, она может привести к вторичным задержкам прибытия и/или отправления того же поезда, а также повлиять на последующие поезда из-за накладывающихся маршрутов и перегрузки (secondary delay). Поэтому при возникновении задержки важно прогнозировать возможные конфликты и разрешать их, стремясь минимизировать общие вторичные задержки. Этот процесс называется перепланированием расписания движения поездов (Train Timetable Rescheduling, TTR).
Коротко об RL и Q-learning
Обучение с подкреплением (RL, Reinforcement Learning) – область машинного обучения, в которой обучение осуществляется посредством взаимодействия с окружающей средой. Это целенаправленное обучение, в котором агент (обучаемый) не получает информации о том, какие действия следует выполнить, вместо этого он узнает о последствиях своих действий.

Основная идея обучения с подкреплением делает его перспективным для решения задач в реальном времени, поскольку агент уже научился решать задачу заранее, а полученный обширный опыт гарантирует его производительность с точки зрения качества решения.
-learning — это метод обучения с подкреплением без модели (model-free reinforcement learning method), которому не нужна функция перехода состояний среды (transition function). Таким образом, он подходит для сложной среды (моделирование среды с высокой точность является сложной задачей). В этом методе используется
-функция, которая каждой паре состояние-действие ставит в соответствие возможную награду за его совершение в этом конкретном состоянии.

Ключевые элементы в-learning:
-
- множество состояний;
-
- множество действий;
-
- функция вознаграждения. Она возвращает вознаграждение за действие
в состоянии
;
-
- функция оценки значения пары состояние-действие.
-функция указывает, насколько хорошим является действие
в состоянии
.
В состояниивыполняется действие
, возвращается вознаграждение
, а затем
-функция обновляется по формуле:
где
-
- размер шага (learning rate). Гиперпараметр
определяет в какой степени новая информация должна переопределять старую информацию,
;
-
- коэффициент дисконтирования (discount factor). Гиперпараметр
определяет важность будущих вознаграждений,
;
-
- следующее состояние из состояния
путем выполнения действия
.
Основная идея-обучения заключается в обновлении
методом проб и ошибок, в ходе которого действия выбираются по эпсилон-жадному алгоритму (epsilon-greedy,
-greedy). Эпсилон-жадный алгоритм - это правило выбора действия, которое направлено на достижение компромисса между эксплуатацией (exploitation) и исследованием (exploration). В любом состоянии
метод выбирает действие
с вероятностью
(exploitation) или выбирает случайным образом из всех действий, независимо от значения
, с вероятностью
(exploration).
-функция постоянно обновляется (от эпизода к эпизоду). Эпизод - это одна симуляция от начального состояния среды до достижения конечного состояния. На основе хорошо обученного
оптимальное действие при заданном состоянии
будет
.
Моделирование железнодорожной среды
Железнодорожная среда представлена станциями, соединенными открытыми путями. Определим станцию как ресурс, который состоит как минимум из одного пути. Рассмотрим двухпутную железнодорожную линию (double-track railway line) так, что каждый открытый путь является однонаправленным, что означает, что он может быть занят только поездами, идущими в определенном направлении. Путь может быть занят несколькими поездами одновременно, если эти поезда разделены безопасными расстояниями.

Построим модель железнодорожной среды методом моделирования на основе событий.
Событие - это отправление или прибытие поезда на станцию.
Атрибуты, связанные с событием :
-
- тип события
,
;
-
- поезд, соответствующий событию
;
-
- станция, соответствующая событию
;
-
- ресурс, который будет занят поездом
, когда произойдёт событие
;
-
- первоначально запланированное время события
;
-
- начальная задержка события
;
-
- перенесенное время события
;
-
- задержка события
.
Атрибуты и
является фиксированными, а атрибуты
- переменными.
Атрибуты, связанные с ресурсом:
-
- индекс ресурса
, который является уникальным номером, присвоенным каждой станции или участку,
;
-
- тип ресурса: станция или путь;
-
- возможные направления поезда,
;
-
- количество путей в
;
-
- вектор,
-й элемент которого указывает самое раннее время, когда путь
из
станет доступным;
-
- список,
-й элемент которого указывает на поезд, который в данный момент занимает путь
из
.
Атрибутыи
являются фиксированными, а атрибуты
- переменными.
Выбор события: на каждом шаге моделирования будет выбрано событиес самым ранним перенесенным временем (
- множество событий)
и действие будет выбрано агентом для события .
Для ресурса станции доступность определяется по параметру
, где каждая запись указывает самое раннее время, когда путь
будет доступен. Предполагается, что каждый трек
является двунаправленным:
.
Размерравен количеству путей в
. Каждая запись
инициализируется значением 0, что означает, что соответствующая дорога готова к использованию, и когда поезд начинает занимать дорогу, значение обновляется до ожидаемого времени отправления этого поезда с этой дороги плюс минимальный интервал
, после которого другой поезд может прибыть на ту же дорогу. Другими словами, интервал отправление-прибытие
применяется между последовательными поездами, которые будут занимать один и тот же путь станции. Если запись
связана с временем более ранним, чем текущее время, и ни один поезд не будет занимать его в этот момент, то ее значение будет обновлено до 0 снова, указывая на то, что соответствующий путь доступен.
Интервалы, необходимые для обеспечения безопасной работы поездов:
-
- минимальный интервал между отправлением поезда и прибытием другого поезда, занимающего тот же путь станции;
-
- минимальный интервал между временем отправления двух последовательных поездов с одной и той же станции. Время отправления поезда со станции соответствует времени выхода поезда на следующий открытый путь с этой станции;
-
- минимальный интервал между временем прибытия двух последовательных поездов на одну и ту же станцию. Время прибытия поезда на станцию соответствует времени отправления поезда с предыдущего открытого пути на эту станцию.
Для ресурса открытого пути доступность определяется
, который в этом случае состоит только из одной записи. Рассматривается двухпутная железнодорожная линия, поэтому каждый открытый путь
является однонаправленным, что указывает на то, что он может быть занят только поездами, идущими в определенном направлении
или
.
Значение инициализируется 0, указывая на то, что открытая дорога готова к использованию. Когда поезд въезжает на этот открытый путь,
будет обновлен до времени въезда (т.е. времени отправления с расположенной выше станции относительно открытого пути) плюс минимальный интервал
, после которого другой поезд может въезжать на тот же путь. Минимальный интервал движения (
или
) определяется как минимальный интервал времени между временем отправления/прибытия двух последовательных поездов на станцию. Для предотвращения "обгона" на открытом пути (в случае увеличения времени движения) между двумя последовательными поездами, которые прибывают на следующую станцию с одного и того же открытого пути, устанавливается минимальный интервал
.
Каждый раз, когда поезд въезжает на открытый путь, его ожидаемое время отправления
с этого пути сравнивается с ожидаемым временем отправления
предыдущего поезда
, который въехал на тот же открытый путь ранее и все ещё занимает этот путь.
Если , тогда
. Иначе, обновления
не произойдёт.
Атрибутинициализируется как пустой список для ресурса открытого пути
. Каждый раз, когда поезд въезжает на открытый ресурс пути
, к
будет добавлен один элемент, указывающий соответствующий номер поезда. Когда поезд покидает ресурс открытого пути, его номер поезда будет удалён из
.
Для ресурса станции инициализируется как список, состоящий из
элементов со значением 0. Здесь
- количество путей в
. Элемент
будет обновлён, когда поезд прибудет на соответствующий путь, и вернётся к значению 0, когда поезд отправится с пути.
Множество действий (action set): {0, 1}
Действие означает, что агент решает не реализовывать событие
в момент времени
, а вместо этого отложить его на фиксированное
минут:
Действие означает, что агент решает реализовать событие
в момент времени
. Если это действительно реализуемо, то
удаляется из набора событий
.
Действие может быть нереализуемо, если
, что указывает на то, что ни один из путей в ресурсе
не доступен для приёма поезда
в момент времени
. В этом случае моделирование завершается. Здесь
- это ресурс
, который будет занят событием
, когда событие
произойдёт.
После каждого действия ( или
) переменные атрибуты ресурсов и событий в
будут обновляться соответствующим образом.
Например, если событие задерживается на
минут, то перенесенное время и задержки следующих событий, соответствующих тому же поезду
будут обновлены перед началом следующего шага моделирования.
Предположим, что событие - одно из следующих событий поезда
, тогда его перенесенное время
будет обновлено до самого раннего времени, когда оно могло произойти, что считается как
плюс самое короткое время, необходимое от события
до события
, если это самое ранее время позже, чем
. В противном случае
не будет обновлен, поскольку более раннее отправление/прибытие не допускается.
Функция вознаграждения (reward function) моделируется следующим образом:
Если , то штраф равен -1 (поскольку задерживается прибытие/отправление поезда). Если
, и это действие реализуемо, то награда равна +1 (т.е. нет эксплуатационного конфликта). В противном случае действие
даётся со штрафом -10.
Состояниежелезнодорожной среды определяется как
где
-
- текущее событие;
-
- задержка события
;
-
- уровень перегрузки ресурса
,
;
-
- ресурс, который будет занят поездом
, когда событие
произойдёт,
;
-
, если
, где
- наибольшая рассматриваемая задержка. Иначе,
.
Уровень загруженности ресурса определяется соответственно для ресурса станции и путевого ресурса следующим образом:
Уровень перезагрузки - ресурс станции:
-
, если все пути в
доступны;
-
, если один путь в
недоступен;
-
, если по крайней мере два пути в
недоступны.
Уровень перезагрузки - открытый путевой ресурс:
-
, если
не занят ни одним поездом;
-
, если
занят одним поездом;
-
, если
занят по крайней мере двумя поездами.
Доступность или недоступность трека ресурса зависит от соответствующей записи в , которая указывает самое раннее время, когда трек станет доступным. Только если самое раннее доступное время трека меньше
, то трек считается доступным на текущем шаге моделирования.
Размер состояния зависит от количества рассматриваемых ресурсов. В крайнем случае рассматриваются все ресурсы, включенные в железнодорожную среду, что может привести к большому размеру состояния, вызывающему проблемы с памятью. Поэтому в векторе состояния
рассматривается только
ресурсов, включая ресурс, который в данный момент занят поездом
, и следующие
ресурсов, которые будут заняты поездом
.
Моделирование железнодорожной среды инициализируется, когда все поезда ожидают в своих исходных пунктах, и завершится, когда все поезда достигнут своих пунктов назначения (что соответствует пустому ), или действие
не может быть реализовано из-за конфликта.
Заключение
Задачу перепланирования расписания движения поездов часто решают при помощи комбинаторной оптимизации. В данной статье был рассмотрен подход к решению через такую область машинного обучения, как обучения с подкреплением (RL). Была рассмотрена модель железнодорожной среды. Описан подход к применению RL для решения задачи. Описанный метод был протестирован на части голландских железных дорог. Результаты показывают, что метод позволил найти качественное решение по перепланированию в рамках ограниченного количества обучающих эпизодов. Ссылка на статью с более подробным описанием подхода и результатов применения.
Автор: artur_temievich