Why Multiple Checkout Lines Are Not All Bad

“All models are wrong, but some are useful.”  George E. P. Box

Last week I saw a clever short video titled, “Why the other line is likely to move faster.”  It explains, among other things, why it often seems that no matter what checkout line you choose while doing your holiday shopping, you notice that another line is moving faster than yours.  The video generated some interesting discussion, at least on Reddit and Slashdot where I bothered to look.

(Unfortunately, the title of the related Slashdot submission was, “Scientifically, You Are Likely In the Slowest Line.”  This is not just misleading, it is simply false.  As several commenters point out, the argument presented in the video is the weaker statement that “you are likely not in the fastest line.”)

The focus of this post, however, is on another observation in the video, and the corresponding online discussion.  In the first part of the video, the Engineer Guy notes that there are (at least) two approaches to serving customers with multiple servers.  The first approach, common in grocery stores, is to have a separate line, or queue, of customers for each server.  The second approach, used at airport ticket counters, banks, etc., is to have a single queue of customers, with the person at the front of the queue waiting for the next available server.

The interesting observation made in the video is that the latter approach is much more efficient than the former: “… for 3 cashiers, it’s about 3 times faster than having a single line for each cashier.”  From some of the comments, this seems to be “common knowledge” from queuing theory, and businesses that still have separate lines should apparently open an operations research textbook and get with the times.

I am not so sure.  I am not an expert in queuing theory; even my last stochastic processes course was 12 years ago.  So as an exercise, I wrote a series of simple discrete event simulations of this process to see what happens.  For a specific example, let us assume that there are three cashiers as in the video.  Customers arrive with exponentially distributed inter-arrival times at the average rate of one every two minutes.  Each cashier serves a customer in an average time of five minutes, also exponentially distributed.  In each of the two queuing approaches described above, what is the average time that a customer must wait in line?  (This is the same setup used for a puzzle found here.)

Before getting to the simulation results, we can compute analytically what the average waiting times should be in both cases.  (Actually, this is in part why we assume that arrival and service times are exponentially distributed, so that the problem is analytically tractable.)  First, with three separate queues, the average waiting time is:

where (cashiers), (customers arriving per minute), and (customers served per minute by each cashier).

With a single queue feeding all three cashiers, the average waiting time is:

This all matches up reasonably well with the threefold improvement mentioned in the video.  And when I ran the simulation of the single queue case, I also saw an average waiting time of about 7.12 minutes.  Everything makes sense so far.

However, when I ran the simulation with three separate queues, the average waiting time was only 7.77 minutes, nowhere near the predicted 25 minutes.  What was going on?

It turned out that my simulation attributed more intelligence to the customers than is assumed in the above analysis.  In my first draft of the multi-queue simulation, as each customer arrived ready to checkout, he entered the queue that currently had the fewest number of customers.  In this case, the resulting behavior is not significantly worse than the single queue approach, in neither mean nor variance.  When I modified the simulation so that each customer entered a randomly selected queue, the average waiting time jumped to 24.49 minutes as originally expected. (Edit 2020-12-31: Python code for these two simulation variants is available on GitHub.)

Who does this?  Who approaches the front of the store with a full cart and just rolls a die to determine which line to enter?  Of course, queue length is not the only factor to consider: customers also gain some information about potential waiting times by observing the number of items in others’ carts, there are express lanes with different distributions of service times, etc.  Adding any of these factors to the model makes analysis more difficult, usually prohibiting closed form solutions like those above.  (For example, I suspect, but am not sure, that even my original “enter the shortest queue” process does not have a clean analytical solution.)

I think the point here is that the grocery stores and other businesses with multiple queues are not necessarily missing out on a better approach.  The mathematical models that admit clean solutions are only useful to the extent that they capture the relevant characteristics of the system being modeled.  A model stops being useful when it fails to capture even modest intelligence of customers; or the space and logistics required for one long, possibly serpentine line of grocery carts; or the psychological effects of customers seeing exactly the same number of people, not in several smaller lines, but one long line, etc.

Finally, some mathematical musings: first, as mentioned above, is there a simple analytical expression for the average waiting time of the “shortest queue” process above?  I suspect there is not.  Also, what about selecting a queue at random?  In the example above, I can certainly see how the average wait is 25 minutes if there are not only three separate queues, but three separate customer arrival processes, each with an average inter-arrival time of six minutes, for an aggregate arrival rate of one every two minutes.  I suspect that the random queue selection above may be equivalent to this in the sense that it yields the same distribution of waiting times.  Simulation bears this out, but I am not sure if things work out the same analytically.