Creating better bus routes with algorithms

Come September, hundreds of Boston Public School students will ride new bus routes thanks to experts at MIT.

The “Quantum Team” from the MIT Operations Research Center won the inaugural Boston Public Schools’ Transportation Challenge, a competition intended to generate ideas to help the school system streamline routes, reduce emissions, and save money through a hackathon-style competition.

Professor Dimitris Bertsimas, co-director of the Operations Research Center, led the winning team, along with PhD students Arthur Delarue and Sébastien Martin. Bertsimas says that this is a prime example of optimization being deployed to streamline costs.

“The Boston Public Schools use 650 buses of various sizes, costing $120 million — 12 percent of their funds — per year,” says Bertsimas, whose team won $15,000 in the competition. Private funders contributed the prize money.

Approximately 50 superfluous routes could be eliminated using the new method, saving the school district between $3 million and $5 million annually. According to a release, BPS transportation staff currently build school bus routes manually, using pupil transportation software — a multi-week process. MIT’s solution devises routes in approximately 30 minutes.

Bertsimas and his team gleaned data from Google Maps to analyze traffic patterns during morning and afternoon rush hours. Combining that with data provided by the Boston Public Schools on students and their assigned schools, they used mapping software and optimization techniques to devised an algorithm that would reduce the number of bus routes, reconfigure bus stops, maximize the number of students riding each bus, and cut the amount of time that empty buses are on the road. They also had to take into account that some students require wheelchair-friendly buses and others need home pickup.

“This speaks to the power of optimization and large data sets,”  he says.

Since the win, at least four school districts have contacted Bertsimas with similar transportation woes, he says.

“This solution can be applied anywhere,” he says.