Waiting for a bus? Math may help
Georgia Tech student Alexandra Gaigelas takes a shuttle bus to get around the Atlanta campus. Many times, she waits too long for a bus.
"There's nothing more frustrating than standing at a stop, waiting for 10 minutes, getting on the bus and seeing another bus directly behind you.”
And that second bus is largely empty. It's called bus bunching, and it happens when buses are thrown off schedule because of traffic, weather or too many passengers at one stop.
And when those buses are off schedule, the drivers try to adjust. Student Sukirat Bakshi says he's been victim of a bus "drive-by."
“It happened to me where the driver just would not stop at a stop. They would just run off to catch up to the schedule.”
It turns out math can fix the problem. Georgia Tech professor John Bartholdi and University of Chicago professor Donald Eisenstein used complex algebra to develop a kind of anti-bus-bunching formula. They took what’s known as the Markov Chain through the wringer. It’s a math theory that shows predictable long-term behavior.
“The trick is to hold the bus for an adjustable amount of time at one stop,” Bartholdi said. “We simply control how long they wait at the end of the route, and then we tell them, 'drive comfortable with the traffic to the other end. Don’t worry about where you are. Just flow with the traffic.' "
Buses in the loop are all connected through GPS and a computer pad. It signals to the driver when it’s time to leave. Georgia Tech is testing the theory on its shuttle system.
“This tells me exactly when it’s time to go, and the communication between each other is done automatically, so it takes a lot of stress from us,” said Clarence July, who drives one of the gold and yellow Georgia Tech buses.
Drivers can ignore the schedule, and riders on campus can walk up to any stop and know that a bus will come within approximately six minutes. Bartholdi and Eisenstein say their math formula works for any shuttle system that runs in a loop in which buses are no more than about 12 to 15 minutes apart.
“Others have tried to control buses by asking drivers to try to adhere to a target schedule,” Bartholdi said. “What is new here is that the buses in effect coordinate themselves. No one needs to tell the drivers what to do; no one needs to worry about being off-schedule or how to recover a lost schedule.”
Georgia Tech plans to fully implement the no schedule bus system on campus this fall.
Here's how Bartholdi explains the equations used to calculate the space between buses:
This equation is actually a bunch of equations: one for each bus. The first line describes how the headway (the space between buses) changes for the bus that is currently at the end of the route (the turnaround point). Alpha (in red) is a control parameter - a number, say, 0.5 - by which the bus manager chooses whether the bus should wait longer (and fix imbalances faster) or vice versa. The "v" is the average velocity of the buses.
The second line describes how the headways of the other buses change.
This collection of equations describes how the headways change from bus arrival t to the next bus arrival t+1. In other words, it predicts the future behavior of all the buses.
Don Eisenstein and I recognized that this set of equations has a very special algebraic structure: they describe a "Markov Chain," which is a sequence of events for which the future can be predicted by knowing merely the current state (no history is needed). In our case, we only need to know the most recent headways to predict the next headways, and the headways after those, and so on.
The theory of Markov Chains allows us to conclude that, in the absence of disruptions, the headways will move inexorably and quickly toward a common value, which is given in the equation above. What this means in practice is that the buses will move away from each other, to space themselves more evenly. In other words, we will have created a force, a sort of "anti-gravity” that pushes the buses apart and so resists bunching.
@CNNLightYears on Twitter
People in Orbit
Expedition 36 Commander
Expedition 36 Flight Engineer
Expedition 36 Flight Engineer
Contributors
-
Elizabeth Landau
Writer/Producer -
Sophia Dengo
Senior Designer
OH gosh I totally rebmmeer that! It was when my son started a new school when he was a junior in high school so you'd think that I would have been okay but instead I dropped him off and then parked where I could watch (using binoculars like a stalker/peeping tom) until he got picked up. I still get sick to my stomach rebmmeering that day.I now have to do it 2 more times... my next two boys will be starting school next and then the next years. Ugh.
I just like the valuable info you supply in your articles. I'll bookmark your weblog and take a look at again right here regularly. I'm moderately certain I'll be told lots of new stuff right right here! Best of luck for the next!
Now that just sounds awesome. I look forward to great public transportation in the future.
It is not always feasible to use a private car.
Public transit is nothing more than a time wasting hobo infested metal tube of unhygienic squalor designed to waste tax payer money, spread communicable diseases and export crime.
After sundown your average city bus or train becomes little more than an outhouse / drunk tank / drug den on wheels.
At rush hour you're packed like cattle on their last ride to the slaughter house forced to endure cramped quarters as everyone passes around and spreads their colds and flu's and who knows what else.
Every surface in your average city bus or train is covered with excrement, pathogen and grime from thousands of unwashed hands. Furthermore a lot of people choose to consume food or drink on board a bus amid the squalor.
The costs of having a car are worth it just to know I don't ever have to deal with public transport
Why don't they just adapt the system that is used in Geneva? Those buses arrive on time every time. Or.... you could just double the amount of buses, that would cut the time.
how about... doubling the NUMBER of buses?
I remember when they were testing this, it was pretty sweet lookin!
Don't the drivers get breaks? According to the information provided, they don't seem to have factored that.
slightly racist. Also suggests author did not read the article- the driver doesn't have to understand the underlying math. He or she just goes when the system says go.
Nice article in the NY Times. I was rtailtng around in my suburban, 5-bedroom, 2.5 bath house a few years ago - me and a cat! It felt absurd, so I sold the house and rented a one-bedroom apartment in the city. Then I had the benefit of two cross-country moves in two years, inspiring me to purge even more stuff. When you have to pay to ship it, you realize you don't really value it. I like to joke that cash is easier to pack. I feel like I live a better life with about one-third of what I used to own.
Did they consider that by holding buses they might be able to space them more evenly, but the total number of runs goes down?
The best method for the passenger is also the simplest: do your run then immediately start the next run.
Think about it. They essentially are taking capacity out by reducing the number of runs.
So let's say their formula gets the time to an even 7 minutes between busses. The simpler approach with no idling of buses would likely produce results that vary, but the average time between buses would be lower. Isn't that the goal? Same amount of buses and drivers, but no idling to "even out" the times. So it might be 3 minutes or 9 minutes, but since the average is less than 7 minutes, the passenger wins.
No, the goal was to try to fix the "bus bunching" problem. They want the busses evenly spaced out so that one bus doesn't end up right behind another. Besides, a bus coming within aproximately six minutes isn't bad at all.
Exactly – they gave no thought to the actual "goal" of transportation – to move people as quickly as possible from point a to b. They got lost on a non problem of bunching, and then "solved" it by decreasing capacity and increasing total wait times.
Sorta makes them look bad, or at least shortsighted. Perhaps they simply needed to be told: whatever your solution, it can't increase total average wait times.
The problem of "bunching" was a real problem though, both for riders and for the transit system. By having one bus running behind and another right behind it, you've got one busload of passengers who are behind schedule, and a second bus that is transporting nobody wasting more fuel than a little idling would do.
Capacity hasn't been reduced, at least not according to the article- there's no mention of cutting down the number of vehicles in service, stops, or stop times. What's happened is the bus schedule is being adhered to more accurately, improving fuel efficiency, reducing wait times for passengers, and getting passengers to their destinations on time.
This sounds like a whole lot of win for both the passengers and the transit system if you ask me.
Another reader – there is no mention of reduced average waiting times. They simply looked at the issue of bus bunching and thought they solved something by maximizing the spacing between buses.
If they had actually reduced average wait times, don't you think they would have mentioned it? So they didn't reduce wait times.
They also didn't mention any increase in speed of delivery. With less bus hours available (by idling buses) that means each bus will likely stop at every stop. THAT MAKES IT SLOOOOOWER.
Compare to having the first bus in a bunch simply not stop for pickups. The people onboard get to the destination faster. The second bus picks up the people, and that waiting naturally spaces the buses apart.
The huge difference is that the spacing is on demand. And it doesn't simply happen at an arbitrary endpoint. With GPS and communications, it's not hard to tell a bus to skip pickups. There is a bell inside for the exact purpose of letting the driver know they need to stop.
Essentially it lets humans use judgement whereas a formula doesn't. And we can't forget their formula ONLY works on spacing, NOT shorter wait times or faster delivery.
Just because the average looks good doesn't really mean the passenger wins. If the first three busses are only half a minute apart, but the fourth bus is half an hour behind, the average is only about eight minutes [ (0.5*3+30)/4=7.88 ]. That's not so bad on average, but at least the second and third busses will likely run far under capacity while passengers waiting for the fourth get the shaft. Because of situations like this, it's more important to address even distribution than number of runs.
That's an unusual hypothetical – but OK, think about it – HOW ON EARTH WOULD HOLDING A BUS (IDLE) SOLVE THAT HYPOTHETICAL?
Simply put, if there is a traffic delay that adds 20 minutes to the run, holding it for any time at all would simply be 20 minutes PLUS the hold time.
I've never hear of anyone complain of too short a bus wait or too many buses. Wanting them to be evenly spaced also forgets one important thing: passengers are not evenly spaced.
The goal isn't to maximize the number of runs. It is to minimize the average time it takes for a passenger to reach his/her destination from the point they arrive at the bus stop.
Here is a simple intuition for why it may be optimal to wait: Suppose there are two buses that are at the same stop at the same time. Suppose that the next bus arrives in 12 minutes. Then if both buses leave immediately and drive one after another, the second bus will be empty the whole way. It finishes its run faster, but has succeeded in transporting nobody.
If that bus waits 6 minutes, then at every stop there will be more people, who now wait 6 minutes less for a bus and so get to their destination 6 minutes faster.
Here's another way to think about it:
By delaying one minute, a bus driver causes both a cost and a benefit. The cost is that anyone who would have caught his bus anyway is 1 minute later than otherwise. The benefit is that people who arrive at the bus stops along his route in that extra minute get to catch his bus instead of waiting for the next one, and so reach their destination T minutes faster, where T is the time until the next bus.
If there are very few people currently waiting (so that the cost is low) or there is a long wait until the next bus (so the benefit is high), it makes sense to wait.
The number of people waiting for him along his route if he leaves immediately will be a function of the time since the last bus (assuming people arrive at the bus stops uniformly). This logic implies that the optimal initial set up is to space out the buses perfectly, and that some idling at bus stops to restore even spacing is optimal.
The problem is that the average of 3 and 9 is NOT ACTUALLY 6, in this case. Because a passenger is 3 times as likely to fall into the 9 minute slot as the 3 minute one, the average is actually 7.5 ( 9 * 3/4 + 3 * 1/4 ). So this is actually a slightly worse average wait time than when the bus ran less frequently but more regularly every 7 minutes.
Strange, but true.
I really tried to avoid pulling numbers out of thin air. To then try to use a formula on made up numbers only compounds the problem.
I can explain this much more easily to you if you look at fast food operations instead. Would they ever hold up production to try to increase output? NEVER. Any increase in consistency of delivery times would more than be offset by a decrease in total output in a given time. That's not a perfect analogy though.
Or let's look at Amtrack trains. In order to be "on time" they hold the trains for long periods. Yes it gives them leeway, enough so they are always on time, but it results in 8 hour drives taking 20 hours. Of that, they can shave many hours off. They are completely spaced and no bunching occurs. But they are so slow because of it. And to take this back to the buses, no one cares when they come, just how often. And unlike the trains, there is no benefit to holding a schedule.
Also, buses run routes that are circular – so to speak. The end of the line is the beggining. So why would you use that point to hold the buses? Why not choose a point based on where they ACTUALLY bunch up instead of a made up endpoint?
There simply is no formula (involving idling buses) that would work as well as simply having the first bus stop picking up passengers, and letting the following bus do pickups until there is no bunching. You get a dynamic response to conditions that occurs along the route instead of simply at an endpoint. We need nothing more than a lighted sign on the front of the bus that won't pickup in order to let the waiting passengers know that the next bus is right behind it and ready for pickups.
You will note that not one time in this article did it say it would do anything to improve overall average wait times. Think about that. They studied it, and clearly would have touted it if it was possible. The fact they did not even mention it is a good indicator that it got worse.
Dude i dont think you get the point. actually wait times do go down, because there will be no bus bunching. In the current system, if one bus got ahead and one bus got behind, then the wait time would be much more than 6 minutes, not to mention a waste of fuel, since the ahead bus will reach a stop with no one there, as the previous bus would have just recently picked everyone up
I haven't spent a lot of time with this equation, but I am an engineer...it seems that using this method does not actually 'make the buses run on schedule', it only spaces them out evenly in response to the speed of traffic flow. It's still cool – and the stress removal from the drivers is probably the greatest benefit, if not schedule improvement.
Personally, I don't care what the schedule is – just how often it comes, and is there enough room onboard.
Look at Amtrack trains. They keep a schedule by holding the train. So an 8 hour drive takes 20 hours. They use the same idea that they are applying here, of course there are significant differences. But I simply reject the idea that you are going to move people more quickly by holding the buses. The routes are really circles, so the sooner it finishes the route, the sooner it starts the next one.
If they get bunched together, they simply need an indicator that the first bus won't stop to pickup, and a way to let the people at the stops know the next bus is immediately behind it. Everyone wins. The buses seperate (though not a perfect seperation). The maximum number of runs occurs with the minimum number of buses. And the shortest possible average wait time is acheived.
I reject gravity. I don't understand how it works so therefore it doesn't. Point-set-match.
If the total runs "goes down" then so what? If a second bus immediately follows another but is empty it's a wasted resource.
Newton, I'm no Einstein – but your theory of gravity was superceded. It's probably all relative.
JC – It's not like the first bus can't simply not stop for pickups when the next bus is right behind it. Granted, a sign or indicator to the waiting people would be courteous.
Essentially that would be dynamic adaptation to the conditions. The buses get spaced out, while doing the maximum number of runs.
The option presented of holding them at an "endpoint" on a circular route means that you have only one point to adjust at. And instead of keeping the buses moving the whole time, you have some just sitting there.
Please note that NEVER in this article did they say that it resulted in decreased average wait times. NEVER. It's not a huge leap to figure out that they actually made average wait times WORSE since they didn't dare mention it.
Really, this is news. The transit system Ames has been using this type "HOLD AT END" timing scheme for a long time. And on bad weather days or high-use periods they run buses back to back, wonder if they could calculate that idea as well.
Ohh nice, a recursive relation. Those are fun.
Finally, a news story on science, health, math that contains accurate information and the data to support it. I hope this journalist is made CEO of CNN before the end of the week. The Traveling Salesman problem was solved 20 years ago by Bell Labs. Queuing theory has addressed this bus problem in other domains for years. The problem is that there are so many domains, most of which are administered by government, that have uneducated people running the show. It is even true for the US public education system. The BA people are not trained in math and science. They have no clue how to assess a research report much less write one. College degrees in many disciplines are producing people with less capability to solve difficult problems than many engineering trade schools. Every college freshman should be required to take a Operations Research Course so that they understand what math can show. It would be the most significant course for all students as now people would know that there is a science that can be used to make decisions. Liberal socialism, fairness, equality are all bunk which tends to screw everyone. Math is KING!
The problem of the travelling salesman was solved by bees, millions of years ago.
We did the traveling salesman exercise in my computer Science Class 20 years ago. It was solved much earlier than that.
Aimee and Jeff,I read the article about you in Friday's New York Times. According to the story, you have a Honda Odyssey you would like to sell. If you have still have it, my wife and I would like to dssiucs purchasing it.My name is Craig Flournoy. My email is cflourno@smu.edu.According to one of your blog posts, you are visiting friends in Dallas this weekend. We live in Dallas. If it's convenient, we could come by to see the minivan today or Sunday (assuming you drove it to Dallas).I applaud what you are doing. I gave up a high-paying job as a reporter eight years ago, returned to school, earned a PhD and now teach college students. My wife also is a teacher. We have three daughters and have to watch our money closely to get by. But our lives are much more sane.Whatever happens, good luck to you and your family. It's nice to know the spirit of Thoreau lives on. - Craig Flournoy
That depends on what you mean by solved. The Traveling Salesman Problem falls into a category called NP-complete. Determining whether or not an NP-complete problem is a subset of a P problem is a Millennium Prize Problem. That is, solve it and collect $1,000,000. However, your chances of solving it is much less likely than winning a $100,000,000 lottery.
Your comment upon being slaeppd in the face by that insufferable French tree branch, probably didn't hurt american/french relations too much. So, can you provide a little more input on the success or failure with your limited luggage load.Mike
I also read the NYT article. Cheers and good luck to you, what you are doing is woednrful and brave! I can't help with a bus, but a light bulb went off in my head about the stuff you are having trouble giving away. Check out The philosophy is to give away and/or trade items so they don't go in landfills. Perhaps it will help you find more takers?My love and I have to remain in our small city, due to having parents who are getting to a point where they will need us to care for them. Otherwise, we live our life as simply as possible. No credit cards, small apartment, few possessions, etc. We're getting married in Oct. and are asking guests NOT to bring gifts!
This branch of science is specifically Operations Research and falls within Industrial Engineering. The mathmatical models behind this are used for a wide range of problems involving scheduling and optimization.
Kudos to the uncredited author for actually posting the equations. It is a nice break from so many dumbed down news stories here on CNN.
Proves once again that Mathematics is the most beautiful of the Natural Sciences.
Clearly Jesus is the reason these buses schedules change.
Mathematics is not a natural science. It is a formal science, as it deals with formal axiomatic systems. It belongs with computer science and logic, not physics, chemistry and biology.
CompSci, that is not true. Mathematics is the most natural of the sciences. Studies have shown that infants understand basic mathematical concepts such as greater or less. Nothing is more natural. Physics, chemistry and biology all have their own axioms, many of which rely on math. How can these sciences be "natural" if the underlying mathematical foundation is not?
I was always taught that you cannot "prove" anything in science. You can only support it with evidence. You also can't "prove" an opinion because opinions are subjective and science is objective.
Mathmatics is different from science. It is NOT a science at all. Sciece makes observations of the world and tries to exlain what it sees. Math is Not based on observation. It is a formal system. One can do a proof in math but one can never do a proof in science
OH!! I thought the headline read "Waiting for a bus? METH may help" – never mind.
baaaahahahahaha... too funny.
I find a major cause of traffic in my area is the dang Metro Buses stopping in the middle of the road to pick up people.
MBTA needs this. their bus schedule sucks