MIT Team's School-Bus Algorithm Could Save $5M and 1M Bus Miles (wsj.com) 104
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.
Re:So many jobs lost (Score:4, Insightful)
Re: (Score:1)
Traveling salesman problem (Score:2)
Re:Traveling salesman problem (Score:5, Informative)
Re:Traveling salesman problem (Score:5, Informative)
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.
Re: (Score:3)
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.
Re: (Score:3)
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.
Re: (Score:2)
You want to have high school students and kindergarten kids on the same bus?
Nope. I said drop off the elementary kids at the elementary school, then in that empty bus, put on the high school students.
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.
So getting on a bus at 8 at the elementary school is just right, so long as there that bus hasn't been used by elementary students earlier in the day, but putting them on a bus at 8 that had previously been used by elementary students is too early?
I agree that having the younger kids start earlier is an obvious choice, but optimizing the bussing can work regardless of the ordering.
Optimizing can't work regardless of the ordering. At least where I grew up, high school students buses were more spread out, assuming that
Re: (Score:2)
The percentage for an arbitrary graph is still quite poor. It's still about 1.5 times longer than optimal. Euclidean is much better and this problem probably qualifies...
Re: (Score:1)
There are several different polynomial algorithms [wikipedia.org] 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.
+1
I wish people in the USA would realize and accept this same sort of logic when it comes to the screwed up US healthcare system.
Re: Traveling salesman problem (Score:2)
For a small problem like this you can simply run through all possible solutions with a GPU in a matter of minutes. Brute forcing it is relatively simple, as the article said a couple of weeks of people-work.
Re: (Score:2)
I did a basic genetic algorithm project on this for a CS class. 100 cities, and it took about 90 seconds to chug out a working answer. Is it _the_ answer? Perhaps not. But it is good enough.
Interesting. (Score:3, Insightful)
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.
Re:Interesting. (Score:4, Insightful)
Re: (Score:1)
I wish they gave the fuel savings (or miles) as a percentage, then we could compare the little bit over 10% bus reduction to the miles reduction and actually know.
It seems entirely possible that each bus drives more, but there is overall savings.
it can't really be 20% more though I'd think. doing it the old way with 10% fewer buses would be only an 11% increase in bus time, this is also a decrease in overall bus miles.
Re: (Score:2)
Re: (Score:2)
Absolutely, if each bus is more heavily -- and efficiently -- used, where reduction in total passenger-miles is the goal. IOW, buses that are more heavily loaded require more driving around to pick up all the children.
Re: (Score:1)
I don't think it could be that extreme.
They cut 10% of the buses, presumably doing it at the efficiency of by hand, that's only an 11% increase in time.
I also suspect that maximum time is a constraint they had to work with.
Re: (Score:2)
Re: Interesting. (Score:1)
I meant to say if the efficiency was the same.
Clearly it can mean less time if the cut is do to increased efficiency.
Re: (Score:2)
You think a 20% increase in ride times could be accomplished with simultaneous carbon emission (proportional to fuel consumption) reduction? That would probably mean a massive efficiency jump in vehicle fuel efficiency. We'd hear more about that if that were the case.
No they just take all the downhill routes instead of the uphill routes.
Re: (Score:2)
Re: (Score:2)
Re: (Score:1)
As a parent, though, who's son rode the bus for 3 years, my first question would be if this will lengthen bus rides?
Your first question appears to be "who's son rode the bus for 3 years"
Re: (Score:2)
No, they are saying that they are a now a parent, are somebody's son, and rode the bus for 3 years (presumably as a student but possibly as a "bus dad"; then they asked a question.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
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.).
I'm guessing that these guys being from MIT, they've already calculated in that parents like you would drive their kids to school, thus reducing the number of kids and miles driven.
Re: (Score:2)
I'm guessing you didn't read where my son rode the bus for 3 years.
Re: (Score:2)
I'm guessing you didn't read where my son rode the bus for 3 years.
Was this bus named Snowpiercer? Did he get time off for meals and bathroom breaks?
Re: (Score:2)
You succeeded in getting me to Google "Snowpiercer".
Re: (Score:2)
Great film. Daniel Tosh's favorite, in fact.
Re: (Score:2)
Mediocre movie. overly symbolic, annoying ending, but some good action. Danial Tosh is great, but hardly a great movie critic.
It would be interesting to see the distribution of trip times would be for students. That should be very easy to calculate.
Re: (Score:2)
(He actually hates this movie and is vocal about it.)
Re: (Score:2)
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.
Why are you so concerned? I rode the bus a long time myself. My bus ride was 20 minutes. Let's round it up to an even 25 minutes. Now we increase that by 20% and it takes an extra 5 minutes. Since we're talking 5 minutes each way, it would cost an extra 10 minutes a day. If it's an hour long bus ride, then you're talking about 12 minutes, and the round trip is closer to a half an hour of extra time. But I doubt that there are routes in Boston that take that long, as it's a relatively urban area. So,
Re: (Score:2)
what kind of bus ride did your son have that this 20% increase is a non-starter for you?
My son's bus ride was upwards of 90 MINUTES. One way.
And what would you have had him do with those extra 10-25 minutes anyway?
Not waste another 1+ hours of his day.
$4k/yr/student? (Score:4, Interesting)
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...
Re: (Score:2)
It does seem excessive, and there's probably a story behind that... Probably not quite right or missing something...
But generally speaking, reducing the number of students on the buses by 1/3 would probably not amount to 1/3 cost savings.
For example, if a school bus cost $70k and it is carrying 70 students, that bus does not cost $10k if you get 60 students to stop riding. Same goes for a lot of the expense and capital costs associated with running that transportation, I would think.
Re: $4k/yr/student? (Score:2)
Each bus needs a driver and 2-3 teachers per day. All of them are also unionized and contracted to drive regardless of load. It's entirely possible this plan won't save anything as the contract has been signed several years ago for fixed amounts of buses.
Re: (Score:2)
Sure, but the street grid will never change (at least not significantly), residential density won't change (much) and cities on major waterways/ports typically thrive for centuries if not millennia (See Istanbul, Alexandria, London, Paris, Rome). Even if their contracts are for 50 years, they're saving time and labor measured over hundreds of years.
Re:$4k/yr/student? (Score:4, Informative)
$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).
Re: (Score:3)
Re: (Score:2)
Actually, I wonder if the school district ever thought about talking to UPS and/or FedEx - unfortunately I doubt it. But they're dealing with similar problems, and we know the two companies have put a lot of time and money into solving this.
Re: FedEX, UPSand others MONEY!! (Score:2)
You're talking about administrators. They probably have an it person that could've figured this out in less than the prize money but nobody bothered asking.
Re:FedEX, UPSand others MONEY!! (Score:5, Funny)
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.
Re: FedEX, UPSand others MONEY!! (Score:1)
This comment desrves more love
US Postal Service Delivers Childern (Score:3)
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,
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
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?"
One day those buses will be powered by CC (Score:1)
Clean Coal: the future for America's energy needs
Re: (Score:2)
Yes!! "clean" coal shoveled into a roaring furnace by children covered in grime and soot [wikipedia.org], a fat drunkard whipping them when they slack off, red and sweaty from the steam belching from the engine as it wheezes down the alley to the workhouse [wikipedia.org]!!!
Why read Dickens [wikipedia.org], when you can LIVE IT!!!
Coal - it's not just for breakfast anymore.
Kids. choosing a college for the fall ? (Score:3)
Bounty (Score:2)
Last I heard there was a 1M$ bounty on whoever solved the traveling salesman problem.
Re: (Score:2)
Since this is a real world issue, it's important not to let perfect be the enemy of good.
They don't really need to solve the traveling salesman problem. Just coming up with something reasonably close that can be done reasonably quickly saves a lot of money - significantly more than the one million dollar prize you mentioned.
$120 million (Score:1)
$120 million per year for 30k students. That's $4000 per year per student. Or 180 days of school that's $22 a day.
A local bus pass on MBTA is $55/month by way of comparison.
Is anyone else thinking that's one hell of a ridiculously high cost for school busing? I suspect fraud here. No wonder schools are failing students. Their administration and overhead costs are outrageous.
Re: (Score:1)
Re: (Score:2)
Considering that the MBTA does not pick you up at your doorstep, there just might be a slight difference. I'm not saying the cost is entirely justified but that the stops are more customized so that some increase is worthwhile.
I know that a number of years ago, San Francisco made heavy use of the regular transit buses fro school transportation; no idea whether that is still the case.
Re: (Score:2)
School buses shouldn't be picking everyon up at their doorstep either. That's way too many stops for something as massive as a school bus. They must be spending a fortune on gas and brake pads alone.
There's something seriously wrong (Score:3)
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 [mbta.com] 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 [mbta.com]. 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 [wgbh.org] 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.
Re: There's something seriously wrong (Score:2)
They tried it in our city. The problem is that inner city students were so badly raised, they continually had problems with fights, drugs, robberies and assaults after a few years the bus company cancelled the contract.
Re: (Score:3)
Then let the inner city kids get kicked off the bus and handed off to the cops, like any other person.
This is a problem that solves itself once you drop the "no child left behind" madness.
Re: (Score:2)
You mean, bus drivers and cops should profile black kids and arrest minors for "minor offenses"? Have you heard of Ferguson? In our city the mayor is actually ghetto trash.
Once they elected this mayor, she removed camera systems because it "targeted black communities", liquidated several major crime initiatives and reduced the police force and then when the statistics showed a 30% reduction in arrests per year, she claimed victory over the crime problem - because, as you can see, not targeting high crime ne
Re: (Score:2)
And? Let that trash city fail.
Public Transportation (Score:5, Interesting)
We would then have zero busses, teachers that are being paid closer to their value, safer public transportation and more full-time employment.
Re: (Score:2)
working 8 hours per day, 330 days per year
Where are you going to find 650 people willing to have only one day off every 1.5 weeks? Even for $37.88/hr, that's a bit of an ask, doncha think?
Re: (Score:2)
Re: (Score:2)
Re: (Score:1)
(Hint: if you think bus fares pay for even half of the cost of running the bus, you're.. wrong.)
Re: (Score:1)
Using public buses is a clever idea. It is already done in at least a few cities, though maybe only for a subset of students. However, consider that MBTA is subsidized by state and local governments. Would you be willing to factor this into your analysis? I hope it would still be attractive (and we might re-optimize the public buses to improve those too).
Re: (Score:2)
MBTA subsidy is $2.07 per rider. [mbta.com] over the entire system. Most of the students would ride daytime busses, which are subsidized less ($1.43). Using the higher number, the true cost of an adult charlie card is $3.13 ($2.28 for a child). Plenty of room to make that work.
The trick for making public transportation pay for itself is increasing paid ridership. The students would immediately increase ridership about 10% and start them on a life-long path of being customers. So, this even helps out MBTA even
Fuel !!! (Score:4, Interesting)
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 [wikipedia.org] 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!
Re: (Score:2)
Googling, I see many stories of usages and trials of electric school busses.
As many as (Score:2)
as many as 75
So... 75, then?
Someone had a word quota...
Re: (Score:2)
And your solution is to continue wasting tax money paying people to do a job that is not needed. That is about the dumbest idea I have heard for a while.
Maybe we could pay these people to do some of those "jobs that Americans don't want". I'm sure some Americans would want them if the choice was between "job I don't really want and starving" instead of "job I don't want and welfare." Use welfare to pay the relocation costs.
Re: (Score:2)
What fake jobs? I have family paying a bunch of teenagers slightly over minimum wage to sell burgers, fries and frozen custard. Just how much should somebody get paid for doing that and how much do you want that burger and frozen custard to cost.
Also, tending and harvesting crops and cattle and such is not a FAKE JOB. They are real jobs.