Groceries: which lane is the fastest?
blog.mrmeyer.com
blog.mrmeyer.com
Besides, the better item to optimize when grocery shopping is the actual shopping experience. While you may spend five minutes in a check-out line, you may spend an hour or more shopping. Nicking a minute out of the check-out experience is irrelevant if you just wasted five minutes zig-zagging through the store for multiple items (traveling salesman problem) or if you made a couple calls back home to find out if you were out of ____ or needed ____, a time issue that is magnified if you forgot something and need to return to the store before your normal (optimized) shopping trip.
You're right about it not really being worth it for optimizing your waiting time. If there is only one checkout and it's some lady with 50 items and she's struggling with a checkbook, other cashiers will usually open up if you make eye contact with a free employee.
You'd save the most time by planning your shopping in advance. Make a list, and categorize it by food type. If you know your store layout, some time spent thinking about the order of you visit can pay off quite well. Plus, it helps reign in impulse purchases.
It sounds silly but I learned this from Apu on the Simpsons:
“Season 5: “Homer and Apu” Original airdate in N.A.: 10-Feb-94
Apu and Marge wait at the back of the long line in the express lane.
Apu: Mrs. Simpson, the express line is the fastest line not always.
That old man up front, he is starved for attention. He will talk the cashier’s head off.
Abe: {Ah, there’s an interesting story behind this nickel. In 1957, I remember it was, I got up in the morning and made myself a piece of toast. I set the toaster to three—medium brown.}—Then he tied an onion to his belt
Apu: Let’s go to…that line.
Marge: But that’s the longest.
Apu: Yes, but look: all pathetic single men. Only cash, no chitchat.
Marge smiles approvingly as the line moves much faster.”
Nearly every modern point of sale self-swipe card terminal will allow you to swipe, insert pin, and sign electronically before the cashier can finish scanning your items. The only step left once that has completed is to approve the transaction total with the push of a button. I wish more people were aware of this, and then card transactions would be faster.
You can do everything up to that point - 'what type of card is this', etc... And many places are going signature-free below a certain transaction size, so I suppose all interactions can be handled in those cases before the 'total' key is hit.
Entering in/scanning your customer loyalty number and pulling out your credit card and scanning it (and pressing credit/debit) is what I've been able to "preload".
One other neat thing I've noticed is that at my Costco gas station, I can pull the pump out and select my gas type while simultaneously scanning my costco + credit card. I usually try to time myself with the person in front of/behind me to see if I can start my pump faster than them. I usually win :)
As usual, I am too lazy to go look it up for myself. Back to hacking.
"One observational insight provided by comparing queuing models is that a single queue with multiple servers performs better than each server having their own queue and that a single large pool of servers performs better than two or more smaller pools, even though there are the same total number of servers in the system"
http://en.wikipedia.org/wiki/Queueing_model#Multiple-servers...
That being said: My understanding was that the many-line system worked better primarily because of the potential for a lot of lost time between the server saying "Can I help whose next" and the order actually starting. This time is obviously hugely dependent on factors such as floor layout, space around the registers, customers familiarity with the system, etc. The idea was that if you have one line for multiple registers (a la Wendy's) than when the second register opened up the next customer in line had to notice, go to the register, probably walk around the person ordering at the first register, and then start ordering. Whereas in the multi-line system (a la McDonald's) the next customer in line will likely be focusing on the register in front of them ready to take the one step forward when their time comes. These factors can certainly be minimized but in stores that are busy/crowded/not well laid out it they can make a noticeable difference. That's my $.02 anyways.
Say we have 100 people and 10 servers. Everyone takes 1 minute to process, except one guy who needs 10 minutes.
With 10 queues and the long taking guy ahead of 9 other people he's blocking all those for 10 minutes. Total processing time 19 minutes. With 1 queue and the long taking guy first (blocking 1 counter for 10 minutes) total processing time is 11 Minutes.
Another way to look at it is that with one queue, everyone gets the minimum possible wait time. In the many queues case you get that only occasionally. You could optimize the many queues so they're just as efficient as the one single queue but you'd have to know everyone's processing time in advance - impossible in a real world setting.
Not quite impossible. You might not know individually, but on average for a group or segment you could get this information and optimize. Banks can do this by splitting consumer and merchant lines. Merchants typically take longer (who knows by how much), and get their own queue.
With this system, you have 2 queues, 1 for each group. There may be a lot of variation within each group, but the averages work out. Consumers wait the average minimum processing time for the consumer group, and merchant wait the average processing time for the merchant group.
This still leaves room for underutilization. What if the merchant line is backed up and the consumer line is empty? Ideally, the extra tellers would work to pick up the slack, but if this isn't possible then it's still not an ideal system.
Often the first-class line is empty - do you let 'the rabble' check-in there and risk a first class passenger having to (gasp) wait a couple of minutes behind them; or make the long line of economy passengers stare at the unused desk and mutter about the airline.
(Though given that airports are really just a series of queues feeding each other the different in practice is pretty minimal.)
If you define fairness as the average user-wait, I think fastest first is actually optimal. This is still the case with one-queue systems: If you let the 10-minute person go first, you'll have blocked 1/10th of throughput for everyone behind him, and thus increase their wait time. Fastest job first is generally not a bad way to handle queues; it works great for things where "jobs completed per unit of time" is of importance, like chores or fixing bugs (of equal or similar priority).
Besides average user-wait, you could start inventing your own units for fairness depending on the problem. Maybe its average user-wait per processing minute, or something like that, in which case the solution might be more complicated (or might not be, I'm not too concerned with it).
jfb - It also doesn't have any negative effect on "the geegaws sold in line" as they just put the "geegaw" displays along the side of the one queue. In fact it is better for the store in that respect as they can show more variety.
The best way I can think of to get rid of this overhead is to have a rule where each cashier has a queue depth 2 that is fed from a single queue. But how would you get people to stick to just 2 people? And it would be very annoying to be just behind a slow person.
In theory people should naturaly start moving forward when they notice that somebody is finishing up but at least in the Rail station and Post office the counter staff have a tendency to shut their counter without warning or start processing some other task before they are ready to serve the next person.
It works pretty well, but can still be a little frustrating when you see a person who was behind you in the main queue get through first because your sub-queue took longer.
People usually won't act to optimize for the best throughput, just minimize their relative wait times. The behaviour of drivers on congested roads tends to confirm this.
Whole Foods in NYC has solved this problem by having one queue, but when you get towards the front, there are five separate, color-coded lines. At the front of the queue is a giant television that shows a bar of color for each lane. When a register opens up, the number for that register slides into the color bar for the next person in the sequence, and a voice announces "Register 12". It's fairly efficient at keeping the queue moving as well as managing people's psychological need for multiple lines. It also prevents cashiers from wasting time, because as soon as a transaction is finished, their register is automatically assigned to the next person in the queue. The only "wasted" time is the time walking from queue to register, and pleasantries.
Another point is that 6 people standing on a single line for 2 cashiers seems like a longer wait than 3 people standing on two lines.
Grocery delivery would seem the only way out.
At Wegmans at least, in the Northeast US, always pick the longest line. The one with the most customers.
Why? Visible long lines are bad for business. Front-end (checkout) managers hate long lines. As soon as they see them, they start bringing in more people to start running more registers, and then pull people from the back of the longest lines to these newly-opened registers.
This doesn't work so well if there aren't any long lines to begin with, but during the weekends and holidays, I always pick the longest line, and I always get moved to a line-less checkout lane. Never fails.
1) Around 1/3 transactions still require staff intervention of some kind. This might be credit card approval, weight overrides, or just dumb customers. If your transaction is one that needs it then the time it will take is much less predicable than in a normal check-out
2) As people become more familiar with them, they are using them for larger and larger loads. That means people are bringing shopping trolleys in, and bagging themselves, which is slow and creates traffic flow problems.
My solution is to focus almost entirely on how competent and quick the cashier appears to be. If and when most other people do that as well, I'll look for another undervalued variable.
Observe the lanes, every person is assigned 1 point, elderly (60+) +1, buggies over 70% full get +1, smokers get +1, welfare recipients +2. Add up the totals and the line with the smallest sum is usually the fastest. Obviously you can't always tell who is on welfare or who the smokers are, but the obvious ones are usually the ones that take the most time anyway.
Also, the self checkout lines can be incredibly fast or incredibly slow. If there is a problem you have to wait for a cashier to come fix it, and if the person in front of you gets confused it can take forever.
Consider the problem of optimizing the response time of a set of servers. Load balancing - keeping the hardware busy - will keep the request queues at roughly equal and therefore minimize the maximum queue length. That ensures that the hardware is as busy as possible, but you can improve on that.
When a new request arrives, you can either add all of that request to one queue, or you can split it into pieces and distribute those across all the queues. Distributing the request, assuming perfect load balancing, means the latency for that request will be k + 1/n instead of k + 1, where k is the length of the queue.
In other words: Parallelizing gets you a substantial improvement in response time without additional hardware, and without making the code run any faster. I didn't realize the implications of this until recently.
The task you are splitting has to be sizeable enough that the setup costs of parallelization (in this case, going to every cashier to put your stuff and then going and picking it up) don't outweigh the potential benefits from parallelization.In this case, unless you are buying the whole store, it just doesn't make sense to bother splitting your shopping cart like this.
Further, if all the cashiers are busy at all the times being useful (ringing customers), you cannot possibly get a gain from splitting any further. There's no way you could improve the throughput of this system when every processing unit (cashier) is at the top of its utilization.
Your comment only applies if all lines are equal, which they almost never are. So you can't assume perfect load balancing under this circumstance.
I think the best store queueing system is to have one main queue that distributes customers to the first available cashier. People with larger loads take longer, but this has little effect on the main queue.
That's a pretty good summary of Amdahl's law. Even a computer with an infinite number of processors can't run a program faster than it takes to run the slowest sequential part.
Something will happen there, though. Lines = deadweight loss, and deadweight loss = room for improvement.
> Lines = deadweight loss, and deadweight loss = room for improvement.
If every grocery store in town has the same expected line length, then the entire cost of line length is borne by the consumer---since the line lengths are in equilibrium, none of the stores feel economic pressure to reduce their line length, and the line length is a fixed cost of food shopping (unless latency becomes comparable with the length of time a store is open during the day, in which case it's actually limiting the number of customers they can process per day, but I find this highly unlikely).
Granted, a store might try to differentiate itself by reducing its average line length, but there are many other (perhaps more important) factors that go into a consumer's choice regarding grocery stores, e.g., Wal-Mart mega-food-store competes on prices, Whole Foods competes on its customers' self-satisfaction (I kid, I love Whole Foods).
Intuitively, it feels like grocery store line length is in the noise when considering the decision process for most consumers, especially since I can get zero line length at almost any store by going during off-hours. If it's in the noise, there's no selection pressure to improve it.
I think the chief reason line length is considered noise rather than signal is because it's so unpredictable. When it's known, people do a great deal to minimize their time spent in line. They go to the store at off hours; they switch lines once they're standing in them. I know my local Taco Bell gets a lot more business from me because of their speedy response time, vs. the teriyaki place next door that I like more, but takes forever. And my college's bookstore has had a great deal of success with putting live camera feeds of their lines (or lack thereof) on their website.
But with grocery stores, I couldn't really tell you which of the two grocery stores in my area would have a longer line. They're about the same, and that's close enough.
So you'd need a pretty big delta for line length to become a differentiating factor between stores. The current system of a cashier scanning items individually probably won't see drastic efficiency improvements without drastic changes, so...drastic changes are needed.
After a certain point, changes in "line length" become "presence or absence of a line at all." As jonnathanson says below, electronic scan-as-you-buy is probably the future there(Smith's, in answer to my cousin's email inquiry, mentioned they were testing a portable bar code scanner). I'm under the impression that grocery stores have pretty cruddy margins, so maybe I shouldn't read that much into "in testing." If anyone out there is dying for a startup idea, I think this one is worth a look. (Before you say it, I'm working on another project, and my cousin left for grad school.)
Since few things are more self-satisfying than sailing out of a store without waiting in line, maybe Whole Foods will be the first? ;)
The old guy ("Grampa" Abraham Simpson) is in fact also a single guy.
For enforcement they used sampling: at payment time, you were sometimes required to have your items scanned by a cashier anyway. The theory was that the more reliable you showed yourself to be, the less likely you were to be selected.
I haven't seen back to the store that they trialled it in recently, but I guess that it didn't work for some reason since it has not become widespread.
The next line is open, but I've already invested 10 minutes waiting in this one and switching will mean it was time wasted!