Бостон заменил планировщиков маршрутов школьных автобусов алгоритмами — сэкономил $5 млн, сократил автопарк и выбросы

Алгоритм за 30 минут работы смог повысить эффективность маршрутов на 20% по сравнению с тысячами часов работы специалистов.

Издание Route Fifty рассказало о том, как Бостон столкнулся с высокими расходами на школьный транспорт из-за сложных и извилистых маршрутов, искал специалистов по обработке данных и смог за одно лето исправить ситуацию.

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

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

Школьный округ Бостона (BPS, Boston Public Schools District) позволяет родителям выбирать школу для ребёнка по списку из десяти позиций, пытаясь сгладить неравенство, которое может проявиться, когда ученики ограничены собственным районом.

Всем школьникам начальных классов, кто выбрал школу больше, чем в миле (1,6 км) от дома, предоставляется автобус до 220 школ, но многие учреждения расположены гораздо дальше — в некоторых школах учатся дети из «20 различных почтовых индексов».

Начало занятий может различаться от 7:15 до 9:30 утра, поэтому рейсы автобусов проходят через несколько школ с учетом расписания, чтобы вовремя высаживать и забирать детей.

В 2017 году округ столкнулся с проблемами: в расчете на одного учащегося у BPS самые большие транспортные расходы в США — около $2000 в год, в сумме эти траты составляли около 10% всего бюджета округа. Расходы постоянно росли, а качество работы автобусного парка было значительно ниже, чем в других крупных районах.

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

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

По словам старшего менеджера по стратегическим проектам BPS Уилла Эгера, округ хотел рабочее решение, которое одновременно и быстро работало, и позволило бы решить большинство проблем с логистикой.

Для этого нужно было учитывать миллионы переменных, которые влияют на выбор маршрута, например, ширину дорог, инфраструктуру, возможности автобусов (наличие подъемников для инвалидных колясок или детских сидений), желание детей, чтобы их каждый год обслуживал один и тот же водитель автобуса, драчунов, которых нужно было рассаживать по разным автобусам.

Также у Бостона было около пяти тысяч учащихся с особыми потребностями — школьников нужно было сопровождать от двери до двери, в том числе, если школа не принадлежала BPS.

Победителем конкурса стала команда исследовательского центра MIT Operations Research Center. По словам одного из членов MIT кандидата наук Артура Деларю, команда потратила «сотни часов на разработку решения», а для учета всех вводных данных пришлось создать «такое количество вариантов (решения), что их невозможно перечислить».

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

Теперь составители отслеживают маршруты с задержками, собирают пожелания от заинтересованных сторон (директора школ, ученики, родители, водители) и помогают ориентироваться водителям. «Google Карт» в таком случае недостаточно, потому что сервис оптимизирован под легковые машины и не учитывает габариты автобусов, например, при разворотах.

Алгоритм MIT управляет всей системой маршрутов, предоставляя базу для более тонкой настройки проектировщиками и внесения изменений.

Бостон протестировал новую систему маршрутов в 2017-2018 учебном году: за 30 минут алгоритм смог создать маршрутную карту на 20% более эффективную, чем разработанная вручную, и чем дольше он работает, тем лучше результат.

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

Запуск алгоритма летом 2017 года позволил сократить парк на 50 автобусов (8% от всего парка) — это самое большое сокращение за один год. Автобусы проехали на 1,6 млн километров меньше, чем в 2016 году, а выброс углекислого газа сократился на 20 тысяч фунтов в день. Округ сэкономил $5 млн и реинвестировал их в другие школьные инициативы.

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

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

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

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

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

#алгоритмы #оптимизация