Drawing bus routes for Boston Public Schools (BPS) involves challenges unique to the city. Since BPS allows parents to select their child’s school from a list of about ten options, some schools draw students from more than 20 different zip codes, resulting in bus routes that can be meandering and complicated, and the nation’s most expensive on a per-pupil basis at $2,000.
In 2017, BPS hosted the inaugural BPS’ Transportation Challenge where researchers could experiment with anonymized BPS data sets to create efficient routes and optimal start times for each school. The algorithms needed to account for several decision variables, 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. The solution also needed to address 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).
A team from MIT Operations Research Center won the competition, discovering that the best solution 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. The MIT team’s winning algorithm routes the entire system at once, providing a base for the human routers to tweak. Under the system-level approach, individual schools are independently routed, and those routes are then connected. 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 solution uses flexible integer programming that allows the district to adapt to changing policies.
- Previously, bus routing for BPS was an incredibly laborious process, one that took ten school system routers thousands of hours to create custom routes for each child and school. The algorithm was able to successfully create a system-level route map in just 30 minutes that was 20 percent more efficient than the ones done by hand.
- Running the algorithm allowed for the system to eliminate 50 buses, an 8 percent drop in the fleet that was the largest Boston had seen in a single year.
- Buses drove 1 million fewer miles during the 2017 school year and cut 20,000 pounds of carbon dioxide emissions per day.
- The algorithm resulted in $5 million in cost savings, which the district reinvested back into classroom initiatives.