Как математика помогла составить расписание 5500 поездов в Голландии. И не только

Профессор математики и мать двух дочерей Нелли Литвак вместе с преподавателем МФТИ и сотрудником «Яндекса» Андреем Райгородским написали книгу «Кому нужна математика?», которая вышла в издательстве МИФ. В книге понятно и просто объясняется, как математика помогает нам в реальной жизни. Мы публикуем отрывок из второй главы «Менеджмент и многогранники».

Расписание движения поездов на голландских железных дорогах

Самая престижная награда в исследовании операций — премия Франца Эдельмана за выдающиеся успехи науки в приложениях. В 2008 году её получили Железные дороги Нидерландов за новое железнодорожное расписание, которое начало действовать в 2006 году.

Нидерланды — маленькая, но густонаселённая страна. На территории размером примерно с Нижегородскую область проживает около 17 миллионов человек. Железные дороги — основа всей голландской логистики. Многие каждый день ездят на поезде на работу. Совещание в другом конце страны — обычное дело. Голландцы — чемпионы Европы по пассажирским железнодорожным перевозкам. В 2006 году Железные дороги Нидерландов перевезли 15,8 миллиарда пассажиров.

До 2006 года действовало расписание, составленное в 1970 году. Перевозки увеличивались, составы постепенно удлинялись, а где возможно, добавлялись новые поезда. Пока наконец к началу 2000-х увеличивать перевозки в рамках старого расписания стало невозможно. Прокладывать новые пути фактически тоже не возможно из-за их безумной дороговизны, да и просто нехватки земли. Железнодорожные пути в Нидерландах строились и расширялись очень мало ещё со времён Второй мировой войны.

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

Как это сделать? В 2002 году было решено составить новое расписание.

Расписание железных дорог — дело очень сложное. Нужно, чтобы два поезда одновременно не претендовали на один и тот же участок рельсов. Маршруты с пересадками тоже должны быть удобными, без получасового ожидания на платформе. Кроме того, нужно распределить пути прибытия и отправления на каждой станции, определить количество и тип вагонов для каждого состава, составить расписание кондукторов и машинистов. И всё это для 5500 поездов в день!

Над задачей работала целая команда математиков. Каждый этап составления расписания требовал новой модели и новых подходов. Некоторые задачи, например распределение путей прибытия и отправления, после нескольких шагов предварительной подготовки удалось решить с помощью пакета CPLEX. Задача расписания движения поездов упрощалась благодаря цикличности: поезда отправляются в одно и то же время каждый час. Но даже в этом случае коммерческие пакеты оказались бессильны. Справиться с задачей помогли новые математические идеи. Внедрение не сразу прошло гладко. И всё же теперь больше поездов перевозит больше людей по тем же рельсам. Пассажиропоток увеличивается, но расписание по-прежнему справляется. В рамках старого расписания это было бы невозможно.

Что такое оптимальное решение

Если вы недавно посещали Нидерланды, то последний раздел вас мог удивить. Железнодорожное движение далеко от совершенства. Мелкие (и крупные) задержки случаются сплошь и рядом. Пересадки порой очень короткие, их легко пропустить при малейшем опоздании. Поезда часто переполнены, особенно вагоны наиболее популярного второго класса. Далеко не все обрадовались новому расписанию. Влиятельная голландская газета NRC Handelsblad писала:

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

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

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