The Boston Public School District held a contest to determine the best solution for busing around 25,000 students to school every day. The winning algorithm improved the efficiency of the routes in 30 minutes. From a report: In 2017, the district was facing serious challenges. On a per-pupil basis, Boston Public Schools had the highest transportation costs in the country, around $2,000 per student per year, representing 10% of the district's budget. The schools dealt with rising costs each year, despite declining ridership. The on-time performance rate of their buses was also well below that of other large districts. With no clear vendor to turn to with this problem, BPS instead sought out experts, hosting a competition where researchers could experiment with anonymized BPS data sets to create efficient routes and optimal start times for each school. "To put it simply, we wanted a solution that worked," said Will Eger, the BPS senior strategic projects manager. "There are lots of quirks in this transportation situation, and we wanted something that could address the vast majority of those issues while also being highly efficient, something that could run overnight at least." Those quirks represent millions of decision variables that affect any solution, including varying road widths, differing bus infrastructures (for example, the presence of wheelchair lifts or child safety restraint seats), students who require the same bus driver every year, students who have monitors, and students who have been in fights and, therefore, need to be on different buses. It also includes the roughly 5,000 students who have a special need that requires door-to-door pick up and drop off (sometimes to non-BPS schools, as the city provides yellow bus service to students who attend charter and private schools within Boston, and to special education facilities outside the city). Considering all those possibilities creates a "number of solutions so large that you can't even enumerate it," said Arthur Delarue, a PhD candidate who worked with the team from the MIT Operations Research Center whose algorithm won the competition. The team spent hundreds of hours devising a solution to what Delarue called a "bold and unusual" challenge. Their solution replaced what had before been an incredibly laborious process, one that took ten school system routers thousands of hours to create custom routes for each child and school. Those employees still work with BPS, tracking routes that struggle with on-time performance, and managing route guidance for drivers (Google Maps isn't sufficient since it's built for cars, and 70-passenger buses can't, for example, easily make u-turns). But now, the MIT algorithm routes the entire system at once, providing a base for the human routers to tweak.
Read more of this story at Slashdot.