Tuesday, September 15, 2009

Finest Moments of Operations Research - This Day 8 years ago

The second half of September in 2001 was among the finest moments for Operations Research practitioners. For various reasons, these fact is unknown even within the OR community, so this story is worth retelling, even if it has to be from this insignificant virtual outpost of O.R. This story is about a bunch of unknown OR guys in United Airlines. Similar stories are likely to told about other large US carriers as well (Continental has even published some of this in a conference/journal).

There is chaos everywhere on Sept 15th, 8 years ago, since many are uncertain if there are going to be more attacks. In an order with little precedent, no planes are allowed to fly in the U.S for three days. Planes over North America on 9/11 are forced to land at the nearest feasible airport, and thus crews and aircraft are strewn all over the continent (For example, a small airport/town in Newfoundland played host to thousands of passengers and many large airplanes during those days and many were accommodated in people's homes. There was an interesting movie about this on Canadian television).

The larger Airline carriers chalked up huge losses with little to no revenue coming in. Around the 15th of September, flights are allowed to resume. Airlines are faced with mammoth decision problems. How to build a new airline schedule from scratch for thousands of flights, and crew schedules for tens of thousands of crew members to safely get through the next few days?

How to do all of this in the safest and most cost-effective manner?

Airline planning/optimization tools in Airlines are typically designed toward building schedules a month or two in advance. Since these schedules are built so early, the actual pilots and aircraft that operate these schedules are assigned much later by other systems. So the O.R guys in the airline were brought together and given these tasks:

a) building a new optimization model that would construct a new airline and crew schedule

b) such that the schedule was feasible, safe, and bring all the crew members back from all these remote airports to their domiciles in a safe and cost-effective manner and then reassign them to new flights

c) assign all pilots by name to these schedules

d) solve this O. R problem that is about 100 times more complex than what is normally seen in airline business, and do all this in 3 days

e) hook up the model to the on-line (real-time) database for input, and to the real-time crew-recovery system residing in main-frame computers for output in a seamless manner

The O.R guys (comprising of more than 10 nationalities) responded in an amazing manner. working day and night shifts on a 24 hour clock, a group of about 10 O.R PhDs just out of college invented brand-new airline scheduling models (unpublished to this day - they don't look pretty but were darned effective and had several cool innovations). IT engineers hacked away to rig up a flawless I/O hookup. Their effort was no less amazing as they had to overcome many unforeseen challenges. For example, it was found that many of these airports where crews were stranded were minor ones using alphanumeric codes, whereas in 2001, large US airlines served airports that no numeric characters in their names!)

There were lucky breaks and heartbreaks along the way. It was discovered that the real-time crew recovery system could not delete existing flight attendant assignments, and therefore, our new optimization models were 'over-covering' many flights. However, in the days after 9/11, flight attendants (mostly women) had no protection against terrorists in the main cabin and therefore, about 60% called in sick. This canceled out the over-covering effect and some how, the whole thing worked. It was an amazing sight to see the very first United flight come back home to Chicago after 9/11. The pilot obtained permission to fly over the United HQ and dip his wings in a show of unity, and it was beautiful.

In between, there were bomb threats that led to at least two evacuations. Then the grim reality that the junior OR guys would lose their jobs due to crippling airline losses. Despite all this, an unassuming bunch of young OR practitioners saved the day for United. After that experience, no real-life O.R problem was scary enough.

Everybody fights terror their own way, but the OR way is likely to be the most efficient.

8 comments:

  1. A very nice and moving account, Shiva. Thanks for sharing.

    ReplyDelete
  2. thanks for visiting and reading this post !

    ReplyDelete
  3. very interesting post Shiva. Revived memories of some crisis situations (not with OR though)

    ReplyDelete
  4. very nice, dee. a crisis is too valuable a thing to waste!

    ReplyDelete
  5. Thanks for sharing this nice account dealing with OR side of 9/11

    ReplyDelete
  6. thanks for posting this...I still remember those nights in the office on this effort.

    ReplyDelete
  7. hey anand: i'm really glad you got a chance to read it. It was an unforgettable experience, but I hope no OR guy is required to do that ever again ...

    ReplyDelete

Note: Only a member of this blog may post a comment.