Jo Craven McGinty
A trio of MIT researchers recently tackled a tricky vehicle-routing problem when they set out to improve the efficiency of the Boston Public Schools bus system.
Last year, more than 30,000 students 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 winners—Dimitris Bertsimas, co-director of MIT’s Operations Research Center and doctoral students Arthur Delarue and Sebastien Martin—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,” Dr. Bertsimas said. “Our whole running time is in minutes. If things change, we can re-optimize.”
The task of plotting school-bus routes resembles the classic math exercise known as the Traveling Salesman Problem, where the goal is to find the shortest path through a series of cities, visiting each only once, before returning home.
Intuitively, traveling to the closest destination first and then the next closest after that until the tour ends would seem to guarantee the most efficient route.
But in practice, the nearest-neighbor solution rarely produces the shortest route. In one 42-city example that starts in Phoenix, following the nearest-neighbor approach leads to the Pacific Northwest, but other locations remain on the East Coast, forcing the “salesman” to travel 45% farther than the most efficient route.
The trick, then, is to figure out the best overall path. Sifting through the number of options, which can be astronomical, is daunting.
Assuming the distance between any two points is the same in both directions, a five-city tour has a dozen possible routes.
A 10-city tour has 181,440 possible routes. And a 50-city tour has more than 304 novemdecillion options. (Add 60 zeros to see what that looks like.)
Some previous columns
- Losing Your Old Area Code? You’re Not Alone
- Dollar’s Gyrations Are No Cause for Alarm
- Pollsters Survey What’s Wrong With the Polls
“Every example is solvable but not in a practical amount of time,” said William J. Cook, a mathematician at the University of Waterloo and author of “In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation.”
One of the largest routes Dr. Cook has optimized stopped at 49,603 historic sites in the U.S. “It took 178.9 computing years to solve, running on a 310-processor computing cluster from March through November 2016,” he said.
Algorithms help speed up the work. An iPhone app Dr. Cook helped develop can calculate the optimal route for a 50-city tour in seconds.
But the Boston Public Schools conundrum was more complex than the basic Traveling Salesman Problem.
The MIT researchers had to optimize multiple routes that accounted for traffic, different-size buses, students with special needs such as wheelchair access, and staggered school days that start at 7:30 a.m., 8:30 a.m. or 9:30 a.m.
They first paired clusters of students with bus stops. Then, using Google Maps travel times to account for traffic volume, they connected the bus stops into six to eight efficient route solutions for each school.
“Next, we combined one solution from one school to another school and to another school to optimize the overall system,” Dr. Bertsimas said.
Individual students may be on a bus for more or less time than last year, but in keeping with school-system rules, no bus trip should last more than one hour, Mr. Delarue said.
Whether the plan will work as predicted remains to be seen. A previous effort to automate the system failed in 2011 when buses following routes created with software ran perpetually late.
To avert similar problems this year, the school system’s transportation staff vetted the MIT’s computer-generated routes, making tweaks as needed.
“We wanted to make sure we were not picking up students on small streets with big buses,” said John Hanlon, chief of operations for Boston Public Schools, noting one adjustment his staff has made. “That’s not something the algorithm would have known to do.”
Drivers will try out the routes the week before school starts. But the real test will occur on Sept. 7—the first day of school—when everyone will find out how efficiently the wheels on the buses go round and round.
Write to Jo Craven McGinty at Jo.McGinty@wsj.com