How One City Saved $5 Million by Routing School Buses with an Algorithm

School buses line up in Boston, a city with one of the most challenging systems to route.

School buses line up in Boston, a city with one of the most challenging systems to route. Shutterstock

 

Connecting state and local government leaders

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.”

Emma Coleman is the assistant editor for Route Fifty. 

FEATURED CASE STUDIES
Powered By The Atlas
Orlando Protects Citizens During Heavy Rain Events by Optimizing Water Data Intelligence
Orlando, FL, USA
Small city of Baldwin, GA with <5K residents reduces info calls to City Hall by 50%
Baldwin, GA, USA
Integrated city systems, unified data, & automation drive 316% increase in field efficiency
Seattle, WA, USA

NEXT STORY: How Libraries are Embracing Artificial Intelligence

X
This website uses cookies to enhance user experience and to analyze performance and traffic on our website. We also share information about your use of our site with our social media, advertising and analytics partners. Learn More / Do Not Sell My Personal Information
Accept Cookies
X
Cookie Preferences Cookie List

Do Not Sell My Personal Information

When you visit our website, we store cookies on your browser to collect information. The information collected might relate to you, your preferences or your device, and is mostly used to make the site work as you expect it to and to provide a more personalized web experience. However, you can choose not to allow certain types of cookies, which may impact your experience of the site and the services we are able to offer. Click on the different category headings to find out more and change our default settings according to your preference. You cannot opt-out of our First Party Strictly Necessary Cookies as they are deployed in order to ensure the proper functioning of our website (such as prompting the cookie banner and remembering your settings, to log into your account, to redirect you when you log out, etc.). For more information about the First and Third Party Cookies used please follow this link.

Allow All Cookies

Manage Consent Preferences

Strictly Necessary Cookies - Always Active

We do not allow you to opt-out of our certain cookies, as they are necessary to ensure the proper functioning of our website (such as prompting our cookie banner and remembering your privacy choices) and/or to monitor site performance. These cookies are not used in a way that constitutes a “sale” of your data under the CCPA. You can set your browser to block or alert you about these cookies, but some parts of the site will not work as intended if you do so. You can usually find these settings in the Options or Preferences menu of your browser. Visit www.allaboutcookies.org to learn more.

Sale of Personal Data, Targeting & Social Media Cookies

Under the California Consumer Privacy Act, you have the right to opt-out of the sale of your personal information to third parties. These cookies collect information for analytics and to personalize your experience with targeted ads. You may exercise your right to opt out of the sale of personal information by using this toggle switch. If you opt out we will not be able to offer you personalised ads and will not hand over your personal information to any third parties. Additionally, you may contact our legal department for further clarification about your rights as a California consumer by using this Exercise My Rights link

If you have enabled privacy controls on your browser (such as a plugin), we have to take that as a valid request to opt-out. Therefore we would not be able to track your activity through the web. This may affect our ability to personalize ads according to your preferences.

Targeting cookies may be set through our site by our advertising partners. They may be used by those companies to build a profile of your interests and show you relevant adverts on other sites. They do not store directly personal information, but are based on uniquely identifying your browser and internet device. If you do not allow these cookies, you will experience less targeted advertising.

Social media cookies are set by a range of social media services that we have added to the site to enable you to share our content with your friends and networks. They are capable of tracking your browser across other sites and building up a profile of your interests. This may impact the content and messages you see on other websites you visit. If you do not allow these cookies you may not be able to use or see these sharing tools.

If you want to opt out of all of our lead reports and lists, please submit a privacy request at our Do Not Sell page.

Save Settings
Cookie Preferences Cookie List

Cookie List

A cookie is a small piece of data (text file) that a website – when visited by a user – asks your browser to store on your device in order to remember information about you, such as your language preference or login information. Those cookies are set by us and called first-party cookies. We also use third-party cookies – which are cookies from a domain different than the domain of the website you are visiting – for our advertising and marketing efforts. More specifically, we use cookies and other tracking technologies for the following purposes:

Strictly Necessary Cookies

We do not allow you to opt-out of our certain cookies, as they are necessary to ensure the proper functioning of our website (such as prompting our cookie banner and remembering your privacy choices) and/or to monitor site performance. These cookies are not used in a way that constitutes a “sale” of your data under the CCPA. You can set your browser to block or alert you about these cookies, but some parts of the site will not work as intended if you do so. You can usually find these settings in the Options or Preferences menu of your browser. Visit www.allaboutcookies.org to learn more.

Functional Cookies

We do not allow you to opt-out of our certain cookies, as they are necessary to ensure the proper functioning of our website (such as prompting our cookie banner and remembering your privacy choices) and/or to monitor site performance. These cookies are not used in a way that constitutes a “sale” of your data under the CCPA. You can set your browser to block or alert you about these cookies, but some parts of the site will not work as intended if you do so. You can usually find these settings in the Options or Preferences menu of your browser. Visit www.allaboutcookies.org to learn more.

Performance Cookies

We do not allow you to opt-out of our certain cookies, as they are necessary to ensure the proper functioning of our website (such as prompting our cookie banner and remembering your privacy choices) and/or to monitor site performance. These cookies are not used in a way that constitutes a “sale” of your data under the CCPA. You can set your browser to block or alert you about these cookies, but some parts of the site will not work as intended if you do so. You can usually find these settings in the Options or Preferences menu of your browser. Visit www.allaboutcookies.org to learn more.

Sale of Personal Data

We also use cookies to personalize your experience on our websites, including by determining the most relevant content and advertisements to show you, and to monitor site traffic and performance, so that we may improve our websites and your experience. You may opt out of our use of such cookies (and the associated “sale” of your Personal Information) by using this toggle switch. You will still see some advertising, regardless of your selection. Because we do not track you across different devices, browsers and GEMG properties, your selection will take effect only on this browser, this device and this website.

Social Media Cookies

We also use cookies to personalize your experience on our websites, including by determining the most relevant content and advertisements to show you, and to monitor site traffic and performance, so that we may improve our websites and your experience. You may opt out of our use of such cookies (and the associated “sale” of your Personal Information) by using this toggle switch. You will still see some advertising, regardless of your selection. Because we do not track you across different devices, browsers and GEMG properties, your selection will take effect only on this browser, this device and this website.

Targeting Cookies

We also use cookies to personalize your experience on our websites, including by determining the most relevant content and advertisements to show you, and to monitor site traffic and performance, so that we may improve our websites and your experience. You may opt out of our use of such cookies (and the associated “sale” of your Personal Information) by using this toggle switch. You will still see some advertising, regardless of your selection. Because we do not track you across different devices, browsers and GEMG properties, your selection will take effect only on this browser, this device and this website.