Optimized school bus routing helps school districts design better policies

BPS promo

Boston Public Schools (BPS) is responsible for the education of over 54,000 mostly low-income and minority students. Boston’s narrow streets and traffic combined with the district’s generous levels of school choice, legally mandated transportation services for non-district schools, and other factors result in the country’s most expensive public school transportation system. Within this system, constructing and managing school bus schedules is complicated and time-intensive, typically requiring a team of 10 working overtime for two months. The result of that process, even when using the best bus routing systems available, was invariably an inefficient set of bus routes and unnecessary costs. 

To address this problem, BPS took the unusual step in April 2017 of hosting a “transportation challenge.” With support from Google, Microsoft, and private donors, BPS published a list of routing constraints and approximations of students’ addresses, and asked for a system of routes. The winning team from the MIT Operations Research Center proposed a creative algorithm that could route 25,000 students in 30 minutes, compared to 3,000 hours for human experts. Its solutions promised potential savings of up to 20 percent, and outperformed current state-of-the-art algorithms by 10 percent. 

BPS used this algorithm for the first time in the summer of 2017, resulting in a 7 percent reduction in the BPS bus fleet (50 buses), representing an estimated $5 million in annual transportation savings without increasing the average student’s home-to-stop walking distance or ride time. This was the single largest bus fleet reduction in BPS history – larger than when BPS shifted 8,000 7th and 8th graders from bus service to public transportation. The algorithm has now been implemented for two years running and continues to be improved as BPS and MIT work toward refining time performance and generating savings to reinvest into classrooms. 

In addition to creating more efficient bus operations, automated routing gave BPS the ability to evaluate the transportation costs of previously untested policy ideas, including shifting school locations, adjusting rider eligibility rules, or changing school start and end times. Like most other districts, BPS staggers the start and end times of different schools to allow buses to serve multiple schools during the day. Because of this, the system is so interconnected that small tweaks often have significant transportation implications. In 2016, a change to one school’s start time caused an unexpected cost increase of more than $1 million. Being able to understand the implications of proposed changes can help BPS and other districts avoid unintended costs by giving them the ability to easily run accurate simulations – something that to date, no school district transportation system can reliably do. 

Adjusting schools’ start times is a challenge for school districts across the country. A growing body of research has found that too-early school starts have been linked to teen health issues including obesity, depression, and traffic accidents. The American Academy of Pediatrics issued a public report calling for teenagers to start their school day after 8:30am, while a 2015 CDC report found that just 17.7 percent of U.S. high schools comply, a reality that could cost the U.S. economy more than $80 billion over the next decade. Yet an inability to quickly and easily run simulations to understand transportation implications from a new set of start times has hindered districts in finding and moving to an optimal set of bell times. 

Exploring adjustments to BPS’ current start and end times had vexed the BPS Transportation Department and multiple outside partners for years: no one, in academia or industry, had ever jointly solved school bus routing and bell time selection. However, working with BPS, the MIT team created an innovative optimization tool that could handle the task. Specifically, the tool could find and evaluate bell time assignments on the efficiency frontier of several criteria determined by community feedback. These new bell times ultimately did not become a reality for a number of reasons, but the effort showed the potential for using an algorithm to solve a seemingly intractable public policy dilemma.

Since developing these new operations research tools, the MIT team has contributed to a growing national conversation about school start times. In September 2018, they provided data for the Boston Globe’s top-trending interactive article “The Equity Machine,” which allowed readers to visualize the policy tradeoffs of different bell time scenarios. In solving a problem widely considered impossible, operations research has surged to the front of the national debate about school start times. Though bell times in Boston have not changed, the Boston School Committee approved a new policy that explicitly outlines quantifiable objectives that future bell time assignments should seek to optimize. Buoyed by media coverage (Wall Street Journal, NPR, The Boston Globe), the MIT team has been solicited by dozens of policymakers at the state and local levels, leading to the development of a new software system for school transportation and policy by Dynamic Ideas, a company started by Dimitris Bertsimas. Dynamic Ideas is currently in talks with almost 30 districts (and directly partnering with three) across 17 states to implement routing and/or bell time solutions. 

By producing innovative solutions to one of the field’s oldest and most difficult problems (vehicle routing) and one of its newest (start time selection), BPS and MIT have created a blueprint for the role of operations research in addressing complex and important public policy problems.