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.
As a parent, though, who's son rode the bus for 3 years, my first question would be if this will lengthen bus rides? (A 4% reduction in cost for a 20% increase in ride times would be a definite non-starter in my book.)
No, I didn't RTFA.
"I don't know, therefore Aliens" Wafflebox1
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.
Consider that the college that did most to increase the packing density of kids onto buses to the exclusion of all other considerations is... MIT. Choose your college accordingly.
Nullius in verba
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.
It's important, as riders prefer predictability to fit in with the rest of their scheduled daily activities such as school and work.
I know, right?
Just the other day I was waiting for the light rail and a couple cars got into an accident on the next street with one ending up disabled right in the middle of the tracks. Of course my first question to the people getting the passengers to swap trains so both could continue in their original direction was "Why doesn't your scheduling algorithm take into account these unforeseen circumstances because, you know, I have places to be?"
it breaks down the problem to separate problems for each school
Those assumptions are the problem.
Drop off children at elementary schools earlier. Pick up at elementary schools for high schools. Use the same bus at the same stop, simplifying the problem. The science also supports starting older school later. Two problems, one stone.
Learn to love Alaska
That doesn't sound right. $120 million over 30,000 students is $4000 per student-year. If there are 200 school days in a year, that's $20 per student per day, or $10 per student per trip. A savings of $5 million only reduces this to $9.58 per student per trip.
A monthly MBTA bus pass is $55/mo, which at 21 school days per month would work out to $1.31 per student per trip. So the school buses are 7.6x more expensive.
A little of the price difference I can understand due to school buses running fewer trips (a school bus usually services 2-4 schools on staggered schedules, with a few hours lull around lunch). So the purchase cost of the bus is amortized over fewer trips. Utilization of public buses is also higher. 392,413 riders on a weekday over 7200 round trips = 54.5 riders per circuit, which is close to or over 100% capacity per circuit (obviously not everyone is on the bus at the same time, but we're looking at fares per circuit). School buses OTOH run at about 51% capacity per circuit.
But if you figure these are both 2:1 factors, then that would bring up the MBTA bus cost to just $5.24 per student per trip. Still about half that of operating the school buses. Maybe that's the solution. In other countries I've visited, schoolkids ride the public bus and subway.
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...
What? You want to have high school students and kindergarten kids on the same bus? And you completely defeat the advantage of delaying the high school start time if you make them get up early to spend an hour due to a two-stage bussing plan.
I agree that having the younger kids start earlier is an obvious choice, but optimizing the bussing can work regardless of the ordering.
One of the most overlooked, yet most significant innovations of the early 20th century might be the Post Office’s decision to start shipping large parcels and packages through the mail. While private delivery companies flourished during the 19th century, the Parcel Post dramatically expanded the reach of mail-order companies to America’s many rural communities, as well as the demand for their products. When the Post Office’s Parcel Post officially began on January 1, 1913, the new service suddenly allowed millions of Americans great access to all kinds of goods and services. But almost immediately, it had some unintended consequences as some parents tried to send their children through the mail.
“It got some headlines when it happened, probably because it was so cute,” United States Postal Service historian Jenny Lynch tells Smithsonian.com.
Just a few weeks after Parcel Post began, an Ohio couple named Jesse and Mathilda Beagle “mailed” their 8-month-old son James to his grandmother, who lived just a few miles away in Batavia. According to Lynch, Baby James was just shy of the 11-pound weight limit for packages sent via Parcel Post, and his “delivery” cost his parents only 15 cents in postage (although they did insure him for $50). The quirky story soon made newspapers, and for the next several years, similar stories would occasionally surface as other parents followed suit.
SMARTNEWS Keeping you current A Brief History of Children Sent Through the Mail In the early days of the parcel post, some parents took advantage of the mail in unexpected ways image: https://thumbs-prod.si-cdn.com... Baby bag banner Uniformed Letter Carrier with Child in Mailbag (Smithsonian Institution) By Danny Lewis SMITHSONIAN.COM JUNE 14, 2016 | UPDATED: DECEMBER 21, 2016 40.9K183516543.3K Editor's Note, December 21, 2016 Listen to the Smithsonian perspective on this story from the Smithsonian’s new podcast, Sidedoor. Listen to the episode “Gaming the System” below and subscribe here for future episodes. One of the most overlooked, yet most significant innovations of the early 20th century might be the Post Office’s decision to start shipping large parcels and packages through the mail. While private delivery companies flourished during the 19th century, the Parcel Post dramatically expanded the reach of mail-order companies to America’s many rural communities, as well as the demand for their products. When the Post Office’s Parcel Post officially began on January 1, 1913, the new service suddenly allowed millions of Americans great access to all kinds of goods and services. But almost immediately, it had some unintended consequences as some parents tried to send their children through the mail. RELATED CONTENT A Brief History of American Dead Letter Offices Mail Delivery By Rocket Never Took Off A Brief History of Post Office Cats “It got some headlines when it happened, probably because it was so cute,” United States Postal Service historian Jenny Lynch tells Smithsonian.com. Just a few weeks after Parcel Post began, an Ohio couple named Jesse and Mathilda Beagle “mailed” their 8-month-old son James to his grandmother, who lived just a few miles away in Batavia. According to Lynch, Baby James was just shy of the 11-pound weight limit for packages sent via Parcel Post, and his “delivery” cost his parents only 15 cents in postage (although they did insure him for $50). The quirky story soon made newspapers, and for the next several years, similar stories would occasionally surface as other parents followed suit. image: