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.
$120M / 650 buses = $185k per bus+driver per year.
Those buses sit idle most of the day. They need fuel, maintenance, insurance, and registration; and they depreciate. The analysts may also have calculated in the cost of parking (including the amortized cost of the land which is expensive in Boston), loan servicing (interest), and the opportunity cost of capital (the money tied up in the buses).
Any sufficiently unpopular but cohesive argument is indistinguishable from trolling.