Topics in Airline Planning

Talk presented by Richard E. Stone Senior Consultant, Operations Research

Northwest Airlines

 

Abstract:

In many ways a major airline can be viewed as one large planning problem which is usually approached as many interdependent smaller (but still imposing) planning problems. The list of things which need planning seems endless: crews, reservation agents, luggage, flights, through trips, maintenance, gates, inventory, equipment purchases. Each planning problem has its own considerations, its own complexities, its own set of time horizons, its own objectives, but all are interrelated.

In this talk, we will briefly look at a few of these airline planning problems. For each, we will outline the basic problem, considerations, and objectives. In addition, for each planning problem we review, we will discuss how one might quantitatively approach the problem so as to intelligently support the planning process.

At the IMA Industrial Problems Seminar on January 30, 1998, Richard Stone reported on airline planning problems. In many ways a major airline can be viewed as one large planning problem that is usually approached as many interdependent smaller but still imposing planning problems. The list of things that need planning seems endless: crews, reservation agents, luggage, flights, through trips, maintenance, gates, inventory, equipment purchases. Each planning problem has its own considerations, its own complexities, its own set of time horizons, its own objectives, but all are interrelated.

In this talk Dr. Stone looked briefly at a few of these airline planning problems, outlining for each the basic problem, considerations and objectives. In each case he discussed how one might quantitatively approach the problem so as to support intelligently the planning process.

It takes hundreds of people many months to make an airline schedule. The following can be thought of as a check list of the high-level issues to be decided in building an airline schedule.

 

• Markets.

To which airports should the airline fly? 

• Frequency.

For each airport, how much service should the airline provide?

• Hubs.

Which airports should be used as hubs? A hub is an airport used as a central connecting point for traffic.

• Fleet Planning.

Which types of aircraft should the airline purchase? How many of each type? 

• Banks.

To maximize the number of possible connections and, hence, the number of "city pairs" it serves, an airline tends to organize the hub flights into banks. A bank consists of several dozen planes which: (1) all arrive close in time, (2) pause to let passengers change planes and then (3) all depart close in time. Exactly how many banks there should be, when they should occur, and how they should be structured, are important issues involved in designing an airline schedule. 

• Timing.

Exactly when during the day should the flights serving the various airports arrive and depart? 

• Block Times.

The block time is the time between when a plane leaves the gate at the departure airport and enters the gate at the arrival airport. Since many factors can delay a flight, the larger the scheduled block time, the more likely that the flight will arrive ontime. However, larger block times also mean fewer flights can be scheduled and higher costs per flight. Achieving an appropriate balance is another issue involved in designing an airline schedule. 

• Fleet Assignment.

Which type of plane should be used for each leg? (A leg is a nonstop flight.) Clearly, we would want the larger planes to service the legs with the larger demands. This requires forecasting that future demand. It also requires assigning fleets to legs that best cover the demand given the operational constraints of the schedule. 

• Through Flights.

When a plane is part of a bank, it will service one of the arrivals into the bank and one of the departures out of the bank. A passenger traveling on both that arriving flight and departing flight does not have to change planes to make the connection. This type of connection is called a direct flight or through flight. Passengers tend to prefer direct flights rather than regular connections. Therefore, planning must be done, given the arrivals, departures, and other considerations, so as to create those through flights that would attract the most passengers. 

• Planned Maintenance.

The schedule must ensure that, on a regular basis, each plane stays overnight at a maintenance base for a minimum period of time.  

• Meal Service.

The level of meal service must be decided for each flight. 

• Crew Planning.

Pilots and flight attendants must be scheduled in a manner that meets federal, airline, and union regulations, in addition to ensuring that each flight can be flown. 

• Gate Plotting.

At an airline's hubs, when many planes will be on the ground at once, the problem of parking all the planes simultaneously can be quite difficult. There are several physical and operational considerations to take into account in addition to such goals such as minimizing the distance passengers and luggage must travel within the airport. 

• Station Manpower.

This involves the scheduling of the many people working at the airports. This includes both the customer service personnel helping passengers in the terminal as well as ground service personnel handling the aircraft on the ground. 

• Recovery.

As with all things, even if all the above planning is done as well as possible, many factors cause deviations from the plan. Recovery is the day-to-day concern of returning to plan as smoothly as possible.

 

Some of these problems are not mathematically tractable. For a more detailed analysis Dr. Stone selected one of these problems that is tractable mathematically:

 

Crew Planning

