WNPR

2 MIT Engineers Use Math To Plot A Path For Boston's School Buses

Aug 2, 2017
Originally published on July 27, 2017 8:41 am

At MIT, bright young engineers are still asked to tackle devilish math problems on their way to a degree.

But officials at Boston Public Schools (BPS) are hoping they can turn their attention to the world outside. Like the problem the district faces each morning: how to get thousands of students to school using more than 600 buses without burning through too much money or learning time.

They’re counting on two young engineers from MIT, and a special algorithm, to make a difference where trained staff and experience can’t.

Arthur Delarue and Sebastien Martin are doctoral students. They developed “Quantum” with a faculty adviser, Dimitris Bertsimas. It looks like a simple piece of software — imagine Google Maps but for school buses. But it runs on powerful math.

Both men are French and studying operations research. “Basically, we try to make math useful,” says Delarue, just 21, of his field.

The ‘Traveling Salesman Problem’

The math in question begins with a 200-year-old conundrum. It’s called the “traveling salesman problem.” Simply put, the question is how to find the most efficient way to pass through a series of points on a map without doubling back.

It may sound simple, but for more than a century, the world’s best mathematical minds have contended with the problem.

Jordan Ellenberg, who teaches math at the University of Wisconsin, says it’s the number of possible routes that makes finding the best one so difficult.

“When I say ‘a lot,’ I mean ‘a lot, a lot, a lot’ — to use a technical term.”

Mathematical advancements and faster computers have made it a lot easier to find a single, nearly optimal route. But Ellenberg says assembling a school bus schedule is worlds more complicated.

“It’s not just one traveling salesman, it’s many buses going from place to place,” he says. “It just multiplies the possibilities you have to optimize over enormously.”

Enormously indeed. Martin calculates that there are literally trillions of ways Boston’s many bus routes could come together.

Factoring In Additional Problems

So it’s not enough to find the best route for each of the more than 200 given schools — district, charter and parochial.

“We have a second problem,” Martin says. “How to choose the solution for each school so that we have the best routes overall.”

Any computer program has to contend with the context, too. Some students need buses that accommodate wheelchairs, while others need home pickup. All of these problems get solved amid construction and Boston’s snarling traffic patterns.

The algorithm draws on adviser Bertsimas’ research to address the regular bottlenecks and the odd occasional delay of traffic.

Martin explains that, “First we take into account all the average traffic, and then we add some slack to make sure that even if things go wrong, we still have some time.”

So developing a master algorithm that comes up with a maximally efficient way to handle all those factors is a one-in-a-million math problem — something out of “Good Will Hunting.”

But Delarue and Martin won an open “transportation challege” BPS announced earlier this year because of how well their algorithm does just that.

John Hanlon, director of operations for BPS, says that in past years, his transportation staff has had to labor over each new set of bus routes, and they still faced half-empty buses, late arrivals and high costs.

Transportation costs BPS $110 million a year, as much per student as almost any other city in America. As the district tries to close a structural deficit, it’s the line item that looms largest.

So, Hanlon says, Quantum could represent a sea change in how routes are drawn and redrawn. “It takes a team of six to eight individuals about four weeks to complete the routing [each year],” Hanlon says. “The Quantum team solution can do all that in 30 minutes.”

Hanlon said he also hopes the process to the find the Quantum engineers represents a broader leap forward in government, “a new era” in which brilliant outsiders can help cities like Boston solve complex problems. The district estimates the program could help downsize the fleet by 50 buses next year, saving $3 million to $5 million.

But Quantum is still untested on the open road. Critics like Andre Francois, president of the bus drivers’ union, recall a moment earlier this decade when new routing software contributed to many buses running late.

Francois says that’s a flaw you’ll find in any maps that rely on machines.

“Machines don’t make routes. Humans make routes,” he says. “Machines send you to one-ways, dead-ends. These things never work!”

Francois adds that the city announced the changes “like a thief in the night,” and that he is willing to bet money that the program would result in more late buses in the fall, not fewer.

Delarue, however, defends the software and the district’s approach, saying BPS officials have reviewed their findings “so every single route will have been checked by people with years or even decades of experience.”

Delarue and Martin will stay on with the district to see how their software performs, but like us, they won’t find out whether Quantum passes or fails its test until the fall.

Copyright 2017 WBUR. To see more, visit WBUR.