Now boarding row N

I am at gate C21 at Houston Intercontinental, en route to San Antonio. The flight is late and overbooked; there’s a crowd of hopeful standbys at the podium. The first-class plutocrats are already aboard, and now the rest of us are filing on, one section at a time. “Passengers in rows 25 to 29 are invited to board the aircraft” was the first announcement. Ten minutes later they called for rows 20 to 29. My boarding pass is for seat 14B.

Frequent flyers understand the rationale behind this routine. By filling the airplane from back to front, the theory goes, passengers sitting in the rear won’t have to wait in the aisle while the couple in 8-A and 8-B stow their luggage, fetch blankets and pillows, argue over who gets the window, settle into their seats, get up again to retrieve a book from the overhead bin, and then discover that their tickets are actually for 18 A and B.

A recent paper reveals the awful truth. The airlines’ last-shall-be-first strategy doesn’t work. We might be better off lining up in random order.

The paper, posted in the physics division of the arXiv, is by Eitan Bachmat, Daniel Berend, Luba Sapir and Natan Stolyarov (all of Ben-Gurion University) and Steven Skiena of the State University of New York at Stony Brook. The authors call forth quite a dazzling array of high-powered mathematical tools in the course of their analysis. The geometric context of the problem turns out to be a two-dimensional spacetime with a Lorentz metric; there’s a combinatorial element to the story, involving longest increasing subsequences; from there, I’m afraid it gets even deeper, and at one point we find ourselves dealing with “the normalized discrepancy of the largest eigenvalue of an N x N matrix in the Gaussian unitary ensemble (GUE).”

For all that, the ultimate outcome is clear enough, and it even makes intuitive sense. Suppose there are 29 rows of seats with six seats per row, and the flight is full. Suppose further that the last-first policy can be enforced perfectly, so that all the passengers in row 29 are first in line, followed by those in row 28, and so on. Boarding should be a completely orderly process, with everyone sitting down after the minimum possible delay, no? No. The problem is that no one in rows 1 through 28 can reach their row until at least some of the six passengers in row 29 seat themselves. Then, everyone forward of row 28 has to wait for the next six people to sort themselves out. Under this regime the total boarding time is proportional to N, the total number of passengers. Lining up in random order offers a good chance of getting everyone aboard in time proportional to the square root of N.

If we insist on trying to find an improvement over the random result, we might be better off lining up with all the window seats first, then the middles and finally the aisles—a scheme that some airlines are apparently trying, with loading “zones.” Another algorithm for an airplane with 29 rows of six seats each would line the passengers up according to row number in this sequence: 29 23 17 11 5 28 22 16 10 4…. Then the question becomes: Is the flying public ready for announcements of the form, “We are now boarding all rows N where N is congruent to 5 modulo 6″?

Addendum: Once I finally got aboard, I discovered a further complication: The airplane didn’t actually have 29 rows. My seat in 14B was directly behind row 12. Evidently, Continental Airlines suffers from triskaidekaphobia.

This entry was posted in modern life.

2 Responses to Now boarding row N

  1. Eduardo Stark says:

    Dear Brian:
    I’m a frequent reader of your bi-monthly articles in American Scientist magazine. I would like to know what do you think about Python Programming Language and Numarray for illustrating the pieces of software you frequently use in your presentations.
    Regards from Eduardo Stark

    Dear Eduardo,

    It’s always good to hear from a reader of the column. Thanks for getting in touch.

    As for Python: The small and simple programs that I tend to discuss in my column could easily be written in almost any language. I don’t often work in Python myself, but I’m very much aware of the Python community, and I know it is especially active and lively in scientific and educational computing. It’s possible I’ll have an occasion soon to write about Python (and possibly the numarray package). In the meantime, if you’ve done work of your own in this area, I’d be very interested in hearing about it (perhaps better through private e-mail).

    — Brian.

  2. Brooke says:

    what is your experience of boarding via an odd and even rows pattern?

    Response: None. I’ve never been on a flight that boarded that way. If you’ve tried it, can you say how it went?