Ivars Peterson's MathTrek
It shouldn't be that hard to get passengers on board an aircraft in a timely manner. But there are complications. Flights are often full. Privileged fliers generally get seated first. Some passengers may simply disregard boarding announcements and go out of turn. Luggage doesn't cram easily into packed overhead bins. Someone ends up in the wrong seat and has to switch. A plane's seat configuration and narrow aisles can add to the confusion. The result: disgruntled customers and disgruntled airlines.
There are lots of possible boarding systems. The simplest is random boarding, either with assigned or unassigned seats. Or, at the other extreme, each seat can be called out individually, and passengers get on one by one.
However, airlines typically assign passengers to groups (or zones) to facilitate boarding, allowing only one group at a time to board. At issue is the question of how to assign passengers to groups to minimize boarding time.
For example, it might be best to board groups from front to back, from back to front, from outside to inside (window seats first, then middle, then aisle), or some combination of these strategies.
America West Airlines, now part of US Airways, worked with industrial engineers Menkes van den Briel and René Villalobos of Arizona State University to figure out a system that minimizes seat and aisle bottlenecks. Computer simulations showed that a "reverse pyramid" process appears to work best. In this case, passengers board from back to front and from window to aisle.
A mathematical model recently developed by computer scientist Eitan Bachmat of Ben-Gurion University and his coworkers provides additional insights into the boarding process. The analysis takes advantage of two-dimensional space-time geometry and, intriguingly, involves a branch of mathematics called random matrix theory, which is used to describe the quantum behavior of large atoms (see "The Return of Zeta"). This topic in turn has links to games of solitaire and constructs called increasing subsequences (see "Solitaire-y Sequences").
The researchers assume that the main cause of delay in airplane boarding is the time that it takes passengers to organize their luggage and seat themselves once they have arrived at their assigned row.
The model demonstrates that boarding from back to front is less efficient than letting everyone board at the same time. The problem with the back-to-front approach is that everyone else has to wait until the passengers in the designated row get settled, so, in effect, the boarding time is proportional to the number of passengers.
"Among row-dependent policies which do not severely constrain passengers, random boarding (no policy) is almost optimal," Bachmat and his colleagues report. For random boarding, boarding time is roughly proportional to the square root of the number of passengers.
Nonetheless, it is possible to improve on random seating or any row-dependent system by allowing window-seat passengers to board first, they conclude.
Maybe it's also worth trying a policy in which passengers with no carry-on luggage get to board first, then those with one piece of luggage, then those with two piecesas long as someone strictly enforces a size limit.
Aldous, D., and P. Diaconis. 1999. Longest increasing subsequences: From patience sorting to the Baik-Deift-Johansson theorem. Bulletin of the American Mathematical Society 36:413-432. Abstract available at http://citeseer.ist.psu.edu/aldous99longest.html.
Bachmat, E., et al. Preprint. Analysis of airplane boarding via space-time geometry and random matrix theory. Available at http://www.cs.bgu.ac.il/~ebachmat/prlsubmit.pdf.
Demerjian, D. 2006. Airlines try smarter boarding. Wired News (May 9). Available at http://www.wired.com/news/technology/0,70689-0.html.
Hayes, B. 2006. Now boarding row N. bit-player (Jan. 12). Available at http://bit-player.org/2006/now-boarding-row-n.
Peterson, I. 1999. Solitaire-y sequences. MAA Online (July 5). Available at http://www.maa.org/mathland/mathtrek_7_5_99.html.
______. 1999. The Return of Zeta. MAA Online (June 28). Available at http://www.maa.org/mathland/mathtrek_6_28_99.html.
Stanley, R.P. Preprint. Increasing and decreasing subsequences of permutations and their variants. Available at http://arxiv.org/abs/math.CO/0512035.
Zamiska, N. 2005. Plane geometry: Scientists speed boarding of aircraft. Wall Street Journal (Nov. 2).
Menkes van den Briel of Arizona State University has a Web page devoted to aircraft boarding at http://www.public.asu.edu/~dbvan1/projects/boarding/boarding.htm.
Comments are welcome. Please send messages to Ivars Peterson at email@example.com.