Analog Concurrency: Boarding a Plane

18 Apr 2007

Last week my family and I returned from a visit with the in-laws and boarded a fully-booked Continental Airlines flight at Sacramento Airport bound for New York-La Guardia. Typical of air travel these days, it took nearly a half-hour to shuffle the nearly 140 passengers on board. There were crying kids, wimpering animals in pet carriers, amorphous lines, bustling mobs, and a cavalcade of renegades who believe boarding by row number can’t possible apply to them.

From a civilian’s perspective, this was just one more example of the headache and disorganization we come to expect while being carted into passenger carriers like Guernseys onto a cattle car. From an engineer’s perspective, though, it’s actually an interesting and tantalizingly thorny optimization problem.

The Problem

Airlines allow passengers to loiter and congregate around the gate until the plane is ready to be boarded. At that point, some flavor of queue is requested by loudspeaker announcement. Such a queue is necessary because the gate crew needs to serialize access to several distinct shared resources: the boarding pass scanner, the jetway, the airplane hatch, and the aisle on the airplane itself. If a queue did not exist, either the unruly mob would just jockey for position to get past the boarding pass scanner one by one (everyone holding out their barcoded passes like floor traders on the New York Stock Exchange), or they would simply bum-rush the jetway and deadlock shoulder-to-shoulder at the airplane hatch or have access to their seat starved out by more agressive passengers.

The type of queue used by Continental is a relatively simple priority queue where passengers with a higher priority are always cleared before passengers of a lower priority, while multiple passengers of the same priority are serviced on a first-come, first-serve basis. The highest priority people in the Continental queue, aside from flight crew and airport personnel, are the first-class flyers and elite frequent flyer members. The second priority is for families with small children or those requiring extra time to get seated, such as those in wheelchairs or other physical challenges. The third priority is for standard frequent flyer members. The remaining peons are assigned lower priorities based on the distance of their seat assignment from the back fo the plane.

Obviously, the aim of this type of queue is not to file folks into the plane as quickly as possible, nor it is necessarily to be fair to all passengers. Though it nicely meters people through the boarding scanner, jetway, and hatch, it causes some stalls as higher priority passengers arrive late to the gate and a fair amount of contention for elbow room along the length of the aisle. By not uniformly filling the plane from window seat to aisle seat and from the rear of the plane forward, people get blocked on their way back to their seat while other passengers coopt the aisle to put their baggage in the overhead bins or let a latecomer into their row. Lower priority passengers suffer a much longer trip time to their seat and are in conflict for limited blankets, pillows, and storage space.

Other carriers, such as Southwest Airlines, implement a different form of priority queue that tries to be more fair to all passengers. People are segmented into one of five priority levels labeled A through E. For the most part, it people are assigned a priority upon check-in on a first-come, first-serve basis, though those with special needs may get a priority boost. Once at the gate, passengers queue up in separate lines reserved for each priority. Once boarding begins, everyone in A goes first, then B, and so on. Because Southwest does not have assigned seating, this system also creates significant aisle contention. Some people like windows, some like aisles, but nobody likes the middle. So windows and aisles fill up first, with the aisle folks generally having to get up and stand in the aisle to usher through the latecomers saddled with the middle seat.

A Survey of Solutions: From Weak To Weird

As I was waiting in line, I started thinking about how to speed boarding through increasing parallelism and lessening the bottlenecks on shared resources. The boarding problem looks a lot like a standard concurrency problem in disguise, with issues like fairness, bandwidth, arrival ordering, and resource contention in all of their glory. Imagine it as a stream of messages that need to get routed as quickly as possible to their destinations. At various points along the way, the messages get signed, transformed, filtered, and otherwise serialized. Messages at or near their destination require sorting, processing, and storage.

Obviously, there is a limit to how much performance gain we can get from choosing a different queuing algorithm. The ideal queue is one that loads the plan from window to aisle, from rear of the plane forward, with no exceptions, no latecomers, no preferred boarding. This reduces resource contention everywhere except in the aisle while folks load the overhead bins or take a little extra time inching to their seat. Short of eliminating carry-on baggage or the elderly and infirm, the airlines are not going to make much further progress this way and still keep their customers.

We could have multiple lines leading to multiple boarding pass scanners, but that would just cause a backup on the jetway. We could make a wider jetway that could handle four or more abreast, but then they would just back up at the hatch. Similarly, a wider hatch causes a back up at the aisle. A wider aisle is probably unrealistic, though, since the bean-counters at the airline would want to fill up the extra space with seats.

