ИИ на путях: как решить задачу перепланирования расписания движения поездов23.01.2025 18:45

Привет, Хабр. Я Артур Саакян, главный специалист по анализу данных и машинному обучению в ПГК Диджитал. Мы разрабатываем уникальные цифровые продукты для железнодорожных перевозок, такие как оптимизация ЖД перевозок, навигатор, ЖД карты, цифровой вагон и так далее.

В этой статье опишу подход к оптимизации расписания поездов в реальном времени при помощи обучения с подкреплением (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) — область машинного обучения, в которой обучение осуществляется посредством взаимодействия с окружающей средой. Это целенаправленное обучение, в котором агент (обучаемый) не получает информации о том, какие действия следует выполнить, вместо этого он узнает о последствиях своих действий.

Цикл взаимодействия RL-агента и среды

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

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

Структура Q-table (Q-функция)

Ключевые элементы в-learning:

В состояниивыполняется действие, возвращается вознаграждение R(s, a) , а затем -функция обновляется по формуле:

$Q(s, a) \leftarrow Q(s, a) + \alpha \big[ R(s, a) + \gamma \max_a Q(s',a) - Q(s, a) \big],$

где

Основная идея-обучения заключается в обновлении Q(s, a) методом проб и ошибок, в ходе которого действия выбираются по эпсилон-жадному алгоритму (epsilon-greedy, $\varepsilon$ -greedy). Эпсилон-жадный алгоритм — это правило выбора действия, которое направлено на достижение компромисса между эксплуатацией (exploitation) и исследованием (exploration). В любом состоянииметод выбирает действие $\arg \max_a Q(s, a)$ с вероятностью $(1 - \varepsilon)$ (exploitation) или выбирает случайным образом из всех действий, независимо от значения, с вероятностью $\varepsilon$ (exploration).

-функция постоянно обновляется (от эпизода к эпизоду). Эпизод — это одна симуляция от начального состояния среды до достижения конечного состояния. На основе хорошо обученного Q(s, a) оптимальное действие при заданном состояниибудет $\arg \max_a Q(s, a)$ .

Моделирование железнодорожной среды

Железнодорожная среда представлена станциями, соединенными открытыми путями. Определим станцию как ресурс, который состоит как минимум из одного пути. Рассмотрим двухпутную железнодорожную линию (double-track railway line) так, что каждый открытый путь является однонаправленным, что означает, что он может быть занят только поездами, идущими в определенном направлении. Путь может быть занят несколькими поездами одновременно, если эти поезда разделены безопасными расстояниями.

A double-track railway line

Построим модель железнодорожной среды методом моделирования на основе событий.

Событие — это отправление или прибытие поезда на станцию.

Атрибуты, связанные с событием :

Атрибуты $p(e), \ t(e), \ s(e), \ r(e), \ o(e)$ и $\theta(e)$ является фиксированными, а атрибуты $\chi(e), \Delta(e)$ — переменными.

Атрибуты, связанные с ресурсом:

Атрибуты $u(r), \ p(r), \ d(r)$ и n(r) являются фиксированными, а атрибуты y(r), z(r) — переменными.

Выбор события: на каждом шаге моделирования будет выбрано событиес самым ранним перенесенным временем (— множество событий)

$e^* = \arg \min_e \{ \chi(e), e \in E \}$

и действия будет выбрано агентом для события e^* .

Для ресурса станции r_s доступность определяется по параметру y(r_s) , где каждая запись указывает самое раннее время, когда путь r_s будет доступен. Предполагается, что каждый трек r_s является двунаправленным: d(r_s) = both .

Размер y(r) равен количеству путей в . Каждая запись y(r_s) инициализируется значением 0, что означает, что соответствующая дорога готова к использованию, и когда поезд начинает занимать дорогу, значение обновляется до ожидаемого времени отправления этого поезда с этой дороги плюс минимальный интервал $h_{d, a}$ , после которого другой поезд может прибыть на ту же дорогу. Другими словами, интервал отправление-прибытие $h_{d, a}$ применяется между последовательными поездами, которые будут занимать один и тот же путь станции. Если запись y(r_s) связана с временем более ранним, чем текущее время, и ни один поезд не будет занимать его в этот момент, то ее значение будет обновлено до 0 снова, указывая на то, что соответствующий путь доступен.

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

$h_{d, a}$ — минимальный интервал между отправлением поезда и прибытием другого поезда, занимающего тот же путь станции;
$h_{d, d}$ — минимальный интервал между временем отправления двух последовательных поездов с одной и той же станции. Время отправления поезда со станции соответствует времени выхода поезда на следующий открытый путь с этой станции;
$h_{a, a}$ — минимальный интервал между временем прибытия двух последовательных поездов на одну и ту же станцию. Время прибытия поезда на станцию соответствует времени отправления поезда с предыдущего открытого пути на эту станцию.

Для ресурса открытого пути r_0 доступность определяется y(r_0) , который в этом случае состоит только из одной записи. Рассматривается двухпутная железнодорожная линия, поэтому каждый открытый путь r_0 является однонаправленным, что указывает на то, что он может быть занят только поездами, идущими в определенном направлении d(r_0) = up или d(r_0) = down .

Значение y(r_0) инициализируется 0, указывая на то, что открытая дорога готова к использованию. Когда поезд въезжает на этот открытый путь, y(r_0) будет обновлен до времени въезда (т.е. времени отправления с расположенной выше станции относительно открытого пути) плюс минимальный интервал $h_{d, d}$ , после которого другой поезд может въезжать на тот же путь. Минимальный интервал движения ( $h_{d, d}$ или $h_{a, a}$ ) определяется как минимальный интервал времени между временем отправления/прибытия двух последовательных поездов на станцию. Для предотвращения «обгона» на открытом пути (в случае увеличения времени движения) между двумя последовательными поездами, которые прибывают на следующую станцию с одного и того же открытого пути, устанавливается минимальный интервал $h_{a, a}$ .

Каждый раз, когда поезд въезжает на открытый путь, его ожидаемое время отправления $\pi_t$ с этого пути сравнивается с ожидаемым временем отправления $\pi_{t'}$ предыдущего поезда , который въехал на тот же открытый путь ранее и все ещё занимает этот путь.

Если $\pi_t - \pi_t' < h_{a, a}$ , тогда $\pi_t \leftarrow \pi_t' + h_{a, a}$ . Иначе, обновления $\pi_t$ не произойдёт.

Атрибут z(r_0) инициализируется как пустой список для ресурса открытого пути r_0 . Каждый раз, когда поезд въезжает на открытый ресурс пути r_0 , к z(r_0) будет добавлен один элемент, указывающий соответствующий номер поезда. Когда поезд покидает ресурс открытого пути, его номер поезда будет удалён из z(r_0) .

Для ресурса станции r_s, z(r_s) инициализируется как список, состоящий из n(r_s) элементов с значением 0. Здесь n(r_s) — количество путей в r_s . Элемент z(r_s) будет обновлён, когда поезд прибудет на соответствующий путь, и вернётся к значению 0, когда поезд отправится с пути.

Множество действий (action set): {0, 1}

Действие a = 0 означает, что агент решает не реализовывать событиев момент времени $\chi(e)$ , а вместо этого отложить его на фиксированное $\lambda$ минут: $\chi(e^*) \leftarrow \chi(e^*) + \lambda$

Действие a = 1 означает, что агент решает реализовать событиев момент времени $\chi(e)$ . Если это действительно реализуемо, то e^* удаляется из набора событий.

Действие a = 1 может быть нереализуемо, если $\chi(e^*) > \min\{ y (r'), r' = r (e) \}» src=«https://habrastorage.org/getpro/habr/upload_files/265/ae7/7c9/265ae77c93cad82d0c2cd7b097987b09.svg» />, что указывает на то, что ни один из путей в ресурсе <img alt=$ не доступен для приёма поезда t(e') в момент времени $\chi(e')$ . В этом случае моделирование завершается. Здесь — это ресурс r(e) , который будет занят событием , когда событиепроизойдёт.

После каждого действия ( a = 0 или a = 1 ) переменные атрибуты ресурсов и событий в будут обновляться соответствующим образом.

Например, если событие e^* задерживается на $\lambda$ минут, то перенесенное время и задержки следующих событий, соответствующих тому же поезду t(e^*) будут обновлены перед началом следующего шага моделирования.

Предположим, что событие — одно из следующих событий поезда t(e^*) , тогда его перенесенное время $\chi(e)$ будет обновлено до самого раннего времени, когда оно могло произойти, что считается как $\chi(e^*)$ плюс самое короткое время, необходимое от события e^* до события , если это самое ранее время позже, чем o(e) . В противном случае $\chi(e)$ не будет обновлен, поскольку более ранее отправление/прибытие не допускается.

Функция вознаграждения (reward function) моделируется следующим образом:

Если a = 0 , то штраф равен -1 (поскольку задерживает прибытие/отправление поезда). Если a = 1 , и это действие реализуемо, то награда равна +1 (т.е. нет эксплуатационного конфликта). В противном случае действие a = 1 даётся со штрафом -10.

Состояние s tate железнодорожной среды определяется как

$state = \{ \tilde{\Delta}(e^*), \ c(r_1), \ ..., \ c(r_n), \ r(e^*) \},$

где

Уровень загруженности ресурса определяется соответственно для ресурса станции и путевого ресурса следующим образом:

Уровень перезагрузки $c(r_s), \ r_s$ — ресурс станции:

Уровень перезагрузки $c(r_0), \ r_0$ — открытый путевой ресурс:

Доступность или недоступность трека ресурса зависит от соответствующей записи в y(r) , которая указывает самое раннее время, когда трек станет доступным. Только если самое раннее доступное время трека меньше x(e^*) , то трек считается доступным на текущем шаге моделирования.

Размер состояния state зависит от количества рассматриваемых ресурсов. В крайнем случае рассматриваются все ресурсы, включенные в железнодорожную среду, что может привести к большому размеру состояния, вызывающему проблемы с памятью. Поэтому в векторе состояния state рассматривается толькоресурсов, включая ресурс, который в данный момент занят поездом t(e^*) , и следующие n - 1 ресурсов, которые будут заняты поездом t(e^*) .

Моделирование железнодорожной среды инициализируется, когда все поезда ожидают в своих исходных пунктах, и завершится, когда все поезда достигнут своих пунктов назначения (что соответствует пустому ), или действие a = 1 не может быть реализовано из-за конфликта.

Заключение

Задачу перепланирования расписания движения поездов часто решают при помощи комбинаторной оптимизации. В данной статье был рассмотрен подход к решению через такую область машинного обучения, как обучения с подкреплением (RL). Была рассмотрена модель железнодорожной среды. Описан подход к применению RL для решения задачи. Описанный метод был протестирован на части голландских железных дорог. Результаты показывают, что метод позволил найти качественное решение по перепланированию в рамках ограниченного количества обучающих эпизодов. Ссылка на статью с более подробным описанием подхода и результатов применения.