Former UW grad student Jason Steffen got a wee bit irked on a flight a few years ago. Which led to this:
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 an improved passenger boarding scheme.
While you will not find the article in Phys Rev, it will hopefully be found in a future issue of the Journal of Air Transportation Management.
February 7th, 2008 at 3:44 pm
This is cool stuff - for those interested, there’s also a New York Times article on the general subject - and it turns out airplane boarding was one of the Mathematical Contest in Modeling problems from last year.
February 7th, 2008 at 4:54 pm
And yet, they still tell you to go to the nearest exit in case of an emergency.
February 7th, 2008 at 5:36 pm
Taking a shower in some hotels can be an uncomfortable experience too. One such bad experience by a grad student and/or her supervisor probably led to this paper
February 7th, 2008 at 6:17 pm
As much fun as this problem is (and we’ve all thought about it waiting to board) I am a little disappointed to see that this particular author didn’t see the need to read (or even look for) any existing literature!
A simple search on Google Scholar (e.g. airplane passenger boarding) will throw up research papers and patents from the early part of the decade and later part of the last. Isn’t science supposed to be about building on the shoulders of giants, not re-inventing the wheel?
From what I can tell… it seems this is a complete re-implementation of “Reducing passenger boarding time in airplanes: A simulation based approach” by Van Landeghem & Beuselinck in 2000 (i.e. do lots of random samples, and pick the best one! Not a particularly scalable solution). But with a lot less rigour.
This proposed solution is also ridiculously difficult to implement in real life… what would have really impressed me would have been a simple heuristic approach that improves on the current situation, but yet offers no additional complications to ground staff operations. Instead, this paper investigates a wholly unworkable near-optimal solution.
February 7th, 2008 at 9:14 pm
It is my understanding that traffic jams and other bottlenecks of that sort are analogous to phase transitions.
Lawrence B. Crowell
February 7th, 2008 at 10:15 pm
See also
http://www.cs.bgu.ac.il/~ebachmat/managesubmit.pdf.
Look at the end of page 2/ beginning of page 3 page, and see how space-time enters the picture.
February 7th, 2008 at 10:41 pm
Also see http://www.cam.cornell.edu/~rfrongillo/mcm/
The paper is a little rough due to the whole thing (from seeing the problem, writing the code, and the paper) was done in 4 days Hopefully a cleaner version will end up on the arxiv some time in the near future. (We had been planning to do it anyway, but this is just extra motivation)
February 7th, 2008 at 11:14 pm
Jetblue has the best solution. They open up both back and front of the plane, and board the zones in the middle first. They end up saving a lot of money according to the stewards i’ve asked about their relative speed =)
February 8th, 2008 at 12:45 am
I don’t see why it would be so difficult to implement the suggested boarding technique. It still amounts to putting letters on tickets and saying “now boarding tickets marked “A”).
As far as improving the time, what I would do would be to give some benefit, perhaps a cash discount, or points, or a better meal, or whatever, to those passengers who checked one bag. The idea is that you need to make flying more expensive for people who insist on loading all their personal belongings into the cabin.
February 8th, 2008 at 1:19 am
“As much fun as this problem is (and we’ve all thought about it waiting to board) I am a little disappointed to see that this particular author didn’t see the need to read (or even look for) any existing literature!”
Disappointing? Yes.
Surprising? Sadly, no.
February 8th, 2008 at 2:38 am
The only problem with the two door solution is that it is only usable in places where you can have passenger access directly to the tarmac (as opposed to via a jet way). The budget airlines in Europe apparently open both doors and just say “get on” with no assigned seats. It should also be noted that one of the major renovations needed for airports to accept the A380 is a dual jetway set up.
February 8th, 2008 at 1:50 pm
“As far as improving the time, what I would do would be to give some benefit, perhaps a cash discount, or points, or a better meal, or whatever, to those passengers who checked one bag. The idea is that you need to make flying more expensive for people who insist on loading all their personal belongings into the cabin.”
Oh, if only. Ryanair’s (the most successful budget airline, IIRC) charge you if you want to check baggage, necessitating you carry all your belongings in the cabin (as one only flies Ryanair if you’re very cheap, and the price of baggage check is quite often more expensive than the ticket).
February 8th, 2008 at 3:43 pm
Checked bags weigh more, costing more fuel. It’s a compromise. But United seems to think that they save money by having people carry on.
February 9th, 2008 at 11:54 am
The ability to board early - and therefore find overhead space above your seat - is considered a perk by frequent travelers. Such travelers are the ones that the airlines are catering to, and they typically avoid checking bags whenever possible. The concept of minimizing boarding time is close to irrelevant to major carriers. So from an operational point of view the topic of the paper is a yawn.
February 9th, 2008 at 5:30 pm
[…] do caos aéreo, USA: “Using a Markov Chain Monte Carlo optimization algorithm and a computer simulation, I find […]
February 9th, 2008 at 7:34 pm
“The concept of minimizing boarding time is close to irrelevant to major carriers. So from an operational point of view the topic of the paper is a yawn.”
This is flat wrong. Southwest has said that adding 5 minutes average to their turn time would cost them $972 million more a year (not counting crew costs) and require 18 more planes. to maintain their service level NYT article (granted it is old, but the order of magnitude is likely still right)
The distinction that matters is long haul vs short haul. For trans-pacific flights turn time is basically irrelevant, but for short haul flights the 30 minutes on the ground at either end start to matter a lot. Say you have a plane on a route where it is an hour gate to gate. If you are rotating crews you can run at least 12 legs a day (southwest averages ~6 turns which means 8 legs per 737 per day as of 2006 so some are likely hitting this number). If you now take 5 minutes off each turn time that gets you an extra flight per day per plane which means an extra flight of profit with out the overhead of more planes.