Thinking radical for a moment, we know that the best we could ever do would be to load everyone at exactly the same time. Imagine if we preloaded people in a 747-sized overhead scaffold and simply popped open the top of the plane and dropped them into their seats like a bowling pin setter at a bowling alley. Not practical, but it’s clearly our performance upper-bound.

Less radical is borrowing the methodology used by FedEx for loading and unloading cargo planes. FedEx planes are designed as empty hulls. Cargo is loaded into wheeled covered pallets whose cross-section is exactly the same shape as the interior of the plane but only about six to eight feet deep. When it’s time to load a plane, the handlers simply roll a bunch of these pallets in through the back of the plane like LifeSavers into a roll.

What if the airlines made seating pods of six rows each? While waiting for your plane to board, you could find your pod inside the airport, load your overhead bin, sit down and get comfortable. Once your plane was ready, the handlers would roll your pod and all the rest in through the back of the plane. The performance boost comes from drastically reducing jetway, hatch, and aisle contention increasing the numbers of paths to seats and by widening the window of time that passengers have to get seated.

How about you? Got any crazy ideas how to better board a plane?

Advertisements

15 Responses to “Analog Concurrency: Boarding a Plane”

  1. Alan Says:

    Marc,

    Any solution that added significant weight to the plane would likely be nixed on fuel considerations. I don’t know if FedEx uses pods that add to the structural integrity of the plane, but this might be a work-around.

    The pods are a good idea, though. Loading people and baggage in the same pod might reduce the whole baggage claim problem, as well as what seems like a resource-intensive baggage loading system. Plane to plane transfers might be speeded by segregating people by pod. The whole jetway/terminal system could possibly be eliminated, for that matter, with pods transported to planes by haulers.

    Using all the emergency exits is an idea, but I think the doors would have to be retrofitted, not to mention the jetways.

    I once had an idea similar to yours, for cross-country shipping by truck – use pods of various sizes that would interlock on the back of a standard semi, with the pods themselves forming the shell of the trailer. Select pods could be refrigerated. Robotic transfer stations across the country would transfer items from truck to truck that served mainly standardized routes. Computers would route, load and store the pods optimally. Pods could be warehoused enroute if desired, and sit at the customer’s facility for them to unload and even reload with finished goods at their leisure. It seems to me this could push efficient logistics down to the smallest customer. With round-the-clock operations, shipping cross-country could be quite speedy.

  2. A Pilot Says:

    Paint footprints containing a seat number on the floor with the back of the plane being closest to the jetway. There will be a small box next to each set of footprints that serves to test fit carry-on luggage. Luggage that is too big will be discarded. There will be no talking. When the gate agent blows the whistle a drum beat will commence and the cattle will march into the airplane. When at their seat they perform a seating procedure in four drum beats or less. The seatbelts cannot be unbuckled. There will be no talking until the no-talking sign is turned off, and then only at a whisper.

    Deplaning will use the same strategy as an emergency evacuation. The flight attendants will yell, and the last one off gets

  3. MooFanchu Says:

    Try googling WILMA (code name for united’s
    boarding scheme: window/middle/aisle)

    See a copy of a recent WSJ article here
    http://rakaposhi.eas.asu.edu/menkes-wsj-online.htm

    Your ideal queue assumes that every passenger
    is of the same “size” (i.e., no baggage,
    kids, elders, prams, wheelchairs etc). There
    may be something in sorting the passengers
    by their actual size: e.g., people travelling
    light board first and take window seats,
    or perhaps interleave passengers by size,
    or something else. But you have to take
    into acccount the blockage induced by any
    given passenger if you want to control
    contention.

  4. Leo Says:

    This is a good discussion of the problem. IMHO the analogy to message passing is slightly incorrect, though, because usually messages don’t interfere with each other as passengers do in the aisle. The possibilities for deadlock scenarios are almost endless, which is what makes this problem so difficult.
    My strategy for optimizing the _personal_ boarding experience is to sit in the lounge until the queue is nearly empty. I was once on an overbooked flight, and the staff asked me very nicely whether I would mind to use the business class because economy was full. Of course I had no objections ;-)

  5. Glenn Says:

    It’s not even that radical an idea. Planes are horrible places to be for an extended time and I suspect most people jostle for position when seats haven’t been allocated for 1 of two reasons:

    1) So they can have the extra leg room on a wing/exit seat
    2) So they can sit up the front and get off first

    Assuming this simple premise to be true, the answer to me seems fairly simple and just a reversal of what the airlines currently do. The passengers they (the airline) truly care about have paid the additional expense for the bigger seat, any that are left give preferentially to the frequent flyers on check-in. Fill the back of the plane first, let the valuable customers make the most of the more comfy lounges for a longer time.

    I don’t know why they insist on filling first/business first. Much like Leo, I stay in the lounge for as long as possible and ignore the call board first. I don’t see the point in paying more to utilise the lounger, having to leave early, just to be jammed into the plane and have the aisle beside me crowded with passengers for the next 30mins making it almost impossible to use a laptop effectively combined with some airlines not allowing them to be used until post take-off. It can easily equate to an additional hour I could be working on the laptop in greater comfort with no delay to anybody else.

  6. Marc Jacobs Says:

    MooFanchu: Thanks for the link. I guess it’s safe to assume that any moderately interesting problem has at least a handful of LaTeX/PS pages devoted to it. :)

  7. Marc Jacobs Says:

    Leo: The reasoning behind the analogy wasn’t that in-flight messages directly influence or compete with each other, but rather that services that process messages often have to serialize access to shared resources.

    For example, a message logging service might have to serialize access to a database table or file in order to record the message. A message transformation service (for example, to add digital signature or routing envelope or lookup keys for values) might require locks on a database or directory service in order to perform the transformation. You might also have a service that receives cumulative messages on a transport that does not guarantee order of arrival (such as market data over Tibco EMS or MMORPG state data over UDP). The service, much like a row on an airplane, can’t complete its work until all messages of a set arrive and can be placed into their correct order.

  8. Marc Jacobs Says:

    Panic posted a comment on reddit that with an interesting link to another study on airplane boarding. Thanks!

  9. Snappy! Says:

    Aye … Singapore airlines do adopt a slightly different boarding order.

    1. First Class, Business, Silver Kris etc
    2. Elderlies, parents with children etc
    3. Passengers seated at the rear end
    4. Passengers seated in the middle

  10. Tom Comeau Says:

    It occurs to me to take a step back and look at the meta-problem: Why are we in a hurry?

    Ignoring Southwest for a moment, the only scarce resource is overhead bin space. When I travel on airlines other than Southwest, I just make sure I’m able to get my Powerbook case under the seat, and I don’t carry anything else. Then I wait until the last possible moment before getting on the crowded, hot, smelly airplane. Particularly if I’m traveling with family.

    Southwest is an entirely different story, and I’d point out that Southwest has the shortest turn times in the industry. Open seating, with three to five boarding groups, is obviously “solved enough” so that putting people on the plane is not the problem. When I travel with my family, I make sure I’m in boarding group A, so we can grab a whole row.

    Airlines have an incentive to get you boarded quickly: Airplanes sitting still aren’t making money. But I can’t think of any significant incentive for me to board quickly.

    tc>

  11. Dan Ciruli Says:

    Southwest claims that their system is, in fact, faster than systems with assigned seats. According to what I’ve read, they feel that people do a *pretty*good* job at efficiently finding an available seat: if a particular row is obstructed, they will proceed farther down the aisle. It’s part of what allows them to turn planes around quickly (and there’s no denying they do that).

    This is sort of like a “pull” based distributed computing system: a row attracts a passenger (an agent asks for more work) when it’s ready (unobstructed).

    The problem is, of course, that the aisle is *almost* serial–it’s difficult to get by someone standing in the aisle.

    In Burbank, Southwest utilizes both doors in their 727s, front-and-rear. Adding parallelization to a scheme like this definitely increases its efficiency.

    BTW – you’ve got fewer than 20 posts ever, and this one generated about 15 comments? Wow!


  12. […] writes about parallel programming, especially but not limited to the .NET platform. Gems like his Analog Concurrency: Boarding a Plane I always find amusing and link-worthy. Be prepared that he has a very irregular posting frequency, […]

  13. Michael Randers-Pehrson Says:

    An improvement could be loading and unloading from opposite ends of the plane, like a queue instead of a stack. It might provide enough of an incentive to early boarders to move all the way to the other end of the plane before blocking the aisle.

    This would require two access points to the plane, but that could be managed with the same number of terminal jetways. This approach might also improve “in terminal” delays by using two separate gates to load and unload: Plane 1 is unloaded via gate A from the back while the jetway from gate B is preparing passengers to load from the front. When plane 1 is ready, passengers can board from gate B. When gate A is done unloading, it can be moved and prepared to load plane 2, which was unloaded via gate H (my terminal is designed to be a circle with passenger access via underground).


  14. […] but welcome nudge from fellow concurrency author Michael Suess in the form of a flattering pingback from his blog, Thinking Parallel. I had actually stumbled on and subscribed to his blog back in […]


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: