I am in Paris attending the CPAIOR (Constraint Programming/Artificial Intelligence/Operations Research) conference. I was the co-Program chair for this, which means my work is done, but now I get to see how good the papers we accepted are. On the whole, things are very good, with a surprise or two (each way!).
Cindy Barnhart of MIT was the plenary speaker this morning, talking about challenges and opportunities for OR in the airline industry, with an emphasis on plane and crew scheduling. Cindy has been working on airline applications for 20 years, so she has a wealth of experience to bring to this. She began with her view on what aspects of mathematical modeling are most useful in this application area. In her view, two key aspects are
- Composite variables: defining variables to include complicated structures. For instance, instead of just having a variable for the number of planes on a particular leg to meet demand, the variable would be choices of combinations of planes, with the variable being 1 if that combination is used. While this leads to more variables, the resulting models are much easier to solve, since their linear relaxations are closer to being integer.
- Implicit formulations: Instead of including all levels of variables, include only the highest level variable, but add constraints so that there is a feasible assignment for the other variables. For instance, instead of including all individual planes, only have a variable for the number of planes of a particular type. Add some constraints so that once the number of planes is known, individual planes can be feasibly assigned.
This lead to the question, then, “Why are things so bad”? Why is on-time service down, and why are people so angry at airlines (particularly in the US)? It is clear that planned schedules don’t correspond to actual. How can models help to close that gap? Cindy offered a wealth of models and insights:
- Creating robust schedules. The key idea in this model is to give more slack to planes more likely to be delayed. Surprisingly, even without changing the schedule, it is possible to reduce delays simply by the assignment of planes to legs: in essence, make sure planes coming in from San Francisco (where delays due to fog are common) are assigned outgoing legs a little later than an identically arriving plane from Phoenix. These delays can be reduced quite a bit more by slightly (up to 15 minutes) modifying the schedule.
- Auctioning for landing slots. Surprisingly in the US, at almost all airports there is no coordination among airlines in their schedules, so far too many planes arrive or leave in a short period, overwhelming the airport capacity. It seems obvious that slots should be auctioned off so that airport capacity is not violated.
- Dynamic Scheduling. Predicting demand on any particular leg on a particular day is clearly one that is approximate at best. As demand comes in, it is possible to change the capacity between cities by, for instance, changing a flight so that a formally illegal connection is now legal. Of course, this must be one-way: all previously purchased connections must remain legal. An airline could even “refleet” a flight, by changing the plane to a larger one or a smaller one to meet demand (in this case, the airline crew must still be legal for the flight, and these changes propagate through the system as the “wrong” planes continue through). Even minor changes (no more than a 15 minute move) can increase the profitability of a schedule by 2-4%, with most of the gain through schedule changes, not refleeting.
- Passenger-Centered recovery. In case of a “disruption” (a storm or other issue), airlines face the problem of getting planes, crews, and passengers back to normal as quickly as possible. Normally airlines treat the problem in that order: get the planes in the right place, then get the crews, then worry about the passengers. What if airlines combine all three and try to minimize average customer disruption while getting planes and crews back on schedule? It is possible to greatly reduce the average passenger delay but the airlines might have to delay a plane that is ready to go. So the delay of “undisrupted” customers will go up a bit in order to greatly reduce the delay for “disrupted” customers. That is going to be a hard step for an airline to do.
Nice talk, but it made me think that airlines are harder to work with than the groups I normally work with.
I disagree with the issue of inconveniencing undisrupted passengers just a little bit to help the others. In my experience, a tiny disruption often leads to delays of half an hour or more because push-back crews get reassigned and departure slots get lost. Also, the airlines currently have a strong incentive to leave the gate on time since that’s what defines an on-time departure. Much better would be to take into account when the plane actually takes off.
The “little bit” is about half an hour: the goal is primarily to avoid overnighting delayed passengers. You are right about the push-back crews: models like this do need to take the whole system together.
And I do agree with your comment on the measures, though I am sure the airlines would argue that time between pushback and takeoff is largely out of their control.
Re #2: Congestion pricing (perhaps in some way combined with slot restrictions) seems to be an economically efficient way to take care of capacity bottlenecks. But as with many OR-based ideas, it runs into institutional and political hurdles, as well as a certain amount of FUD. For instance, on his influential air transportation blog, Don Brown voices his skepticism thus:
What measures out well in simulations doesn’t always translate cleanly to the political reality of the US airspace system.
-Sanjay
You are right about the push-back crews: models like this do need to take the whole system to gether. And I do agree with your comment on the measures, though I am sure the airlines would argue that time between pushback and takeoff is largely out of their control.
**************************************************
jack888
Florida Drug Rehab