A new twist on boarding order algorithms
Mar 5, 2008, 4:35 pm
#1
Moderator: New York City and FlyerTalk Evangelist
Original Poster
Join Date: Sep 2007
Programs: AA PLT, Natl EC
Posts: 10,855
A new twist on boarding order algorithms
As we know, many (most?) airlines now board by groups in an inverted pyramid, back-to-front. A new analysis by Jason Steffen using modified Monte Carlo simulations suggests that patterns involving boarding by every other row would make it easier for people to store their luggage, thereby speeding the boarding process by 2-fold or more.
There was a news article on this in Nature last week:
Strict ordering slashes tarmac time
In case you can't access the Nature article (a subscription may be required), I'll try to reproduce the boarding schemes below. The first is the strictly ordered option, which provides the most improvement. Acknowledging that this is impractical, the author also examined a number of modified schemes, including the second shown below that uses blocks.
The preprint of the primary article can be accessed here:
Optimal boarding method for airline passengers
Most of this seems pretty impractical to me ("I'm sorry sir, your group number is 58 and your wife's is 83; we've only called group 27"), and, of course, F, elites, and other preboards would interfere, but I thought it was interesting nonetheless. I wonder if the airlines use similar analyses but, perhaps, weigh the practical issues more heavily in selecting the inverted pyramid scheme.
There was a news article on this in Nature last week:
Strict ordering slashes tarmac time
Steffen characterized each sequence in terms of the difference in seat number for successively boarding passengers. He assumed that each passenger needed at least one free space either in front of or behind them to stow their luggage. The best distributions turned out to be those in which the highest fraction of passengers had an empty row separating them from those admitted before and after them, ensuring that there was enough stowing room between successive individuals. In other words, what matters is not the absolute seat positions in the sequence, but where those seats are relative to each other.
Code:
Strictly ordered (fastest option)
30 10 29 09 28 08 27 07 26 06 25 05 24 04 23 03 22 02 21 01
middle (etc.) -------------------------------43 62 42 61 41
aisle (etc.) ----------------------------------------------
FRONT BACK
aisle (etc.) ----------------------------------------------
middle (etc.) ---------------------------------------------
40 20 39 19 38 18 37 17 36 16 35 15 34 14 33 13 32 12 31 11
Compromised option using blocks
3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1
3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1
3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1
FRONT BACK
4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2
4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2
4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2 4 2
Optimal boarding method for airline passengers
Abstract
Using a Markov Chain Monte Carlo optimization algorithm and a computer simulation, I find the passenger ordering which minimizes the time required to board the passengers onto an airplane. The model that I employ assumes that the time that a passenger requires to load his or her luggage is the dominant contribution to the time needed to completely fill the aircraft. The optimal boarding strategy may reduce the time required to board and airplane by over a factor of four and possibly more depending upon the dimensions of the aircraft. I explore some features of the optimal boarding method and discuss practical modifications to the optimal. Finally, I mention some of the benefits that could come from implementing and improved passenger boarding scheme.
Using a Markov Chain Monte Carlo optimization algorithm and a computer simulation, I find the passenger ordering which minimizes the time required to board the passengers onto an airplane. The model that I employ assumes that the time that a passenger requires to load his or her luggage is the dominant contribution to the time needed to completely fill the aircraft. The optimal boarding strategy may reduce the time required to board and airplane by over a factor of four and possibly more depending upon the dimensions of the aircraft. I explore some features of the optimal boarding method and discuss practical modifications to the optimal. Finally, I mention some of the benefits that could come from implementing and improved passenger boarding scheme.
Mar 5, 2008, 5:00 pm
#3
Join Date: Oct 2000
Location: BKK when I'm not in Princeton
Programs: UA MP:1P for life, TG:Gold, CO:Gold
Posts: 2,017
Great article, thanks for the post
I enjoy these sorts of models. In this case, the author apparently considered people as behaving as discrete, random particles. I'm not sure if that would be the best basis of a model, since the motion of individuals in close proximity to each other are affected by the motions of their nearest neighbors. That effect is often modeled as a finite reaction time, or signal speed, among particles (people) modeled as a continuum. Cars on a highway are also modeled that way, with the net result that a the cars behave as a predominantly one-dimensional supersonic compressible fluid, exhibiting analogous behavior to a decrease in flow area (e.g. lanes ending and the flow slowing), increases in in duct area (adding an extra lane which generates in increase in speed), shocks (accidents), expansions (light turning green)... I point this out because an interesting continuum model, motivated by the interesting work by the author of the cited work, may be formulated to further refine and deal with boarding-time predictions based on different schemes.
One thought that does come to mind regarding the present work is that the status of pax would have to be removed, and groups broken up - to randomize the process - for such an approach to be implemented. That may not be something that would be immediately salable and accepted
I enjoy these sorts of models. In this case, the author apparently considered people as behaving as discrete, random particles. I'm not sure if that would be the best basis of a model, since the motion of individuals in close proximity to each other are affected by the motions of their nearest neighbors. That effect is often modeled as a finite reaction time, or signal speed, among particles (people) modeled as a continuum. Cars on a highway are also modeled that way, with the net result that a the cars behave as a predominantly one-dimensional supersonic compressible fluid, exhibiting analogous behavior to a decrease in flow area (e.g. lanes ending and the flow slowing), increases in in duct area (adding an extra lane which generates in increase in speed), shocks (accidents), expansions (light turning green)... I point this out because an interesting continuum model, motivated by the interesting work by the author of the cited work, may be formulated to further refine and deal with boarding-time predictions based on different schemes.
One thought that does come to mind regarding the present work is that the status of pax would have to be removed, and groups broken up - to randomize the process - for such an approach to be implemented. That may not be something that would be immediately salable and accepted
Mar 5, 2008, 5:07 pm
#4
Moderator: New York City and FlyerTalk Evangelist
Original Poster
Join Date: Sep 2007
Programs: AA PLT, Natl EC
Posts: 10,855
Interestingly, in Fig 7 of the paper, totally random boarding is nearly as efficient the modified optimal approach and window-middle-aisle groups.
I agree - it seems an overly simplified model, which is why I wonder if the airlines might have something that takes more of the issues you mentioned into account.
I agree - it seems an overly simplified model, which is why I wonder if the airlines might have something that takes more of the issues you mentioned into account.
Mar 6, 2008, 1:32 pm
#6
Join Date: May 2007
Location: IAD
Posts: 2,060
I think the irrationality of the human psyche makes these computer models pretty useless. For example, I doubt the models would have predicted some flights I've had that boarded back-to-front as normal, but with the result that halfway through boarding, the back of the plane was fully seated and the front half of the plane's overhead compartments were all full....
Mar 6, 2008, 2:13 pm
#7
Moderator: New York City and FlyerTalk Evangelist
Original Poster
Join Date: Sep 2007
Programs: AA PLT, Natl EC
Posts: 10,855
Mar 6, 2008, 2:14 pm
#8
Join Date: Oct 2000
Location: BKK when I'm not in Princeton
Programs: UA MP:1P for life, TG:Gold, CO:Gold
Posts: 2,017
I think the irrationality of the human psyche makes these computer models pretty useless. For example, I doubt the models would have predicted some flights I've had that boarded back-to-front as normal, but with the result that halfway through boarding, the back of the plane was fully seated and the front half of the plane's overhead compartments were all full....
The problem at hand - passenger boarding - represents a so-called complex adaptive system, where elements of the system (passengers) find solutions (storing luggage) based on their previous experience. Those previous experiences (e.g. non-early-boarders waiting to store luggage in a hopefully open stowbin close to their seat, when seated in the rear of the plane, and subsequently finding a lack of available storage space) provide feedback which modifies the passenger's future actions (for example, passengers deciding to utilize first-available stowbins). This sort of stuff can be modeled, and then compared to real-life, with a subsequent adjustment of the model, which can then be used to investigate a large range of different (boarding) scenarios.
Perhaps arcane, but interesting nonetheless.
Mar 6, 2008, 5:48 pm
#9
Join Date: Oct 2007
Posts: 561
I think the irrationality of the human psyche makes these computer models pretty useless. For example, I doubt the models would have predicted some flights I've had that boarded back-to-front as normal, but with the result that halfway through boarding, the back of the plane was fully seated and the front half of the plane's overhead compartments were all full....
No model is going to be best for every situation, but in general computer models can be very helpful abstractions. Computer queuing models led to the current single waiting line approach at bank tellers, for example -- when I was a kid, lines formed behind each teller, and you hoped that the people in front of you didn't have complex transactions. The assumptions used by a model can always be questioned and tweaked, but sometimes you find rather robust results that aren't very susceptible to changes in initial conditions.
Mar 6, 2008, 7:41 pm
#10
Moderator: New York City and FlyerTalk Evangelist
Original Poster
Join Date: Sep 2007
Programs: AA PLT, Natl EC
Posts: 10,855
4 Robustness of the Optimal
4.2 Random Shifts and Swaps
If pairs of passengers are swapped, which effectively randomizes portions of the line, then the time to board the airplane can change significantly. Indeed, a 20% increase in the boarding time results from randomly swapping only 10% of the passengers—that is 6 pairs for the case of 120 passengers. However, there is an upper limit to the effect of swapping passengers since once they are completely randomized additional swaps maintain the random nature of the passenger order and the ordering doesn’t get any worse. To completely randomize the optimal ordering one must swap at least 60 pairs of passengers. It is unlikely, even in the worst of cases, that so many of the passengers would be out of order. Interestingly, random boarding takes much less than half the time of the worst case boarding; indicating that randomization is not catastrophic. Indeed, we will see in the next section that random boarding compares favorably with traditional boarding techniques.
4.2 Random Shifts and Swaps
If pairs of passengers are swapped, which effectively randomizes portions of the line, then the time to board the airplane can change significantly. Indeed, a 20% increase in the boarding time results from randomly swapping only 10% of the passengers—that is 6 pairs for the case of 120 passengers. However, there is an upper limit to the effect of swapping passengers since once they are completely randomized additional swaps maintain the random nature of the passenger order and the ordering doesn’t get any worse. To completely randomize the optimal ordering one must swap at least 60 pairs of passengers. It is unlikely, even in the worst of cases, that so many of the passengers would be out of order. Interestingly, random boarding takes much less than half the time of the worst case boarding; indicating that randomization is not catastrophic. Indeed, we will see in the next section that random boarding compares favorably with traditional boarding techniques.
Oct 31, 2011, 1:30 pm
#11
FlyerTalk Evangelist
Join Date: Dec 2009
Location: HaMerkaz/Exit 145
Programs: UA, LY, BA, AA
Posts: 13,167
Airlines Are Trying to Cut Boarding Times on Planes
The Cattle Call at Gate 15 Is Taking Longer and Longer - NY Times
Interesting read. I still wonder what the best way to board planes is.
I find CO for example, who group all of the elites/premium cabins together, to be better than UA, who have so many distinctions (F/GS, C/1K, 1P, *G/2P... and that's before regular boarding)!
The CO approach basically takes the random for the elites before starting regular boarding. I personally have never had trouble finding overhead space when boarding early with EliteAccess, even though tons of elites board then.
Interesting read. I still wonder what the best way to board planes is.
I find CO for example, who group all of the elites/premium cabins together, to be better than UA, who have so many distinctions (F/GS, C/1K, 1P, *G/2P... and that's before regular boarding)!
The CO approach basically takes the random for the elites before starting regular boarding. I personally have never had trouble finding overhead space when boarding early with EliteAccess, even though tons of elites board then.
Oct 31, 2011, 1:34 pm
#12
Join Date: Jan 2010
Location: Aussie in ORD
Programs: Marriott Plat, Ua Gold, GE.. Sucker for punishment
Posts: 4,237
Checked-baggage fees have only added to the problem, because travelers now bring more roll-ons onboard, blocking the aisles as they try to cram their belongings into any available space.
The airlines do not mind if boarding takes a little longer because all the extra fees have been a major benefit for their bottom lines. They collected $1.6 billion from checked bags alone in the first half of 2011, about the same as the first half of last year, according to the Department of Transportation.
Oct 31, 2011, 1:38 pm
#13
Suspended
Join Date: Sep 2006
Programs: AAdvantage PP
Posts: 13,913
The Cattle Call at Gate 15 Is Taking Longer and Longer - NY Times
Interesting read. I still wonder what the best way to board planes is.
I find CO for example, who group all of the elites/premium cabins together, to be better than UA, who have so many distinctions (F/GS, C/1K, 1P, *G/2P... and that's before regular boarding)!
The CO approach basically takes the random for the elites before starting regular boarding. I personally have never had trouble finding overhead space when boarding early with EliteAccess, even though tons of elites board then.
Interesting read. I still wonder what the best way to board planes is.
I find CO for example, who group all of the elites/premium cabins together, to be better than UA, who have so many distinctions (F/GS, C/1K, 1P, *G/2P... and that's before regular boarding)!
The CO approach basically takes the random for the elites before starting regular boarding. I personally have never had trouble finding overhead space when boarding early with EliteAccess, even though tons of elites board then.
Oct 31, 2011, 1:45 pm
#14
Join Date: Jan 2010
Location: Aussie in ORD
Programs: Marriott Plat, Ua Gold, GE.. Sucker for punishment
Posts: 4,237
One thing that Virgin Australia does (or did) was use the front and rear of the plane for boarding... those up the back exited the terminal via stairs and entered the AC via the rear doors (I remember the old "time to split" sign)
I guess rules here in the USA prohibit pax from walking outside the terminal...
I guess rules here in the USA prohibit pax from walking outside the terminal...