Бостон заменил планировщиков маршрутов школьных автобусов алгоритмами — сэкономил $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 Operations Research Center. По словам одного из членов MIT кандидата наук Артура Деларю, команда потратила «сотни часов на разработку решения», а для учета всех вводных данных пришлось создать «такое количество вариантов (решения), что их невозможно перечислить».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0
98 комментариев
Написать комментарий...
Mike Espoo

Вот у людей то проблемы.
У нас вообще никаких школьных автобусов нет и это забота родителей как доехать до школы ребенку.

Ответить
Развернуть ветку
Sandrino Komaroff

Автобусы вам дай, может, вы еще и свобод каких потребуете? Обойдетесь, чай, не баре. Не жили богато - нехрен начинать

Ответить
Развернуть ветку
Вадим Моржик

Никаких свобод у амеров по сравнению с россиянами тупо нет

Ответить
Развернуть ветку
Sandrino Komaroff

Да что ты говоришь. Пригожину привет передай

Ответить
Развернуть ветку
Павел Андрейчук

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

Ответить
Развернуть ветку
Sandrino Komaroff

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

Ответить
Развернуть ветку
Павел Андрейчук

беспредел силовиков это ты про митинги что ли? Так почитай как митинги разгоняются в США и тебе сразу перехочется митинговать^^
Обвинительные приговоры... Давай по факту- сколько человек ни в чём не повинных сидит? Я не могу похвастаться широким кругом знакомых у которых проблемы с законом, однако у меня есть 3-е таких знакомых которые сидели в тюрьме, внезапно, но все трое на публику говорят что не виновны и им подбросили/подставили/нашли козла отпущения (нужное подчеркнуть). А по факту:
1-й реально барыжил наркотой
2-й реально отмывал деньги
3-й реально обносил квартиры

Ответить
Развернуть ветку
Steve Evets

Одно дело - что ваши "знакомые" про себя говорят. И совершенно другое - что говорят люди со стороны, свидетели, про действия незаконно задержанных.
Сравнили хрен с полицейской дубинкой

Ответить
Развернуть ветку
95 комментариев
Раскрывать всегда