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

в 15:30, , рубрики: artificial intelligence, machine learning, reinforcement learning, жд, ИИ, искусственный интеллект, машинное обучение, обучение с подкреплением

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

В этой статье опишу подход к оптимизации расписания поездов в реальном времени при помощи обучения с подкреплением (RL), который применим и к российским грузовым ж/д перевозкам, но пока не используется. Тезисы статьи:

  1. Перепланирование расписания движения поездов (Train Timetable Rescheduling)

  2. Коротко об RL и Q-learning

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

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

Перепланирование расписания движения поездов (Train Timetable Rescheduling)

Управление железнодорожным движением в режиме реального времени (Real-time railway traffic management) является важной частью логистики. Оно включает в себя планирование, контроль и организацию транспортных услуг, необходимых для перемещения транспортных средств (например, подвижного состава) и грузов.

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

Когда возникают такие ситуации, поезд отправляется со станции с первичной задержкой (primary delay). Если задержка значительная, она может привести к вторичным задержкам прибытия и/или отправления того же поезда, а также повлиять на последующие поезда из-за накладывающихся маршрутов и перегрузки (secondary delay). Поэтому при возникновении задержки важно прогнозировать возможные конфликты и разрешать их, стремясь минимизировать общие вторичные задержки. Этот процесс называется перепланированием расписания движения поездов (Train Timetable Rescheduling, TTR).

Коротко об RL и Q-learning

Обучение с подкреплением (RL, Reinforcement Learning) – область машинного обучения, в которой обучение осуществляется посредством взаимодействия с окружающей средой. Это целенаправленное обучение, в котором агент (обучаемый) не получает информации о том, какие действия следует выполнить, вместо этого он узнает о последствиях своих действий.

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

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

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

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

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

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

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

  • S- множество состояний;

  • A- множество действий;

  • R(s, a) - функция вознаграждения. Она возвращает вознаграждение за действиеaв состоянииs;

  • Q(s, a) - функция оценки значения пары состояние-действие.Q-функция указывает, насколько хорошим является действиеaв состоянииs.

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

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

где

  • alpha - размер шага (learning rate). Гиперпараметрalphaопределяет в какой степени новая информация должна переопределять старую информацию, 0 < alpha leq 1;

  • gamma - коэффициент дисконтирования (discount factor). Гиперпараметрgammaопределяет важность будущих вознаграждений, 0 leq gamma leq 1;

  • s'- следующее состояние из состояния s путем выполнения действия a.

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

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

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

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

A double-track railway line

A double-track railway line

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

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

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

  • p(e)- тип событияe, p(e) in {arr, dep};

  • t(e)- поезд, соответствующий событиюe;

  • s(e)- станция, соответствующая событиюe;

  • r(e)- ресурс, который будет занят поездом t(e), когда произойдёт событиеe;

  • o(e)- первоначально запланированное время событияe;

  • theta(e)- начальная задержка событияe;

  • chi(e) - перенесенное время событияe;

  • Delta(e)- задержка событияe.

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

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

  • u(r)- индекс ресурсаr, который является уникальным номером, присвоенным каждой станции или участку, u(r) in { 1, ..., n };

  • p(r)- тип ресурса: станция или путь;

  • d(r)- возможные направления поезда,d(r) in { up, down, both };

  • n(r)- количество путей вr;

  • y(r)- вектор,i-й элемент которого указывает самое раннее время, когда путьiиз rстанет доступным;

  • z(r)- список,i-й элемент которого указывает на поезд, который в данный момент занимает путьi из r.

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

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

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)равен количеству путей в 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}.

Каждый раз, когда поезд t въезжает на открытый путь, его ожидаемое время отправления pi_t с этого пути сравнивается с ожидаемым временем отправления pi_{t'}предыдущего поезда 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 означает, что агент решает не реализовывать событиеe в момент времени chi(e), а вместо этого отложить его на фиксированное lambda минут: chi(e^*) leftarrow chi(e^*) + lambda

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

Действие a=1 может быть нереализуемо, если chi(e^*) > min{ y(r'), r'=r(e) }, что указывает на то, что ни один из путей в ресурсе r' не доступен для приёма поезда t(e') в момент времени chi(e'). В этом случае моделирование завершается. Здесь  r'- это ресурсr(e), который будет занят событием e, когда событиеe произойдёт.

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

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

Предположим, что событие e - одно из следующих событий поезда t(e^*), тогда его перенесенное время chi(e) будет обновлено до самого раннего времени, когда оно могло произойти, что считается как chi(e^*) плюс самое короткое время, необходимое от события 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^*) },

где

  • e^* - текущее событие;

  • Delta(e^*)- задержка события e^*;

  • c(r_i)- уровень перегрузки ресурсаr_i, i in { 1, ..., n };

  • r(e^*)- ресурс, который будет занят поездом t(e^*), когда событие e^* произойдёт, r(e^*) in { r_1, ..., r_n };

  • tilde{Delta}(e^*)=Delta(e^*), если Delta(e^*) leq D, гдеD - наибольшая рассматриваемая задержка. Иначе, tilde{Delta}(e^*)=D.

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

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

  • c(r_s)=0, если все пути в r_s доступны;

  • c(r_s)=1, если один путь в r_s недоступен;

  • c(r_s)=2, если по крайней мере два пути в r_sнедоступны.

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

  • c(r_0)=0, если r_0 не занят ни одним поездом;

  • c(r_0)=1, если r_0 занят одним поездом;

  • c(r_0)=2, если r_0 занят по крайней мере двумя поездами.

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

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

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

Заключение

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

Автор: artur_temievich

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js