Compared to most of the other planning problems listed, crew planning is relatively easy to model mathematically and interpret as an optimization problem. Still, efficiently solving the model and producing a practical crew plan can be quite complicated. In the following, we will be concerned with the flight crew (pilots), but similar issues arise when dealing with the cabin crew (flight attendants).

 Airline crews do not follow normal 9-to-5 work days. The actual work day for a crew member can start at any time during the day (or night) and can be somewhat longer or shorter than 8 hours. Such a work day is called a DUTY PERIOD and consists of briefings, flight legs, ground time, and debriefings. A work week, that is a sequence of duty periods separated by overnight stays, is called a TRIP or PAIRING. A trip must start and end at the crew member's home base. There are many federal, airline, and union rules regarding duty periods and trips. These dictate the maximum amount of time within a duty period that a pilot can spend flying a plane. These, also, dictate the minimum amount of time that overnights between duty periods can be depending on the length of previous overnights, the amount of flying a pilot has done, and the type of flying that was done, e.g., flying a red-eye flight requires more rest time.

Normally pilots are paid for the total block time (see above) of the flights that they flew. However, the rules dictate that a pilot must be paid a certain amount over and above this total block time depending on how the duty periods and trips are structured. A flight leg that a pilot flies is called a LIVE flight for that pilot. When pilots fly on legs as passengers during a duty period, so as to get to the next live flight, they are said to DEADHEAD on that leg. The rules can dictate that the pilots must be paid for DEADHEAD flights. Also, the rules can dictate that pilots must be paid a certain minimum for duty periods and/or trips, and this minimum can be an absolute amount and/or a percentage of the total time of the duty period and/or trip. This extra amount that pilots are paid above the total block time is called the PENALTY and represents the inefficiencies contained in the crew plan. The object of crew planning is to design a set of trips that follow all the rules, ensure that each leg in the schedule has a crew to fly it, and minimizes the penalty.

We say that a trip is LEGAL if it satisfies all the various rules. A step towards modeling the crew planning problem would be to define a binary matrix A whose rows represent the flight legs in the schedule and whose columns represent all possible legal trips. The element A_ij would equal 1 if flight leg i is a live flight for trip j. Otherwise, A_ij would equal 0. We next determine a vector c such that c_j is the total crew cost associated with trip j. The crew planning problem can now be stated mathematically as:

 

Find a binary vector x such that Ax =1, while minimizing c'x.

 

This type of problem is called a SET PARTITIONING problem. If the rules dictate that pilots must be paid the same for deadhead flights as for live flights, then we can define A_ij to equal 1 if flight leg i is a flight for trip j, either live or deadhead. The model now becomes:

 

Find a binary vector x such that Ax     1, while minimizing c'x.

 

This type of problem is called a SET COVERING problem. The advantage is that we do not have to specify to the model which flight legs in each trip are to be live. Notice that two trips with the same flight legs, differing only by which legs are live, are represented by the same column in the set covering problem but by different columns in the set partitioning problem. Thus, the set covering problem will be much smaller and, hence, easier to solve than the set partitioning problem. The disadvantage, of course, is that the airline would be paying more penalty if the pilots were paid the same for deadhead flights as for live flights.

Both set partitioning and set covering problems are special cases of INTEGER PROGRAMMING problems. Integer programming problems are difficult restrictions of the easier to solve LINEAR PROGRAMMING problems. Some texts treating linear programming and integer programming are:

 

George B. Dantzig and Mukund N. Thapa,

Linear Programming 1: Introduction,

Springer Series in Operations Research,

Springer-Verlag, 1997.

 

George L. Nemhauser and Laurence A. Wolsey,

Integer and Combinatorial Optimization,

Wiley Interscience Series in Discrete Mathematics and Optimization,

John Wiley & Sons, 1988.

 

Harvey M. Salkin, Kamlesh Mathur, and Robert Haas,

Foundations of Integer Programming,

North-Holland, 1989.

 

Alexander Schrijver,

Theory of Linear and Integer Programming,

Wiley Interscience Series in Discrete Mathematics,

John Wiley & Sons, 1986.

 

Ariela Sofer and Stephen G. Nash,

Linear and Nonlinear Programming,

McGraw-Hill Series in Industrial Engineering and Management Science,

McGraw-Hill, 1996.

 

James K. Strayer,

Linear Programming and its Applications,

Undergraduate Texts in Mathematics,

Springer-Verlag, 1989.

 

Stanislaw Walukiewicz,

Integer Programming,

Mathematics and its Applications,

Kluwer Academic Publishers, 1990.

 

We can see from the above analysis that, in principle, the crew planning problem can be completely solved. In practice, however, the number of possible legal trips is several dozen orders of magnitude larger than can be efficiently dealt with by any modern computer. Of course, we don't need all the possible legal trips; we only need the ones that make up the optimal solution. While this last observation is overly simplistic, it does suggest a practical iterative strategy for dealing with the large number of legal trips.

