Ages ago (in blog years) I mentioned some algorithmic ideas for getting passengers aboard airplanes faster, based on a 2005 paper by Steven Skiena and others. Since then, the queue at the departure gate has only gotten longer. Now another preprint on the same theme has landed in the arXiv. This one is by Jason H. Steffen, a postdoc at Fermilab.
Steffen assumes that the main impediment to speedy boarding is the time passengers need for stowing their carry-on luggage. He argues that the loading process will go faster if we make sure everyone has plenty of elbow room for cramming their wheely-bag into the overhead bin. Thus he favors boarding-line sequences generated by the following rule: If two passengers are seated near each other in the aircraft (in the same row or in adjacent rows), then they should not be adjacent in the queue.
I don’t necessarily agree with Steffen’s premise or his conclusion, but I have no evidence of my own to report, so let’s set that issue aside. I’m intrigued by a related, subsidiary question. If we assume that there is some optimal ordering for passengers as they enter the airplane, how do we organize the unruly and impatient mob at the departure gate so that everyone enters the plane in the specified order? Here are a few ideas.
Boarding Hats. Most airlines now use some kind of zone system, where the passengers are divided into several groups. As boarding time approaches, people mill around near the gate asking, “Have they called Group 2?” or “Is this the line for Group 4?” To achieve finer-grain control over boarding order, we would need larger numbers of smaller groups, which would make the process of finding the right group even more cumbersome. In the limiting case, each passenger would be assigned an individual boarding-sequence number, and the passengers would have to sort themselves into the correct sequence. People are actually rather good at this task, given enough information. When I was a schoolboy, my classmates and I could quickly line ourselves up in order of height, relying on an efficient parallel sorting algorithm. But that method works so well mainly because height is a visible trait. To bring to same efficiency to sorting passengers at the departure gate, the boarding sequence number must be as readily discernible as height. Thus I propose replacing the traditional boarding pass with the boarding hat, which has your number prominently printed on all sides. This innovation would be a special treat for the mathematical community, given the well-known genre of puzzles about mathematicians who can see the number on everyone else’s forehead but not their own.
The Boarding Buzzer. If you think a numbered paper hat is too undignified for airline passengers, here’s another replacement for the boarding pass. When you check in for a flight, suppose you get an electronic gadget like one of those buzzers that restaurants hand to customers who are waiting for a table. As I imagine the boarding buzzer, it has various blinking lights and sound effects and a display screen that counts down the minutes remaining until you are due to report to the gate. The time shown on the display is different for each passenger and is calculated to get everyone on board at just the right moment. When I first thought of this scheme, I dismissed it as preposterous technological excess. But when I told a friend about it, she said I shouldn’t blog it; I should patent it. Obviously I haven’t taken my friend’s advice, and so when I check in at an airport a few years from now and the agent hands me one of these contraptions, I’m going to be mightily annoyed to see that someone else has cashed in on my idea. Still, the device could have certain charms. It would allow you to wander throughout the airport rather than remain tethered to the departure lounge. If a flight were delayed or shifted to a different gate, the airline could notify you right away. Likewise, if you were on standby, you could be paged when a seat opened up.
Out-of-Order Execution. The problem of dealing with suboptimal sequences of events is familiar to designers of computer hardware. Many modern microprocessors analyze the stream of instructions awaiting execution and reorder them to improve throughput. If the next instruction in the stream can’t be executed immediately because its operands aren’t yet available, then maybe some other instruction can take its place. This principle could also be applied to airplane boarding. As passengers enter the jetway, their boarding passes are scanned, and so their actual order in the queue is known from that point forward. Suppose there were a small buffer area at the other end of the jetway, near the aircraft door, along with a display screen where passenger names could be listed. This scheme would allow groups of passengers to be rearranged at the last minute to avoid bottlenecks. The overall boarding order might not be ideal, but it could be locally optimized.
First Come, First Served. A few airlines have abolished seat assignments altogether: You line up at the gate, file onto the airplane, and take any unoccupied seat you choose. In my experience, the boarding process on open-seating flights is generally quick and efficient. But the protocol creates an incentive to be at the head of the queue, and so people start lining up at the gate quite early. Thus the airline gets the benefit of faster loading, but the passengers likely spend more time waiting in line.
The Worst of Both Worlds. Here’s an idea so bad I hesitate even to mention it, lest some airline decide to try it. Suppose all seats are assigned, but you don’t receive your assignment when you book a flight or when you check in at the airport. Instead the assignment is made as you hand in your boarding pass at the gate. This allows the airline to parcel out the seats in whatever order will optimize the boarding process, but it leaves the passengers with little or no control over where they sit. (After long observation you might figure out something about the assignment algorithm and thereby learn where not to stand in line.)
A final thought about luggage: If Steffen is right that carry-on baggage is the main cause of delay, some other tactics might be considered. What if passengers without carry-on bags were allowed to board first? By assumption they would board quickly, relieving congestion for the heavily laden crowd to follow. The policy might also induce some passengers to carry less luggage.
Then there’s the Russian-made aircraft I flew on once, many years ago. You reached the passenger cabin by walking through a lower deck lined with luggage racks, dropping off your bag on the way in and grabbing it on the way out. Probably preferable to wearing a numbered hat or carrying a buzzer.
You dismiss the first come, first served model rather quickly. I assume, therefore, that you’re not familiar with Southwest’s method. When you check in with Southwest, you are assigned a boarding group (A, B, or C) and a number (1-60). So your order is based on when you check in, not how long you’ve been standing in line (see below, however)
When boarding begins, the boarding group and either 1-30 or 31-60 is asked to line up. There are signs breaking the line into sections of 5 and rotatable signs indicating the letter. Everyone lines up in their appropriate group of 5, usually not bothering to be exactly precise (they don’t check when they scan your boarding pass)
In my experience, the technique works very well. People tend to spread out, alleviating the baggage problem. The bottleneck tends to be when all the window and aisle seats are full and people have to choose a middle seat (all Southwest flights are on 737s). Everyone is reluctant to spring for a middle seat, so they tend to move slow, looking for an aisle or window seat.
Another interesting aspect of Southwest’s system is the passengers who stay on the plane when it stops to take on new passengers. Because Southwest flights don’t just fly from one place to another and back repeatedly, some of the passengers don’t have to change planes. This means that occasionally, even if you have an “A” group boarding pass, you’ll still end up in a middle seat.
Southwest’s system is definitely the fastest I’ve used. I much prefer it to the others.
About the checking in: Check in online starts 24 hours before the flight leaves, so if you actually wait until you get to the airport to check in, you’re pretty much guaranteed a late B pass and a middle seat. There are a few websites which will allow you to check in automatically exactly 24 hours before your departure time.
“When I was a schoolboy, my classmates and I could quickly line ourselves up in order of height, relying on an efficient parallel sorting algorithm. But that method works so well mainly because height is a visible trait….”
I wonder, what is the comparison threshold for judging relative height? I can imagine a scenario in which a large class, with a shortest-to-tallest difference of several inches, is unable to sort itself because nobody rates himself taller or shorter than the people on either side of him — one could conceivably even have the students lined up in exactly the wrong order!
To make the problem somewhat more mathematical, suppose you start with a permutation of the integers from 1 to N (say N=100), and then start transposing adjacent elements into “correct” relative order if they differ by more than 1. After all possible transpositions are made, you can take some measure of how far off from 1…N you are. One might ask for the “average error”, or some such statistic.
The shipping industry solved this years ago - containerization. Instead of boarding, a block of fliers would arrange themselves into a seating container, which would then be sealed and placed in the aircraft.
I wonder why carry-on luggage is always above the seats? Why not have the bins below the seats? Would require less lifting.
There’s also the possibility of an auction, where passengers bid on their boarding order. Would solve the problem of who gets the bin and the window seat.
@ Caleb Eggensperger
I fly Southwest often, and I know the A-B-C drill, but not the numerical sequence within those groups. Perhaps it’s something added in recent months, or used only at certain airports?
I first saw the sections of 5 within the Southwest A-B-C groups in January, 2008 (in Boise, ID).
@ Barry Cipra:
If we’re talking about what actually goes on in the classroom, there’s no rule requiring that the pupils make only pairwise comparisons of nearest neighbors. On the contrary, I think the process works so well partly because people in this situation tend to employ a hierarchical method. First you look around and decide whether you belong toward the front or toward the back, then within your half of the group you reach a similar judgment, and so on. Thus each child makes on the order of log2 n decisions.
But I find Barry’s approximate-sorting problem interesting, even if it doesn’t describe the “Line up alphabetically according to height” process. Surely someone has studied this?
I’ve written some very hasty code to play with the idea. The results seem to depend sensitively on the details of the sorting algorithm.
I define a predicate, ‘close-enough,’ which returns true iff two numbers differ by no more than 1.0. If I plug this predicate into the standard Lisp ‘sort’ function, I get results that are not well sorted, to say the least:
9 11 10 15 1 13 17 4 19 8 3 2 12 14 18 20 6 5 7 16
15 7 8 18 16 17 13 12 20 19 1 11 10 9 6 4 5 3 2 14
12 11 9 4 2 16 15 18 17 20 13 14 19 6 5 7 8 10 3 1
It appears there’s not even an upper limit on the difference between adjacent elements. I don’t know offhand what algorithm the Lisp ‘sort’ procedure uses, but I’d guess it’s some variant of quicksort.
Doing an insertion sort with the same ‘close-enough’ predicate gives results that look like this:
2 1 4 3 6 5 7 8 11 10 9 13 12 14 15 18 17 16 20 19
4 3 2 1 6 5 9 8 7 10 14 13 12 11 16 15 17 20 19 18
2 1 3 5 4 7 6 8 10 9 11 14 13 12 18 17 16 15 19 20
A version of the exchange-sort Barry recommends gives similar-looking results:
2 1 3 4 6 5 9 8 7 12 11 10 14 13 17 16 15 18 20 19
1 2 3 5 4 7 6 8 11 10 9 17 16 15 14 13 12 19 18 20
2 1 4 3 6 5 8 7 10 9 11 14 13 12 16 15 18 17 20 19
Next question: What’s a good measure of out-of-sortedness? Ordinarily I’d say the sum of (aj – j)2, where the index j runs from 1 through N. But here we seem to be looking for a more local measure—maybe simply the count of out-of-order pairs, or else something like the sum of (aj – aj+1)2.
I suspect there’s more to say about this idea of sorting with errors or approximations. Maybe a subject for an item of its own.
@ Jim Ward:
When I patent my boarding buzzer, you should be sure to file for your airline container idea. Brilliant! And what’s especially nice is that containers are “intermodal.” We can board our Paris-bound container at the train station; it will be hauled by rail to the airport and then lifted by crane from a siding onto the waiting containerized aircraft.
What about the fastest way to deboard, or unload an airplane? The airlines do not say anything about how this should be done, yet by unwritten custom it always seems to be row by row, front to back. Why has this custom evolved? It seems rather inefficient, aisle, center window would probably be faster. Also, does it follow that reversing the fastest loading scheme is the fastest unloading scheme? I would think not.