В 2017-ом Бостонский школьный округ тратил по $2000 в год на перевозку одного ученика на автобусе от дома до школы, что при их численности около 25 000 человек выливалось в 10 % от всего бюджета района. В США еще с 60-х годов пытаются (но пока не могут) решить задачу построения оптимальной схемы перевозки школьников. В каждом округе свои условия, а для такого крупного, как Бостон, один только подсчет количества возможных решений потребует применения суперкомпьютера. Поэтому ученым из MIT поручили найти нестандартное решение.
В округе 220 школ и каждая семья может выбирать из 10 ближайших, куда их детей нужно отвезти, причем в разных школах разное время начала занятий — от 7:15 до 9:30. Есть 5000 инвалидов, посадка-высадка которых требует особых условий и времени. Первоклашек должен возить один и тот же водитель, знакомый им человек, а старшеклассников приходится разделять во избежание разных конфликтов. Огромный автобус на 70 мест может проехать и развернуться далеко не везде – стандартная навигация по Google Maps здесь не всегда применима.
Команду по поиску решения возглавил кандидат наук Артур Деларю. Ученые потратили сотни часов только для уточнения множества переменных, которые следовало учесть при разработке алгоритма. И пришли к выводу, что нет смысла менять то, как работают сами автобусы и школы – нужно менять график посещения машинами остановок. За основу взяли аргумент, что каждый школьник не должен тратить на дорогу более 1 часа.
Когда алгоритм запустили в 2018-ом в пробном режиме, компьютер за 30 минут составил схему маршрутов на 20 % короче прежней. По мере совершенствования системы за год с маршрутов убрали 50 автобусов. В текущем году остальные машины проехали на 1,5 млн км меньше прошлогоднего показателя, а это экономия на топливе и снижение выбросов в атмосферу на 10 тонн в день. Всего же благодаря новой схеме организации движения школьных автобусов Бостонский округ сэкономил за год 5 миллионов
Источник
