Optimizing Airplane Boarding

OK, check out this thought chain. I got an email from United Airlines inviting me to check in online, which I did earlier this morning. As part of the process, I was given the opportunity to change my seat. Unfortunately, the diagram that was offered to me didn’t indicate where the aisle was (United, this is an opportunity to improve your GUI), which is an important consideration when selecting a seat.

I wanted to know where the aisle was, and figured I probably could find the floor plan somewhere online. So I did a Google search for

boeing 767-300 floorplan

and found this paper on optimizing airplane boarding, by a team of students at Cornell’s Center for Applied Mathematics; here is the parent website. Page 10 of the paper has the floor plan of a Boeing 767-300, with the aisles clearly demarcated. (The story seems to be that the students submitted this paper to the 2007 Mathematical Contest in Modeling. The winning papers were published in this issue of the UMAP Journal; maybe United Airlines should read these papers. I bet it was a lot of fun to work on this project, whether or not you won the contest; just seeing how other teams approached the problem would be intriguing.)

I’ve always wondered whether we’re boarding airplanes in the most optimal manner. Given that passengers enter from the front, the standard procedure is to fill seats from back to front; obviously, filling seats from front to back sounds like a bad idea. But why not go a step further, and board the window passengers first and the aisle passengers last, from back to front? I guess the logistics would be too messy.

Some years ago, I was on a domestic flight here in the U.S. in which they boarded passengers from both the front and rear doors, which you’d think would be more efficient. And subjectively (I didn’t time it), boarding did indeed seem to go faster. But I never saw that done again. Maybe it required more attendants to handle two lines, and wasn’t worth the increased manpower cost.

Along similar lines, check out this recent MetaFilter post regarding Braess’ Paradox. Here, the very non-intuitive take-home message is that shutting down certain roads can sometimes improve traffic flow. Don’t you think that’s really interesting?

As for my airplane seat on United Airlines, I usually prefer to be seated next to the window so that people aren’t climbing over me to get to the bathroom. Unfortunately, no window seats remained unclaimed, so I settled for the aisle seat that was already assigned to me. Oh, well. I have printed out the Cornell paper and will read it on the airplane, as a sort of consolation!

Addendum (1/10/09): The Cornell paper confirmed that the standard procedure is to fill seats from back to front, in blocks. It also described several other algorithms for filling seats, including simply filling them at random to more exotic methods such as “Reverse Pyramid”. Window-Middle-Aisle (WMA) did better than random seating. Window-Middle-Aisle with Perfect Ordering (PO-WMA, i.e., WMA from back to front) is optimal; but the authors cautioned that “this method is potentially very difficult to implement,” which is what I suspected. They mention that this paper suggested that a deli-style ticket system might make PO-WMA feasible.

A surprising result from the Cornell study is that the standard procedure, block seating from back to front, actually did worse than random seating! Perhaps it is a compromise; maybe the standard procedure is indeed less efficient than random seating, but maybe it minimizes fights between people jockeying for the front position.

Another interesting thing is that the paper mentions which airline uses which algorithm. They reported that United uses WMA seating, giving this webpage as the reference; here, it’s called “outside-in” rather than “Window-Middle-Aisle,” but it’s the same thing. (Actually, the authors cited a web page at Arizona State University, but that web page is now defunct; apparently, Dr. van den Briel has moved to the University of Colorado at Boulder. I believe that the URL I have given is the Colorado version of the original Arizona web page.)

Sitting on the airplane reading the Cornell paper, I realized that I hadn’t noticed whether United actually boarded using WMA; my thought chain had been wandering elsewhere. But when coffee was being dispensed, I asked one of the more interactive flight attendants whether United in fact uses WMA. He said that they’re supposed to but the people at the gate counter have ultimate control, and most often they just go with the usual back-to-front by block method. With a mischievous smile, he also invited me to write a letter to the higher-ups at United to complain about it, if I thought it was important enough; maybe he had a beef with the gate counter people!