Airplane Boarding Problem

Inconvenience is the impetus for innovation. Despite being unnecessarily alliterative, I believe the preceding sentence to be true most of the time. One of the most inconvenient situations, I think, is the process of boarding a plane. Therefore, it's no wonder that significant research has gone into developing the optimal algorithm for boarding an aircraft.

Recently, on a trip back home from Seattle, I spent some time thinking about this when I noticed that I had a "zone number" printed on my ticket. The airline was boarding the aircraft serially, by zone. I was sitting in an aisle seat toward the back of the plane and had zone 5 (out of 7). This seemed to make sense, given that I had heard to optimal way to fill an aircraft is by filling all of the window seats first, then the middle, and finally the aisles. The concept here is that by getting people out of the aisle and into their seats quickly, you can board the plane faster - makes sense. The old process of filling the plane from the back forward was inefficient to say the least.

I recently read an article about a nuclear physicist that has patented his optimization algorithm for boarding planes. Here is an excerpt from the article:

"Then he ran various boarding options on his computer using the algorithm and found that one option was easily the best. This requires that each passenger is given a specific queuing position; that they board window seats first; and that they do so with an empty row between themselves and the next passenger. Thus passengers would board, if entering at the back of a 40-row aircraft, by filling up seat 40A, then 38A, then 36A and so on to the front; then they fill 39F, 37F, 35F, to the front; then 39A; 37A, 35A to the front; and so on, filling first window seats, then middle seats and finally aisle seats. If boarding from the front, they would begin at 1A, then move to 3A. The point is that people loading luggage do not block progress."

This appears to be an extension of the algorithm I described earlier.

Now, all of this makes sense in theory, yes? Well, in a vacuum, this would be incomparably faster than any process that we could implement in practice.

So, let's go ahead and add some corporate business logic to the mix. Consider the boarding process that U.S. Airways uses, the Reverse Pyramid. The algorithm is described in a Wired article here. Sounds pretty good, right? Now, let's take a look at the corporate implementation of the process:

• Pre-board call - Customers needing assistance and families traveling with children
• Zone1 – Dividend Miles Chairman, Platinum and Gold members, Star Alliance Gold™ members and all passengers in Zone 1
• Zone 2 – Dividend Miles Silver members, US Airways Signature® Visa and World MasterCard® holders and United Premier® members and all passengers in Zone 2
• Zones 3-7 – all other passengers following reverse pyramid system

Why does this have to contain all of these exceptions for certain classes of fliers and those who have the company's credit card? Don't answer that question - it is rhetorical. While, granted, there are probably a relatively small number of people on most flights that have these varying levels of status and credit cards, it seems like it could be enough to dilute the efficacy of the optimization algorithm the airline uses.

I should say that I have nothing against U.S. Air. I know that all airlines do stuff like this, but I wish they wouldn't let corporate partnerships and the like mess up a good efficiency algorithm.

Anyway, I always enjoy the application of mathematics and logic to solve everyday problems, so I thought I would post this.

--Chris