Sorting Out Highway Traffic

I’ve done a fair amount of driving around Canada. I’ve been across the country a few times, and I’ve done the drive here in Alberta from Calgary to Edmonton quite a few times. Since I am most often the driver these days, I get the wonderful combination of dealing with the sometimes crazy traffic, and developing thoughts in my head as the Alberta prairie flows by me.

While driving, I have noticed that cars on a moderately busy highway tend to travel in groups. I am not the only one who has noticed this, and there is a whole field of research and discussion connecting fluid dynamics and traffic flow. I’m going to step a little bit back from that, and apply another area where logic and mathematics tends to rear it’s beautiful head: computer science.

Cars on a highway are essentially trying to sort themselves from fastest to slowest. If every car on the highway was ordered this way, there wouldn’t be bunching of cars and the need for passing. In fact, there wouldn’t be a need for more than one lane at all.

Let’s consider a typical North American four-lane highway, where people follow the rules and drive on the rightmost lane unless they are in the process of overtaking another vehicle. The highway has limited access and a constant speed limit, so we are going to negate incoming and outgoing traffic and variable speeds as factors for this discussion. We’re also, for the sake of simplicity, going to assume that everyone is using cruise control, and has chosen some speed to drive for the duration of their trip, unless of course they are passing or have to slow down behind another car. Finally, the cars start in random order with respect to their speed; that is they are not in reverse order nor are they in perfect order already. When a faster car encounters a slower one, the pair perform what is known in computer science as a swap (pretty complex terminology, I know) and the set of cars on the highway becomes one step closer to being sorted. Specifically, the category of sorting that is being performed is a comparison sort. Comparison sorts are straightforward in that they only use one comparison (bigger or smaller) throughout the whole process, as opposed to multiple checks (bigger than this number, smaller than that).

Sorting a list of objects is a big deal in computer science. There are tons of ways to go about it, and many methods have been studied mathematically on how efficient different algorithms are, and what the best and worst case scenario is. For us, a useful metric is to find out how many average swaps/moves have to be made in relation to the number of elements. For example, a bubble sort has an average number of swaps of n(n-1)/4, which means that if a group of 10 cars on a highway were sorting themselves out using a bubble sort, it would take on average 23 swaps to sort out the list.

A bubble sort has a simple process: go through the list from front to back and compare pairs of items. If they are out of order, swap them. I brought it up because it’s pretty close to how it happens on the highway, except the encounters happen somewhat randomly (although the closer a car’s speed is to the faster/slower end of the group the more encounters they will have on average). Bubble sorts are fairly inefficient, one of the best the best comparison sorts, quicksort, has an average number of swaps of 1/3nln(n) (or for our case of 10 cars, 8 swaps on average); which is less than the bubble sort for more than two items. As the number of items grow. It’s likely that the “random bubble sort” the highway appears to be using is at least as bad as the standard bubble sort.

One interesting thing about applying this to traffic is that swapping cars take a pretty long time on a highway. In fact it’s likely that the time for two cars to swap places is close to the time between any two encounters. This means it’s quite likely that a car will have an encounter with another car but not be able to pass it because it is currently in a swap. This discrepancy is what causes groups of cars to clump up; by the time the 100 passes have been made, another set of cars has been caught up to (and caught up to them) and so these bundles of swaps happen, and traffic is “busy” at that particular moment for those particular drivers. You can think of these traffic bunches as “localized sorts”, and when you’re magically in between two of these you are, for the moment, perfectly sorted. Enjoy that moment of order and serenity on the road, it won’t last.

So what if we add another lane, up from two lanes in one direction to three? This would certainly help the situation where a car has to wait for another swap to finish before it can start, although there would also be cases where two swaps occur simultaneously and still block the system. What it doesn’t change, however, is the number of swaps that need to happen, and the time for each swap to occur. Intuitively, this is one more reason why adding in a lane doesn’t provide the obvious benefit you think it might. Going from one lane to two lanes, however, generally decreases the time for each swap, since there is not the additional issue of having to wait until it’s safe to pass in an oncoming lane. Going from one lane to two does decrease the time for each swap, and that helps a lot.

So the system isn’t great at sorting itself out, but it could be worse. There are people who develop sorting algorithms that are purposely bad, such as the bogosort, where a list of items is shuffled, checked for order, and then shuffled again if not sorted. At least we’re not that bad on the highway, as long as we stick to the right.

2 comments on “Sorting Out Highway Traffic”

  1. Daniel Ashlock Reply

    I suspect that more lanes isn’t the key variable – its jerk removal. On a trip from Guelph to Ames, Iowa I got caught in the eternal repair of I80/90 south of Chicago. Three lanes had to thin down to one and pass. It took so long, I composed a game theory model of driver cooperation and conflict. So far I’ve only gotten one publication out of this, but what I found is that even a relatively modest fraction of helpful, cooperative (angel) drivers substantially speeds things up. Of course this has me modeling with far more parameters per driver-agent than your model.

    • Willem Reply

      Looked up your abstract – very neat. I wanted to use a very simple model to motivate the idea of traffic sorting. It’s an oversimplification, I think but probably good for the purpose of a blog post.

Leave a Reply

Your email address will not be published. Required fields are marked *