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.
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.
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. . . .