We could start by generating several thousand legal trips by some heuristic method for selecting "good" trips, e.g., those with low amounts of penalty. Using these generated trips, we can obtain a reasonable crew plan by solving a reduced version of one of the above integer programs. From the economic information provided by the optimal solution to this reduced problem, we can formulate a secondary mathematical problem (usually a constrained SHORTEST PATH problem) whose solution will produce good legal trips that fit in well with the trips we already have generated. Thus, we expand the list of trips used in the reduced integer program and obtain an optimal solution giving a better crew plan than the one we first produced. In fact, we can use the information we obtained when first solving the reduced integer program to obtain a "jumpstart" when resolving the problem with the new trips.

Clearly, the above scheme can be iterated until a close to optimal crew plan is generated. This general approach, using a secondary problem that iteratively generates the columns of a linear or integer program with a great many columns, is called COLUMN GENERATION. More information on column generation and its use in solving crew planning problems can be found in the following references.

 

R. Anbil, C. Barnhart, L. Hatay, E.L. Johnson, and V.S. Ramakrishnan.

"Crew-pairing optimization at American Airlines Decision Technologies,"

Optimization in Industry, T.A. Cirani and R.C. Leachman (eds.),

John Wiley & Sons, pages 31--36. (1993)

 

C. Barnhart, E.L. Johnson, R. Anbil, and L. Hatay.

"A column generation technique for the long-haul crew assignment problem."

Optimization in Industry II, T.A. Cirani and R.C. Leachman (eds.),

John Wiley & Sons. (1994)

 

The term "long-haul" in the above paper refers to long international

flights. The problems are smaller (fewer legs) but highly constrained

with less flexibility.

 

S. Lavoie, M. Minoux, and E. Odier.

"A new approach for crew pairing problems by column generation with an application to air transportation,"

European Journal of Operational Research, Volume 35, pages 45--58. (1988)

 

P.H. Vance, C. Barnhart, E.L. Johnson, and G.L. Nemhauser.

"Airline crew scheduling: A new formulation and decomposition algorithm,"

Operations Research, Volume 45, Number 2, pages 188--200. (1997)

 

An older version of this paper is available by ftp:

ftp://ftp.eng.auburn.edu/pub/pvance/papers/crew_paper.ps

 

 

Here are some further issues to think about:

Pilots can only fly the specific type of aircraft for which they are currently trained. The fleets an airline owns can be partitioned into classes with each pilot being currently trained for exactly one class. This means that we must solve several crew planning problems, one for each class of aircraft. This is good since it is generally easier to solve several smaller problems than one large problem. However, a pilot can deadhead on any type of aircraft, and can deadhead on other airlines' flights. Thus, while the rows of the matrix A consist of the flight leg for one airline scheduled to be flown by the planes of one specific class of aircraft, the number of columns can grow enormously if we allow for the possibility of pilots deadheading on any flight of any airline. What is the best way to model this flexibility inherent with deadheading?

Trips must start and end at a pilot's home base. There are usually several crew bases with differing numbers of pilots based at each. This imposes a hidden constraint on the problem. If x% of the pilots are based at airport XXX, then we really need to have about x% of the total block time included in trips which start and end at base XXX. How can this requirement best be incorporated into the above model?

Can one develop a "perturbation theory" for the crew planning problem, so that the effect on the optimal crew plan of a slight change in an airline's schedule can easily be determined?

Scheduling is done so that the planned penalty is kept under 1%. However, in practice the actual penalty experienced tends to be higher than the planned penalty due to the usual deviations in plan the airline is forced to make in real-time. Is there a concept of "robustness" so that with robust scheduling the actual penalty more closely follows the planned penalty?

 

Inventory Management

 

Dr. Stone also discussed a planning problem outside of the realm of scheduling the airline. Once a schedule is in place, an airline must now sell tickets to the traveling public in order to stay in business. The problem of trying to get the most revenue from the sale of tickets goes by several names: INVENTORY MANAGEMENT, REVENUE MANAGEMENT, or YIELD MANAGEMENT.

The passengers flying in the same cabin of the same flight of the same plane pay a variety of different fares. For example, for the coach cabin, there are full coach fares (Y class), slightly discounted coach (M class), deeply discounted coach (Q class), super saver (K class), and frequent flyer (free). Airlines naturally want to maximize the fare revenue for each flight. It would greatly help if passengers showed up in decreasing order of fare. The airline could then sell tickets on a first-come first-served basis and know that those passengers who showed up too late to obtain a ticket (because the flight filled up) were the passengers representing the lower fares. In fact, however, passengers tend to show up in the reverse order, with fare increasing! Thus, seats must be saved for the late-coming higher fare passengers if an airline is to gain more revenue. The question is how best to do this in an organized manner.

One method used in trying to maximize revenue on a flight is the system of NESTED BOOKING LIMITS. Such a system works as follows. Suppose we have 100 coach seats for a flight that we wish to book in the four classes K, Q, M, and Y. We want to limit the number of lower fare tickets booked for the flight so that there will be seats available for passengers paying higher fares. This is the Nested Booking Limits concept. If we let K, Q, M, and Y denote not just the fare classes but the number of bookings the airline will accept in each of these respective classes then, for example, we might impose the booking limits (assuming no overbooking):

 

K     38,

K + Q     71,

K + Q + M     87,

K + Q + M + Y = 100.

 

We could look at this problem from a second viewpoint, that of protecting seats for the higher paying passengers, rather than limiting seat to lower paying passengers. This is the NESTED PROTECTION LEVELS viewpoint, which is basically equivalent to nested booking limits. Let K, Q, M, and Y denote the number of seats we will reserve for each of these respective classes. In our above example, the corresponding nested protection levels are:

 

Y = 13,

Y + M = 29,

Y + M + Q = 62,

Y + M + Q + K = 100.

 

How should these protection levels be set? If they are too low, some high paying passengers may be lost. (The passengers are said to be SPILLED.) If they are too high, some seats may not be sold. (The seats are said to be SPOILED.) The problem is that airline seats are a perishable product. Once a plane takes off, all empty seats can no longer be sold. The problem of PERISHABLE ASSET REVENUE MANAGEMENT is faced by any company selling a perishable product, e.g., airlines, hotels, newspapers, fruit stands.

Here is one approach to set the levels. The reader will see that the approach could be modified in many ways and that there are many complications that deserve study. We begin by forecasting, based on history and experience, the distribution of the demand for Y class tickets. We can then plot the reverse cumulative distribution curve for Y class tickets. Denote this curve as P(n). By "reverse" we mean that P(n) is the probability that there will be at LEAST n passengers willing to buy Y class tickets for the flight under consideration.

 If Y is the price of a Y class ticket then Y × P(n) is the expected marginal seat revenue (EMSR) for Y class passengers. Thus, the EMSR curve is just a rescaling of the reverse cumulative distribution curve. Denote this Y class EMSR curve as E_Y (n). We can use the E_Y (n) curve to determine the Y class protection level by choosing n such that E_Y (n) equals M, the price of an M class ticket. (Note that we are approximating that actual discrete EMSR plot by a continuous curve; seats are sold as units.)

What about the next protection level? Suppose that, in addition to our forecast of the demand for Y class tickets, we have a forecast for the demand for M class tickets. Ideally we would convolve these demand distributions and rescale the resulting reverse cumulative distribution curve by Y to get E_Y+M. (We rescale by Y as the marginal spilled passenger will be a Y class passenger as, by assumption, they show up last.) The protection level for ,Y + M would then be the value of n for which E_Y+M equals Q, the price of a Q class ticket.

 However, the ideal is hard to obtain. The convolution requires that we know how the Y class demand and M class demand are correlated when it is hard enough to estimate these distributions as it is. A simple heuristic would be to find n1 and n2 such that E_Y(n1) equals Q and E_M(n2) equals Q and then use n1 + n2 as the protection level. Clearly,there should be room for improvement. Here are some references for those interested in exploring this further.

 

P.P. Belobaba.

"Application of a probabilistic decision model to airline seat inventory control,"

Operations Research, Volume 37, pages 183--197. (1989)

 

P.P. Belobaba.

"Optimal vs. heuristic methods for nested seat allocation,"

Proceedings of the AGIFORS Reservations and Yield Management Study Group,

Brussels, pages 28--53. (1992)

 

P.P. Belobaba and L.R. Weatherford.

"Comparing decision rules that incorporate customer diversion in perishable asset revenue management situations,"

Decision Sciences, Volume 27, Number 2, pages 343--363. (1996)

 

S.E. Bodily and L.R. Weatherford.

"Perishable-asset revenue management: Generic and multiple-price yield management with diversion."

Omega, Volume 23, pages 173--185. (1995)

 

L.R. Weatherford and S.E. Bodily.

"A taxonomy and research overview of perishable-asset revenue management: Yield management, overbooking, and pricing."

Operations Research, Volume 40, pages 831-844. (1992)

 

K. Talluri and G. van Ryzin.

"An analysis of bid-price controls for network revenue management."

Manuscript. (1996)

 

  

About the speaker:

 Richard Stone received a S.B. in mathematics from M.I.T. (1977), an M.S. in statistics from Stanford (1980) and a Ph.D. in operations research from Stanford (1981). From 1981 through 1986 he was on the faculty of the Harvard Business School in the area of managerial economics. From 1986 through 1991 he worked in the department of operations research at AT&T Bell Laboratories. Since 1991, Dr. Stone has been a senior consultant with the operations research and management division of Northwest Airlines.