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

Вы когда-нибудь жаловались на опоздания или слишком редкие поезда? Теперь у вас есть шанс улучшить ситуацию!

Ежедневно по швейцарской железнодорожной сети в более чем 10 000 поездов перевозится более 1,2 миллиона человек с лучшей в мире пунктуальностью.

Но ожидается, что трафик будет расти еще больше. По мере добавления новых поездов сложность планирования быстро возрастает.

Ваша цель - придумать оригинальные способы решения этой проблемы. Сможете найти подходящий алгоритм? Мощная эвристика? Перспективный AI-подход?

Давайте начнем!

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

Вы можете найти полную документацию в Стартовом наборе. Там много информации, но не пугайтесь! Мы начнем с интуитивного объяснения проблемы, выявим требования и покажем, как отправить первую простую заявку.

Поезда и рельсы

Каждая задача имеет 4 входа:

  • железнодорожная система,
  • список поездов, которые по нему курсируют,
  • временные ограничения, например, «этот поезд должен прибыть в это место к этому времени»,
  • ограничения ресурсов, например, «только один из этих разделов может использоваться одновременно».

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

Isn’t this backward?
It may be surprising to try to schedule trains while already having timing constraints. This is because we are considering cases where we want to make small modifications to a pre-existing schedule. 
For example if a major football match starts at 20:00, it would make sense to modify the usual schedule to have a train arrive close to the stadium no later than 19:00. Similarly, the departure of the train that brings the spectators back should have an earliest departure of maybe 22:30.

Железнодорожная сеть

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

Мы предполагаем, что каждый участок можно пересечь только в одном направлении. Мы также предполагаем, что в сети нет петель. Таким образом, результирующий граф представляет собой ориентированный ациклический граф (DAG).

Требования

Поезда подчиняются различным требованиям по времени:

  • Самое раннее / самое позднее время прибытия, самое раннее / самое позднее время отправления и минимальное время остановки, которые позволяют пассажирам садиться в поезд и выходить из него.
  • Соединения с другими поездами, что означает, что два поезда должны координироваться, чтобы пассажиры могли переходить от одного к другому.

Простой сценарий

Рассмотрим пример проблемы: sample_scenario.json.

Он содержит два служебных намерения, что является причудливым названием для «поезд, включая все его требования»:

The JSON files describing the problems get very large. An extension such as JSONView can help you understand the simpler files. Beyond that a good way to visualise them is as tables: the one above was rendered using http://json2table.com/.

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

Durations are expressed per ISO_8601 standard. The “P” in "PT3M" is the duration designator, which stands for period. The "T" stands for time, and "M" for minutes.

Пока все просто! Давайте посмотрим на первый маршрут.

На самом деле это простой маршрут, но представление графика в виде структуры JSON делает его громоздким.

Итак, это маршрут 111, по которому ходит наш первый поезд. Каждый из пяти путей маршрута представляет собой последовательность участков, следующих друг за другом. Например, вы можете пройти по участкам первого и самого длинного пути маршрута, обозначенным 1, 4, 5, 6, 10, 13 и 14.

Затем другие пути маршрута «приклеиваются» поверх этого первого с использованием route_alternative_marker_at_entry и route_alternative_marker_at_exit в качестве ориентиров. Например, второй путь добавляет одну секцию, которая заканчивается маркером M1, а четвертый путь добавляет 3 секции, которые разветвляются от M2 и достигают другого конца.

Красные метки показывают маркеры разделов, которые есть на некоторых разделах. Это маркеры, указанные в требованиях к разделу каждого поезда. (Маркер показан прикрепленным к концу раздела, к которому он относится.)

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

Некоторые маркеры являются общими для двух маршрутов. Мы бы позаботились о них, если бы у нас было железнодорожное сообщение, которое нужно обработать, поскольку они имели бы форму «этот поезд должен встретить этот поезд на этом маркере». Но в данном случае у нас нет связей.

Что нас действительно заботит - это ресурсы, общие для этих маршрутов, показанные ниже в красных кружках (опять же, ресурсы показаны прикрепленными к концу разделы, к которым они относятся):

Теперь очевидно, что эти маршруты тесно связаны друг с другом. Фактически в «реальном мире» эти треки проходят рядом друг с другом.

Ресурсы - это «блокировки», которые предотвращают одновременное использование групп разделов. Каждому ресурсу также требуется некоторое время выпуска: количество времени, которое должно пройти между их выпуском одним поездом и следующим занятием следующим поездом.

Теперь, когда у нас есть интуитивное представление о том, как выглядят основные маршруты, давайте рассмотрим менее тривиальную задачу: 01_dummy.json.

Мы видим, что во многих случаях ресурс используется последовательными секциями и разделяется соседними маршрутами. Это соответствует тому факту, что поездам обычно нужна волна из нескольких «зеленых сигналов» перед ними.

Эти графики - реальные образцы из швейцарской сети!

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

В приведенном выше случае мы можем узнать пути между городами Цюрих, Цуг и Пфеффикон.

Реализация собственного решения

Для реализации конкретного решения следуйте этому документу, который поможет вам решить sample_scenario.json проблему вручную.

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

Чтобы отправить заявку, не обязательно иметь решения для всех проблем.
Вы будете наказаны за пропущенные решения, но вы все равно можете проверить правильность своей работы на данный момент. Прочтите здесь, чтобы узнать, как подать заявку.

Как мне подойти к проблеме?

Есть много способов решить эту проблему программно. Мы не хотим описывать их подробно, так как наша цель - предлагать новые инновационные решения!

Один намек: возможной отправной точкой было бы выражение проблемы в виде задачи смешанного целочисленного программирования (MILP).

И последнее, но не менее важное: не существует известного решения проблемы 9, которое не привело бы к задержкам. Вероятно, такое решение существует, но решатель, используемый SBB, пока не смог его найти.

Итак, если вы ДЕЙСТВИТЕЛЬНО найдете такое решение, вы значительно повысите эффективность планирования поездов в Швейцарии! 😎

Challenge Links
Challenge page: https://www.crowdai.org/challenges/train-schedule-optimisation-challenge
Starter kit: https://gitlab.crowdai.org/SBB/train-schedule-optimisation-challenge-starter-kit/
Gitter channel: https://gitter.im/crowdAI/sbb-challenges