If you go (or have ever gone) to a reasonably large gym, you might have encountered the typical locker room changing area. It looks like this:
If you go to the gym regularly (or have been a regular gym goer at some point in your life), you might have noticed an issue that arises with some frequency: the locker you’re trying to access is very close to one in front of which someone else is standing (because their locker is right next to yours). I’ll refer to this phenomenon as interference. Interference is annoying because it creates that awkward situation in which you stand there trying to be polite and wait for the other person to finish, while at the same time getting upset because you’re wasting your precious time: “Man, I was hoping to be finished with my workout in 45 minutes. I gotta go back to the office and work on that integer programming model. Why does this guy take so long to tie his shoes?”
Interference occurs in other places, of course; hence the title of this post. When boarding planes, airlines try to be as efficient as possible, that is, they try to get everyone in their seats and ready to go in the shortest possible time. What is interference during the boarding of a plane? It’s when passengers that are standing in the aisle (e.g., because they’re still trying to put their carry-on in the overhead bin) block the passage of other passengers whose seats are further down the aisle. You might think that the obvious solution is to board everyone starting from the back of the plane towards the front, right? Well, maybe. Back-to-front boarding is intuitively good, but there are other issues at play: some passengers have priority, not everyone is there when boarding starts, etc. Another strategy that seems to work well is a hybrid of back-to-front with window-to-aisle. As you might have guessed, people have used optimization and simulation to try and come up with good boarding strategies. One of these studies was published in the journal Interfaces in 2005: “America West Airlines Develops Efficient Boarding Strategies”. This is an interesting read, and I recommend it.
Where else does interference occur? This XKCD blog post talks about the International Choice of Urinal Protocol:
…the basic premise is that the first guy picks an end urinal, and every subsequent guy chooses the urinal which puts him furthest from anyone else peeing. At least one buffer urinal is required between any two guys or Awkwardness ensues.
Randall then proceeds to analyze this protocol and concludes that it suffers from a problem of underutilization of the available urinals, depending on how many of them there are. However, if guys are smart when picking urinals, they can achieve the optimal utilization (50%).
Now back to the locker room interference problem (which is the one that bothers me most lately). Let’s try to figure out the source of the problem and propose a solution to it. When you arrive at the University of Miami gym (known as the Wellness Center), you hand in your ID to an attendant who, in return, hands you a key that’s taken from a set of drawers that look like this (men’s lockers on the left, women’s on the right):
A key comes out of the drawer and your ID goes in. Interference is created because the attendants do not (and cannot) remember which keys they have handed out recently and what the layout of the locker room looks like. (By the way, locker numbers are not in perfect sequence in the Wellness Center; numbers jump around and you frequently see people who are lost looking for their lockers.) Ideally, what we’d like to happen is for keys to be handed out in such a way that they send the next person to a locker that is far away from the last few lockers that were given away. There are other complicating issues, of course, such as the fact that you cannot control the people who are returning from their workouts, but at least you can reduce interference among new arrivals.
We don’t need to write a mathematical model for this (or do we?). Why not pre-calculate an optimal sequence of locker hand-outs (based on the locker room layout), sort the drawers in that sequence (left to right, top to bottom), and have the attendants hand out keys in this order, cycling back to the top after they reach the last drawer? It won’t be perfect, but it sure will be better than the current system.
I went camping this past weekend (my first time) and my neighbor (who’s actually my neighbor in real life and was my neighbor at the camp site) was drinking a Snapple and read the following fact back to me:
