Optimization in Airline Integrated Planning and Operations
Part I: Robust Planning

George L. Nemhauser (george.nemhauser@isye.gatech.edu)
School of Industrial and Systems Engineering, Georgia Institute of Technology

Download slides here (gzipped PostScript file).

1. This has been an ongoing plan in research project at Georgia Tech involving the NSF and most major US airlines. Planning usually starts 6 months to 1 year before a flight and lasts till the day of the flight.
3. The research has focused on building of the mathematical model and the optimization part.
4. OR/opt. is not yet much involved in 1. Creating the schedule. OR/opt. is very much involved in part 2. Allocate Resources. The resource allocation problem has been split into 4 subproblems a-d which have been solved seperately. Preferably they should be integrated but generally such models are too complicated, some attempts towards integrations have though been made.
5. Q (Nemhauser): Delta has 500 airplanes, how many do you suppose are waiting on the airport in case something comes up?
   A (Audience): 10? 5? 3?
   A (Nemhauser): 0, airplanes are to expensive to have idle.
   Airlines do all planning assuming best case (will fly schedule). Robust planning- planning assuming disruptions, has proven to be very tough.
6. Airlines are the beggest test bag for large scale integer programming in industry. "These guys really care about optimization".
7. The basic model used is a time line network and the modeller needs to track 3 flow streams, airplanes, passengers and crews.
   Usually a weekly time line is needed but people mostly use a daily time line. Usually airlines have the same schedule for all weekdays but somewhat different on weekends.
8. Airlines plan their US domestic flights in a hub and spoke model. Airlines usually have 3-7 hubs and if you want to fly between two non hub cities you usually have to change flights in a hub city.
   The choice of these hubs is a network design problem and has not been looked at from a optimization standpoint. The number of choices would be enormous.
9. Fixing can be expensive, weekly problems are generally to big.
10. The rotation problem is scheduling what individual planes will do. Look at individual airplane types and which particular plane to use.
11. Different types of planes have the same capacity.
    • Planes are enormously expensive resources.
    • Fleeting used to be solved by local opt. (Developed by ATT/Karmakar).
    • When the researcher first approached this problem they conjectured that in a fleet of 500 airplanes they should be able to do fleeting with at least 1 or 2 fewer planes if problem was solved to optimality.
    • However when minimizing the number of planes they came up with the same number as where being used.
    • This was due to the fact that when the fleeting problem had been solved then if a plane was doing nothing a segment would be added.
12. Airplane types are the commodies.
13. The computational results are old. The fleet assignment problem may be considered a solved problem.
14. Here we need to restrict to the same plane being used midday and late night since the crews are not in the model. The same crew can not be used to fly different types of planes.
16. Fleeting with time limits/ time windows on departure time.
    Revenue is considered to be flight leg based but most passengers take more than one flight in the hub based model. An itenerary based fleeting is needed, this was approached in a recent thesis at MIT.
17. Ellis (Johnson) has a Ph.D. student working on a set of fare classes problems.
18. Bid price is a dual variable.
    Q (Audience): In the model you are using continuous variables but customers are coming in discretely, do you know this to be a good approximation?
    A (Nemhauser): Most pairs have very small demand (often less than 1) and also demand tends to come in groups. So either you ignore this or solve w/wo group.
    Wouldn't expect uniqueness of dual solution, another possible version would be to have linear concave functions based on probability. They don't have so much degeneracy but no dual.
    This is definetely an open area.
    Q (Audience): Do you use interior point methods to solve? A (Nemhauser): Essentially subgradient? A (Birch): This model is better than a nonlinear model.
19. Rotation: Look at single fleet (type of airplane) and pair by individual planes the arrival and departure.
    The airlines impose the condition that of all flight legs given to a given plane each plane should fly every one.
    Q (Audience): Why do they impose this condition?
    A (Nemhauser): So all planes have the same physically experience, i.e. we have regularity of tear so they have the same maintainance demands.
20. It is possible to combine the rotation and the fleeting problem.
    Q (Audience): Is the number of hours of maintainance different between types of airplaines?
    A (Nemhauser): Not much different.
21. Each crew member has a base. We prefer that the crew is spends most of its night at its homebase, else way have to provide them with a hotel etc.
22. Example of two day pairings for a crew. The max number of days a crew is on the road is usually 4 to 5 days.
23. Daily problem, enumerate pairings, in reality total enumeration is never done.
24. Solved by using a lot of cheap pairings and then 1 or 2 expensive.
25. Need to solve a shortest route problem.
26. After solving the daily problem we look at flights that are not 7 days a week.
27. Crew scheduling solution still has little robustness. The cost of overnights used to be 8-9% of crew costs, in solution cost of overnights are 1-2% but in reality the costs of overnights is 7-8%.