OM in the News: Using OM to Fix School Bus Routes

Last year, more than 30,000 students in the Boston Public Schools rode 650 buses to 230 schools at a cost of $120 million. In hopes of spending less this year, the school system offered $15,000 in prize money in a contest that challenged competitors to reduce the number of buses. The winner, reports The Wall Street Journal (Aug. 12-13, 2017), was MIT’s Operations Research Center, which devised an algorithm that drops as many as 75 bus routes.

The school system says the plan, which will eliminate some bus-driver jobs, could save up to $5 million, 20,000 pounds of carbon emissions a day and 1 million bus miles each year. The computerized algorithm runs in about 30 minutes and replaces a manual system that in the past has taken transportation staff several weeks to complete. “They have been doing it manually many years,” said the MIT Center co-director. “Our whole running time is in minutes. If things change, we can re-optimize.”

The task of plotting school-bus routes resembles the classic exercise known as the Traveling Salesman Problem (TSP), where the goal is to find the shortest path through a series of cities, visiting each only once, before returning home. Although we don’t cover TSP in the written text, we do so in our MyOMLab Tutorial called Vehicle Scheduling & Routing.

Classroom discussion questions:

1. Provide other applications of TSP.
2. How does this scheduling problem differ from that of airlines scheduling planes and crew?