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

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

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

-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 для решения задачи. Описанный метод был протестирован на части голландских железных дорог. Результаты показывают, что метод позволил найти качественное решение по перепланированию в рамках ограниченного количества обучающих эпизодов. Ссылка на статью с более подробным описанием подхода и результатов применения.