Hi-Tech

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

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

В закладки

Аудио

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

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

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

В чем заключалась проблема

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

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

Автобусы Бостона Objective Subject

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

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

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

Поиск решения

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

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

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

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

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

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

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

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

Эффективность

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

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

Карта школ Бостона

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

В чем особенность алгоритма

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

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

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

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

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

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

Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть