Can MIT Solve Your Fleet’s Next Problem?

A recent article in the Wall Street Journal by Jo Craven McGinty caught our attention. Here’s what the story told us: The Boston Public School system held a contest to design a more efficient way to operate its school bus fleet and save money in the process.

Sounds good, right?

The stakes are high. As the Journal reported, approximately 30,000 students rode 650 buses to 230 schools last year at a cost of $120 million. The prize to streamline and improve the system: $15,000. OK, more about that later.

Topping the competition were Dimitris Bertsimas, co-director of MIT’s Operations Research Center and doctoral students Arthur Delarue and Sebastien Martin. Together, the MIT team build an algorithm that eliminates up to 75 bus routes. What’s more, the plan, will eliminate some bus-driver jobs and “could save up to $5 million, 20,000 pounds of carbon emissions and 1 million bus miles.”

That’s not exactly child’s play.

As the article’s author noted: “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.”

So what’s the best approach? Simple: Plot the best overall path. OK, but there could be an almost infinite number of options — unless you’re a logistics expert or a math whiz.

Assuming the distance between any two points is the same in both directions, a five-city tour has a dozen possible routes.

Enter the power of algorithms. They’re fast.

As the reporter noted: “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 up: Determining whether the plan works. That’s where the rubber meets the road. Literally.

Drivers are expected to try out the routes the week before school starts. Then, it’s showtime.

Category: Featured, News