How One City Saved $5 Million by Routing School Buses with an Algorithm – By Emma Coleman (Next Gov) / Aug 13 2019
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.
The yellow school bus has remained largely unchanged since it first debuted in 1939. But while the buses look the same, their routes have grown infinitely more complex in the past 80 years, as the number of students, schools, and road systems grow and change.
Drawing bus routes for Boston Public Schools involves challenges unique to the city. BPS allows parents to select their child’s school from a list of about ten options, in an effort to reduce inequalities that might result from isolating students to their neighborhoods. While this represents a greater level of choice than most cities, the resulting bus routes can be meandering and complicated.
Compounding that challenge is the fact that BPS provides more bus services than most other districts. All elementary school students who attend schools more than a mile from their home are offered yellow bus service to one of over 220 schools, and many live much farther than that. Some schools draw students from more than 20 different zip codes. Each of those schools also had different start times, between 7:15 and 9:30 a.m., so buses might have to visit multiple schools for pick up and drop off.
In 2017, the district was facing serious challenges. On a per-pupil basis, BPS 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.
“The work of route managers in communicating with stakeholders such as drivers, principals, parents, and students is invaluable and cannot be replaced,” Delarue said. “But in what order stops should be visited, and how that route gets designed can’t be solved efficiently by humans. That’s where we add value.”
Sebastien Martin, another PhD candidate at MIT who worked on the solution, said the dilemmas with drawing school bus routes have been studied since the 1960s, and many solutions have been proposed. “Each school district has such different needs, though, so it’s hard to find a solution that works perfectly everywhere,” he said. “The problem is so hard to solve that even the most powerful computers can’t find a perfect solution for a district the size of Boston. There will always be tradeoffs.”
But even with tradeoffs, using an algorithm, which the city tested for the first time in the 2017-2018 school year, has created dramatic results. In 30 minutes, the algorithm created a system-level route map that was 20% more efficient than the ones done by hand. The longer the algorithm runs, the better solution it produces, until it cannot be improved. Running the algorithm in the summer of 2017 allowed for the system to eliminate 50 buses, an 8% drop in the fleet that was the largest Boston had seen in a single year. Buses drove 1 million fewer miles that year and cut 20,000 pounds of carbon dioxide emissions per day. The district reinvested the $5 million saved back into classroom initiatives.
“Incredibly, this was done without making bus rides or walk time to stops longer,” said Eger. “We now have shorter walk times for younger students and those in dangerous neighborhoods, and we still minimized the total number of stops.”
Much of the algorithm’s success is derived from the fact that it takes a system-level approach, instead independently routing individual schools and then connecting those routes together. Instead, the algorithm assigns students to stops, puts the stops in order to make no student’s ride longer than an hour, and then takes a multi-school routing approach. The best solution, then, is not the one that uses the fewest number of buses for each school, but the one that most effectively recycles buses on paths to multiple schools—and the solution uses flexible integer programming that allows the district to adapt to changing policies.
Now in its third year of operation, Eger said that BPS runs the algorithm in the summer to create a master schedule, and then makes modifications by hand throughout the year, though they’re trying to integrate the two systems so that changes can be done by the algorithm throughout the year. But the more powerful potential to come out of the challenge, in his opinion, was another algorithm, one that allows for “unprecedented insight” into the implications of policy changes, such as school start times.
“This was really eye opening for us,” said Eger. “We can understand now the cost and equity effects, and number of students who might be impacted by any given policy changes.”
But just because the district has been able to clearly enumerate the effects of policy changes doesn’t mean they’ve been popular. In December 2017, based on the recommendations of the algorithm, the Boston School Committee approved changes in school start times for the first time in 30 years. Those changes would have involved 85% of schools.
The move was based on several considerations, including research that showed starting high school before 8 a.m. has detrimental effects on the learning ability of teenagers. MIT research also showed that Boston was inequitable—while most parents prefer start times between 8:00 and 8:30 a.m., only 10% of white students in Boston start before 8:00 a.m., compared to 30% of black students. Higher income students generally start later, at the more desirable times.
So the team worked to swap the start times of high schools with elementary schools in the district, and optimize the start times based on route feasibility, teen health, parent preferences, and equity. Their school start time algorithm explored the tradeoffs to different start times, and found a balance point between all considerations. If it had been deployed, it would have changed the number of teenagers with early high school start times from 74% to just 6%.
But it wasn’t deployed. After it was unveiled, parents loudly objected to the proposal. Less than a month later, the district repealed the proposed new school start times. As Dimitris Bertsimas, a professor who led the MIT team, pointed out in a presentation about the solution, those who favored the status quo had the most to lose. “When your kids are affected negatively, it is hard to see the big picture,” he said.
MIT eventually partnered with the Boston Globe in 2018 to show how the time algorithm could alter the start times at individual schools, but sweeping changes have still not occurred. Even so, Eger said that the project has been inspiring for the district, and the city as a whole.
“This is a positive example to show how we can use some of the unbelievable research potential that Boston has the offer,” he said. “Many school districts have operational problems like this, and handling these complex challenges is not our line of expertise. We should rely on experts for that, and focus on the work we do best.”
