Thursday, August 13, 2009

Queueing Theory and You

Some thoughts on traffic—the automobile kind, not the network kind—while there's maintenance work going on in the office across the hall.

So the other day I'm driving into work, and I encounter not one but two traffic jams. Neither, as it turns out, was due to particularly heavy traffic loads. Rubbernecking (a.k.a. looky-looing) was the culprit in both cases. In both cases, the accident/attraction was off to the side of the road but managed to clog up the roads all the same.

I think it's generally underappreciated how much rubbernecking contributes to traffic jams. No one disputes that the accident itself can precipitate the jam. But a moment's satisfaction of curiosity? On the surface, it seems innocuous, right? As one of the drivers stuck in the jam yourself, you've already spent 10, 15, 25 minutes waiting behind this long line of cars—what could it possibly hurt to glance over for a second or two? But it's precisely that kind of glance that keeps the jam going. The reason for this lies in queueing theory, the study of waiting in lines, and comes about from the interplay between the level of traffic applied to a road, and the carrying capacity of the road.

Roads, like any other conduit, have a certain capacity, which is related to the size of the road but is also determined in large part by driving habits. You're taught, when you're driving, to leave at least three seconds of space between you and the car in front of you—more if it's dark or rainy or whatever. In the Los Angeles area, where I live, it's essentially impossible to do this; if you try, someone will invariably slide into the space, cutting yours down to a second or two, after which your options are to either to stay up close, or to back off until you're three seconds behind the new car, in which case the process repeats.

But actually the exact time is not all that important; what's important is that there is a characteristic following time, which determines the carrying capacity of the road. If the following time is two seconds, then the road can carry half a car per second (per lane). Note that this capacity is roughly accurate no matter how fast the traffic is going—whether traffic is flowing at the speed limit or crawling at 15 mph—as long as the following time is roughly the same. Only when traffic slows so much that cars take a significant time to travel their own body length (the following distance isn't head-to-head, but tail-to-head) does this rule break down.

Provided that that doesn't happen (and we'll get to that in a moment), we can now apply the most basic rule of queueing theory: If the amount of traffic going onto the road is more than the road's carrying capacity, traffic will come to a standstill. Hardly earthshattering news. If the amount of traffic is less than the capacity, traffic can flow. It might, however, flow incredibly slowly.

At first flush, this might sound kind of strange. If a road can carry a car every two seconds, and one car comes down the road only every three seconds on average, shouldn't there be enough room for cars to drive smoothly down the road, with quite a bit to spare? The perhaps surprising answer is that there might not be, and the fault lies in that phrase "on average."

If cars all scrupulously observed at least a two-second following time, and entered the road exactly three seconds after the previous car, then in fact, the cars would be able to flow at the speed limit. They would continue to do so even as you increased the rate of cars entering the road, up until the exact moment when that rate exceeded the capacity. At that point, the cars would start backing up and you'd get a traffic jam. And if you've ever been in a large traffic jam, it might seem that that's exactly what happened.

But that isn't in fact what happens. Generally speaking, the capacity of the road is not exceeded for long stretches. It's just very close. So why doesn't traffic flow smoothly, if the traffic load is less than the capacity? There are a few reasons, but the predominant one is that cars do not observe consistent following time, and don't enter the road at a constant rate. In queueing theory, variation kills.

Suppose that the following time is always at least two seconds, but that cars enter the road every three seconds only on average. Sometimes it's less, sometimes it's more. If it's less—let's say it's a second and a half—the new car now has to wait a half a second before it can proceed, because it's trying to maintain a minimum two-second following distance. On the other hand, if it's more, it doesn't have to wait at all. But it also doesn't try to speed up to catch up to the previous car; it's not trying to maintain exactly a two-second following distance, just a minimum of two seconds.

In short, if the time between successive cars is low enough, it slows traffic down, but no amount of time between cars will speed the traffic up. What's more, the closer the traffic rate gets to capacity, the more often a cluster of cars will arrive to slow down traffic, while the gaps between the clusters still fail to speed it up. We can express this effect graphically, by plotting traffic waiting time (a measure of the intensity of the traffic jam) as a function of the traffic rate R.


The exact shape of this graph depends on how following time and the time between cars entering the road vary randomly, but the basic effect is consistent: Instead of the waiting time (the blue curve) being constant at zero until R reaches the road's capacity C, it actually begins ramping up immediately, slowly at first but with increasing intensity until it spikes upward just as it approaches C (the dotted red line). And when you get close enough to C, the waiting time T gets large enough that you notice it as a honest-to-goodness traffic jam.

So what happens when people rubberneck? Yes, it's true, you might have been waiting for a long time, and you're only looking for a second or two. And you're still kind of driving at the time. But you slow down, just for a split second, and increase your following time. Instead of maintaining a minimum two-second following time, you increase it, maybe to two-and-a-half seconds. And if most everybody does this, the capacity of the road is effectively decreased, by 20 percent. It would have the same effect as closing one lane of a five-lane highway.

You might expect this to increase the waiting time T by 20 percent, but actually, what effect this has depends on how high R is compared to C. If it's relatively low—if we're on the left side of the curve—then moving C down by 20 percent, while keeping R the same, doesn't really affect T very much. But if it's already kind of high (and in Los Angeles, at least, it's that high about 24 hours every day), then moving C down by 20 percent can move you catastrophically high up that blue curve, increasing T many-fold and changing a mild nuisance into a dinner-delaying, or even dinner-cancelling, jam.

But that's OK. You just go ahead and look at that upside-down pickup. What could it hurt?

1 comment: