Мы не устаем восхищаться прогрессом компьютерных технологий. При этом математика достигла гораздо большего прогресса, и никто даже не заметил! Многогранники, плоскости, двойственные задачи и разветвления зашиты в программных пакетах и решают задачи планирования, как будто так было всегда и в этом нет ничего особенного.
Конечно, самое поразительное – совместный эффект математики и компьютеров. Ускорение в 4 миллиарда раз. Задачи, на которые требовалось 126 лет в 1991 году, в 2012-м мы научились решать за одну секунду! И это не предел. В статье 2015 года Димитрис Бертсимас и Анжела Кинг из Массачусетского технологического института приводят новую цифру – 450 миллиардов – и предлагают новые приложения линейного программирования в статистике.
При столь невероятной эффективности для линейного программирования открываются новые горизонты, немыслимые ранее, но вполне реальные сегодня.
Расписание движения поездов на голландских железных дорогах
Самая престижная награда в исследовании операций – премия Франца Эдельмана за выдающиеся успехи науки в приложениях. В 2008 году ее получили Железные дороги Нидерландов за новое железнодорожное расписание, которое начало действовать в 2006 году.
Нидерланды – маленькая, но густонаселенная страна. На территории размером примерно с Нижегородскую область проживает около 17 миллионов человек. Железные дороги – основа всей голландской логистики. Многие каждый день ездят на поезде на работу. Совещание в другом конце страны – обычное дело. Голландцы – чемпионы Европы по пассажирским железнодорожным перевозкам. В 2006 году Железные дороги Нидерландов перевезли 15,8 миллиарда пассажиров.
До 2006 года действовало расписание, составленное в 1970 году. Перевозки увеличивались, составы постепенно удлинялись, а где возможно, добавлялись новые поезда. Пока наконец к началу 2000-х увеличивать перевозки в рамках старого расписания стало невозможно. Прокладывать новые пути фактически тоже невозможно из-за их безумной дороговизны, да и просто нехватки земли. Железнодорожные пути в Нидерландах строились и расширялись очень мало еще со времен Второй мировой войны. Задача, которая встала перед менеджментом железных дорог, – обеспечить требуемый объем перевозок при имеющейся инфраструктуре. Как это сделать? В 2002 году было решено составить новое расписание.
Расписание железных дорог – дело очень сложное. Нужно, чтобы два поезда одновременно не претендовали на один и тот же участок рельсов. Маршруты с пересадками тоже должны быть удобными, без получасового ожидания на платформе. Кроме того, нужно распределить пути прибытия и отправления на каждой станции, определить количество и тип вагонов для каждого состава, составить расписание кондукторов и машинистов. И все это для 5500 поездов в день!
Над задачей работала целая команда математиков. Основные сложности и идеи они описали в статье{4}, за которую им была присуждена премия Эдельмана.
Каждый этап составления расписания требовал новой модели и новых подходов. Некоторые задачи, например распределение путей прибытия и отправления, после нескольких шагов предварительной подготовки удалось решить с помощью пакета CPLEX. Задача расписания движения поездов упрощалась благодаря цикличности: поезда отправляются в одно и то же время каждый час. Но даже в этом случае коммерческие пакеты оказались бессильны. Справиться с задачей помогли новые математические идеи. Внедрение не сразу прошло гладко. И все же теперь больше поездов перевозит больше людей по тем же рельсам. Пассажиропоток увеличивается, но расписание по-прежнему справляется. В рамках старого расписания это было бы невозможно.
Что такое оптимальное решение
Если вы недавно посещали Нидерланды, то последний раздел вас мог удивить. Железнодорожное движение далеко от совершенства. Мелкие (и крупные) задержки случаются сплошь и рядом. Пересадки порой очень короткие, их легко пропустить при малейшем опоздании. Поезда часто переполнены, особенно вагоны наиболее популярного 2-го класса. Далеко не все обрадовались новому расписанию. Влиятельная голландская газета NRC Handelsblad писала:
Это единственная форма высшей математики, которая вызвала в обществе такую бурю эмоций.
Александр Схрейвер, знаменитый голландский математик, один из лучших в мире специалистов по оптимизации, играл ведущую роль в составлении нового расписания. Критика журналистов его не очень взволновала. В одной из статей, рассчитанной на широкую публику, он пишет:
4
Kroon Leo, Huisman Dennis, Abbink Erwin, Fioole Pieter-Jan, Fischetti Matteo, Maroti Gabor, Schrijver Alexander, Steenbeek Adri and Ybema Roelof. The new dutch timetable: The or revolution // Interfaces, 39(1):6–17, 2009.