As I stood in line to board yet another plane this month, I wondered whether this was being done in the most efficient way possible.  It was the third airline and eighth flight in four weeks so time spent standing in line adds up – especially when you consider that delays in boarding often lead to delays in taking off since you have a narrow window of time to push off to keep your place in the takeoff line.

As a former operations research student, I figured someone did some research on this issue which is apparently called a “nonlinear assignment problem with quadratic and cubic terms in the objective function.”

Most airlines have some variation of boarding from the rear of the airplane going forward.  Because of this method, several problems come up that cause delays which everyone has experienced at some point:

1. People sit in the wrong seat and have to move across aisles
2.  Many planes have first class seating areas as the first rows you have to pass.  When first class members are allowed to board first, then they hold up people who need to go to the rear
3. Many airlines have elite members who get to board first.  This causes the same result as no.2
4. Calling each row is too hard so airlines board by zones (or groups of rows) which leads to delays when within the same zone, people sitting in earlier rows are ahead of farther rows. 
5. People need to stow their bags in places sometimes far from their seats and need to travel back and forth

Easier but impractical solutions to these problems include:

• Not allowing any carry-on bags
• Make aisles wider (or people less fat)

Some smart industrial engineer at Arizona State University named Menkes van den Briel did come up with a better solution that he calls the “reverse pyramid” method:

The first economy-class passengers to get on the plane are those with window seats in the middle and rear of the plane. Then America West gradually fills out the plane, giving priority to those with window or rear seats, until it finally boards those seated along aisles in the front.

This method has apparently been effective in reducing boarding time.  However, I think there are two big assumptions it makes that may not hold when you apply it on a larger scale:

• People can understand who is being called over the PA system and can follow directions for boarding.  The method is a bit complicated and people can’t be counted on following directions.  Enforcement of boarding order is critical but I haven’t seen the requisite level of discipline at any airline yet for current boarding methods.

• People can show up on time for flights so they can board in order

Surprisingly, in theory and in practice, one of the most effective boarding methods is to let randomness come into play and allow people choose their own seat as they board the airplane. It solves problem 1-4 and mitigates problem 5.

Southwest lets people choose their own seats once they get on board.  They further optimize this process by not charging for checking-in bags thereby reducing the amount of waiting for stowing luggage.  To ensure some fairness in the seating, they make you line up ahead of time in groups with priority given based on when you have checked in for the flight.  Business travelers and those who pay more get a slight edge by being automatically checked in for the flight as soon as possible.

Boarding time is a huge issue not only for passengers’ sanity but also for airlines.  According to the WSJ:

Southwest says that if its boarding times increased by 10 minutes per flight, it would need 40 more planes at a cost of $40 million each to run the same number of flights as it does currently.

I’m surprised more airlines don’t adopt this method given its benefits.  It’s such a great, non-intuitive solution for such a complicated problem.  It makes me wonder what other complex problems have similar solutions.