Airplane Boarding Algorithms

Background

I and two friends participated in the 2007 Mathematical Contest in Modeling. We tackled problem B, on airplane boarding. Our BOOM submission is an expansion of our MCM07 submission.

Airplane boarding is the process of moving passengers from the airport gate to their seats on the plane and getting their luggage stowed as necessary. Our MCM entry made use of several boarding algorithms currently in use, most of which are zone-based (they divide seats into areas one of which is filled at a time). The notable exception to the algorithms we considered is the policy--in use by Southwest or Jet Blue, I believe--of allowing passengers onto the plane in the order in which they put themselves in line in the airport, and allowing them to pick their own seats. This is termed random boarding, and appears to work better than all zone-based methods (but is harder to model :) ).

Summary

The following paragraph discusses modeling boarding from a discrete-simulation viewpoint.

Like many other processes in nature that are partly parallel and partly serial, the topology of the pathways on an airplane available for passengers to move around in has a dominating effect on the time it takes to fully board a plane. Every deterministic algorithm we have examined shares a common understanding of what people can and cannot do in the confines of the cabin. Every passenger is encumbered by rows of seats that can only be entered from one end, and passageways that can admit at most one person at a time. The best these deterministic algorithms can do is ensure that passengers are seated in the right order (the serial part) while seating as many passengers as possible simultaneously (the parallel part.) In evaluating some of the well-known algorithms for boarding planes of varying sizes, we have verified these observations, showing that planes with more aisles and smaller blocks of seats between aisles are well suited to the best of what these algorithms have to offer. Small planes are best treated by algorithms that seat fliers from the window toward the aisle, favoring the long aisle's capacity to hold people along the length of the plane. But the parallel advantage of the large two-aisle aircraft stands out, favoring algorithms that send entire blocks of people to the rear of the plane, leaving the resolution of seat interference to the multiple aisles' greater surface area. We believe that a plane is best modeled like the circulatory system, the common goal being the efficient saturation of tightly packed containers by discrete particulate objects. We believe that with better modeling of the intelligence and behavior of these particles, better algorithms can be developed: not deterministic ones that can at best fit the topology of the plane, but non-deterministic ones that reflect how agents attempt to locally navigate a high-surface-area, low-volume space.

Resources

• Our submission to MCM07 consisted of three parts: a full report, an executive summary (part of the answer to the question) and a summary for the judges to read prior to possibly reading our report. The summary is given above under Abstract.

  [pdf]	executive summary
  [pdf]	full report, with bibliography

• I'm happy to answer questions via e-mail.