Max Home IndustryАлгоритм оптимизации маршрутов школьных автобусов сэкономит Бостонским государственным школам целых 5 миллионов долларов после того, как эксперты по информатике и логистике приняли участие в трехмесячном хакатоне, который выиграла команда из Центра исследований операций Массачусетского технологического института. Задача была похожа на NP-сложную задачу коммивояжера.
Бостонские государственные школы (BPS) пригласили ученых и компьютерных специалистов, в том числе из Google, Microsoft, Uber, Гарварда и Массачусетского технологического института, чтобы принять участие в программе Transportation Challenge: Solving Routing и Bell Times, целью которой было снижение транспортных расходов и иметь возможность реинвестировать сэкономленные средства для улучшения впечатлений студентов.
Обозначение проблемы на сайте вызова:
В 2016 финансовом году транспортные расходы составили 110 миллионов долларов или 11% бюджета округа. В расчете на одного ученика транспортные расходы BPS занимают второе место и более чем в пять раз превышают средние показатели среди 200 крупнейших школьных округов. Между тем, транспортные расходы продолжали расти — на $ 33 млн по сравнению с 2011 финансовым годом, т.е. на 7,5% в год.
Конкурс состоял из двух частей. В первом раунде был разработан алгоритм, позволяющий сократить количество автобусных маршрутов, перенастроить автобусные остановки, максимально увеличить количество студентов, ездящих на каждом автобусе, и сократить время, в течение которого пустые автобусы находятся в пути. Также необходимо было принять во внимание, что некоторым студентам нужны автобусы, приспособленные для инвалидных колясок, а другим нужен самовывоз.
Эта задача является развитием задачи коммивояжера, сформулированной в 1930 году как поиск наилучшего маршрута между несколькими местами. Он известен как NP-сложный, то есть точное решение не может быть найдено за полиномиальное время. Вместо этого лучший маршрут можно найти с помощью методов оптимизации.
В настоящее время транспортный персонал BPS использует пакет программного обеспечения для построения маршрутов школьных автобусов, и этот процесс занимает несколько недель.
Алгоритм победы в 1-м раунде создает маршруты примерно за 30 минут. Он был разработан квантовой группой Массачусетского технологического института, в которую входили профессор Димитрис Берцимас, содиректор Центра исследований операций, и два аспиранта Артур Деларю и Себастьян Мартин. Они использовали данные из Google Maps для анализа моделей трафика в утренние и дневные часы пик, данные, предоставленные BPS об учащихся и назначенных им школах, а также программное обеспечение для картографии и методы оптимизации.
Ожидается, что новая модель маршрутизации улучшит своевременность движения автобусов BPS, обеспечивая более стабильную доставку учащихся в школу и обратно по расписанию. Ожидается, что расстояние, на которое студенты ходят до автобусных остановок и от них, в среднем не изменится. В некоторых случаях расположение автобусных остановок может немного измениться для одних студентов, а для других останется прежним. Команда Массачусетского технологического института приняла меры к тому, чтобы автобусные остановки не находились в местах с опасным движением транспорта.
Бертимас прокомментировал:
«Наше решение генерирует тысячи возможных маршрутов, а затем выбирает из триллионов перестановок оптимальный автобусный маршрут для соединения школ в течение дня. Создание такого количества перестановок вручную просто невозможно. В нашем алгоритме творчески сочетаются теория оптимизации, человеческая интуиция и вычислительные возможности »,
Получив приз в размере 15 тысяч долларов за раунд 1, команда MIT Quantum выиграла еще 15 тысяч долларов за второй раунд конкурса, который должен был найти оптимальное время звонка (то есть начало школьного дня) для 125 школ с учетом предпочтения среди трех вариантов: 07:30, 08:30 и 09:30.
По данным BPS, внедряющего решения Quantum Team, можно сэкономить до 5 миллионов долларов за счет сокращения 50 или более автобусных маршрутов и использования автобусов, курсирующих до трех разных школ каждое утро и день.
Не только школы получают выгоду, решение Quantum Team может привести к сокращению на 20 000 фунтов выбросов углерода, производимых автобусами BPS каждый день, и может ежегодно убирать с дороги почти 1 миллион миль пробок на автобусах.