Slashdot Mirror
MIT Team's School-Bus Algorithm Could Save $5M and 1M Bus Miles (wsj.com)
An anonymous reader shares a report: 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 and 1 million bus miles (Editor's note: the link could be paywalled; alternative source). 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.
I certainly hope so otherwise the bus drivers won't be able to pay the whip and buggy makers they put out of work. And won't someone think of the poor farriers.
I think the math works out to over $20/day per student, given the numbers in the summary (assuming a school year == 180 days)...
Does anyone else think that's excessive? You'd be better off (by a lot) paying 1/3 of the parents $20/day to carpool two or three other students...
There are several different polynomial algorithms that produce solutions to a traveling salesman-like problem that are typically within around 20% of the ideal solution. I'll take a good enough answer over one that's perfect but won't be available until well after the heat death of the universe.
Not likely for several reasons. The first being they are saving overall miles. While this doesn't exclude the possibility of a longer ride it is not the most likely scenario. Secondly, buses do multiple routes which is why school starts are staggered. If bus rides are longer they wouldn't be able to meet this schedule.
Right. There are even polynomial-time approximation algorithms that guarantee to be within a fixed percentage of optimal. And don't forget that NP-complete doesn't mean it's impossible, only that it takes a long time as the problem size increases. For smaller problem sizes, solving the problem outright isn't impractical. In this case, they have a variation on the classic problem where there's a limit to the number of kids on each bus and a limit to how long (in time) each bus route can be. But if the stops are fixed and the school to which they have to deliver the kids is fixed, then it breaks down the problem to separate problems for each school, and solving each small NP-complete problem is entirely practical. If the destination school isn't fixed, then run an approximation algorithm on the whole thing, then use the school assignments from that algorithm and re-run using the full solution.
We would then have zero busses, teachers that are being paid closer to their value, safer public transportation and more full-time employment.
I wonder if the school district ever thought about talking to UPS and/or FedEx ...
They did, but the companies would only guarantee student delivery by 5pm w/o and extra charge and for FexEX if no one was outside to sign for them they'd leave a note and try again the next day -- UPS would just drop the student off behind a bush Also UPS wouldn't deliver anyone over 150 pounds.
It must have been something you assimilated. . . .
Where I live, more and more "grown-up" buses are going hybrid or natural-gas, much much kinder when you're stuck behind one in traffic.
But all the school buses are the same stamped-metal yellow tanks they've been using since the Korean War, blasting out as much diesel soot as a dump truck. When the school budget comes up, there's always a jaw-dropping-huge chunk set aside to fuel these horrid things.
Maybe as much could be saved by upgrading these monsters to something modern as eliminating routes and cramming more kids on the inside?
Hey, Elon Musk, Jeff Bezos, and college-debt-hounded MIT nerds... how about solving THIS problem on the back of a napkin!
Take it easy, Charlie, I've got an Angle...