Queuing Theory Meets Your Morning Latte

August, 2003

Imagine: You walk into the Department of Motor Vehicles to get a new license, and you're not bombarded by crowds of irritated citizens waiting in endless line. (Resume reading when you wake up from your faint.) A lit board informs you about several options you can take to move through the system most speedily, and you choose the route through multiple counters that seems the most reasonable to you. Ten minutes later, new photo ID in hand, you're strolling out the door whistling Dixie.

Sound like nothing more than a sunny scene from a Jimmy Stewart film? Perhaps, but Professor Sunil Kumar says that such a real-life scenario may be possible with just a little help from queuing and game theory. His most recent paper, co-authored with Stanford doctoral student Ali Parlakturk, titled "Customer Choice and Routing in Queuing Networks," explores the theoretical possibility of channeling customers through a service network in a way that allows them to pick the "shortest route," while also subtly controlling them so that they don't end up inadvertently clogging up the works in their zeal to get out as fast as possible.

The study picks up where the famous Braess paradox leaves off. In the 1950s, German mathematician Dietrich Braess, who was studying traffic flow in road networks, showed that adding an improvement to a system in order to relieve congestion, such as building an extra road to reduce traffic, can actually make things worse. That's because each person's self-interested action of trying to find the fastest route actually makes the overall system worse. The result? More delays than ever. In fact, as shown by later work, the delay can increase infinitely.

How, then, does one design a network to service human customers that will not "infinitely deteriorate" in this way but will still give customers choices for proceeding through that system in ways that are most beneficial to them? That was the question mathematically analyzed by Kumar, associate professor of operations, information, and technology, and the Louise and Claude N. Rosenberg Jr. Faculty Scholar for 2002-03.

In the paper, Kumar uses queuing theory to determine how a simple two-station service system can use rules to handle customers in the most efficient way possible. "As an example, say you have two counters at Starbucks, one that serves the coffee and one that takes the money," Kumar explains. "Let's say you give customers the option of either paying first or getting their coffee first in order to minimize their wait time. We can assume that customers will always do what is in their best interest. But given that this can ultimately make the system deteriorate, as in the Braess paradox, can Starbucks create rules that maintain customer flexibility in routing while also preserving the functioning of the system? Can the cafe guide customer choices in a way that will actually benefit the company?"

Kumar's model suggests that a "network" like Starbucks can essentially set up a "game" and study a situation in which an individual customer cannot benefit from unilaterally changing her decision while all other customers keep their decisions unchanged. Economists refer to such a situation as a Nash equilibrium, named for Nobel laureate and mathematician John Nash. But some Nash equilibria leave everyone worse off. "In our example, Starbucks will need to intelligently apply scheduling rules to prioritize customers properly, and thus induce good Nash equilibria," Kumar says. "For instance, each of the service stations will have to keep an eye out to make sure that the other isn't starved for work. If this does happen, they'll have to adjust the rules for handling customers in the moment."

That might mean that if the coffee counter gets too busy and the cashier is idle, the coffee server tells customers that rather than handling people in line order, he will now give priority to those who have already paid. If the cashier gets overwhelmed and the coffee counter is idle, she may announce that she'll now serve first only those who have already picked up their coffee. Ideally, all customers would be informed of such a possibility up front so that they could make their choices as to which counter to go to first—that is, play the rapid-exit "game"—accordingly.

"Such dynamic scheduling rules would balance the workload, thereby minimizing delays caused by customers routing themselves selfishly and leading to a Nash equilibrium with excellent performance," says Kumar.

The model has other applications, such as for manufacturing processes that can be conducted in multiple sequences depending on customer preference. "For example, shape deposition manufacturing is a process used to rapidly produce product prototypes," says Kumar. "Customers will generally choose a production route that will minimize delivery time of the prototype to them. This can ultimately bog the manufacturing operation down, however, reducing its ability to generate revenue. Again, using our model, you can avoid this by making slight modifications in the scheduling rules regarding how customers will be handled within the routes they've selected."

Kumar hopes that his model, which is currently only theoretical, may be become the basis for empirical testing. "In fact, real-life situations are much more complex than the two-station network we analyze," he admits, "but I am currently looking into how such a model can be applied more generally, especially in communications networks."

MARGUERITE RIGOGLIOSO

Customer Choice and Routing in Queuing Networks" Sunil Kumar and Ali Parlakturk, GSB Research Paper #1782, January 2003.

Debt Relief Works for Some Poor Nations

Hailing Outside Prophets Can Threaten Inside Profits

Committing Altruism Cloaked in Self-Interest

Queuing Theory Meets Your Morning Latte

More Ideas from the Business School's Faculty

Faculty Publications

Queuing Theory Meets Your Morning Latte

Further Reading