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.