March madness

Newsroom has a long piece on traffic congestion in Auckland in March. Near the beginning, Douglas Wilson, from the Transport Research Centre at the Uni of Auckland says

“So suddenly people say, ‘Wow, it’s taking me double the travel time to get to work. Why is that the case?’ It’s not that you’ve doubled the traffic volume. Actually, the volume has only gone up a little, proportionally, but the traffic flow has reached capacity.”

This is one of the Two Simple Facts from queueing theory, the branch of applied probability that deals with congestion in networks. These networks can be physical road networks or electronic data networks or something like a system of medical waiting lists, or something as simple as a literal queue, and what they all have in common is waiting for other users.

Queueing theory can lead to very complicated simulations and theoretical approximations, but parts of it are simple. My Two Simple Facts are

1. When you have multiple servers you should still try to have a single queue
2. A queueing system has a “capacity” and when it gets near that capacity small changes make things much worse

Most of the time, Auckland’s traffic system works reasonably well. There’s enough wiggle room for traffic to catch up around the inevitable slowdows.  When you get a big crash on the motorway or heavy rain or extra drivers, though, the whole system suddenly gets much slower. In the other direction, removing drivers after Christmas opens up the city out of all proportion to the number who leave.

Sudden slowdowns near full capacity are a pretty general property of queueing systems. We can look at them in a nice simple example — this sort of mathematical model is very useful both for understanding the general vibes and for developing theoretical tools.

Suppose we have a market with a single checkout queue.  People arrive in the queue randomly, at some average rate — perhaps 20 people per hour — and the checkout operator can process them at some random rate — perhaps 30 people per hour.  If there’s no-one in the queue, the checkout operator catches up on TikTok until the next customer arrives.

The capacity of this system is 30 people per hour: if you get more customers than that, on average, the checkout can’t cope. The basic question is “what happens to the queue length for various arrival rates?”.  You might reasonably guess that the queue stays short if the arrival rate is less than the service rate and gets longer and longer if the arrival rate is more than the service rate.  What’s less obvious is the transition between these, when the arrival and service rates are not far apart.  If the arrival rate is a little bit less than the service rate it turns out that the queue length varies wildly.   It takes surprisingly small  increases in arrivals to go from a stable, well-behaved queue to a wildly variable one, to one getting longer without limit.  That’s March Madness.

Here’s an example for you to play with: adjust the arrival and service rates, then press the button to get a picture of how the queue length changes over time