Crew Scheduling in the Airline Industry

1. Introduction

The airline industry has been a significant force behind the economic development owing to its operations and impact on related industries like tourism and aircraft manufacturing. It also provides an important mode for business and leisure travel. For airline companies, passenger ticket is the main source of revenue, while the major expenses include crew, fuel, maintenance, and equipment purchase cost. Data indicate that the largest expense is labor cost which accounts for approximately 30% of the overall cost, followed by regional and fuel costs, which collectively accounts for 30%. The split of the cost for American Airlines for 2020 Q1 is shown in Figure 1. Front-line line workers, including the crew (pilots and flight attendants), account for approximately 70% of the overall workforce for an airline. In the current competitive airline industry, minimizing the crew cost is an essential task, as it can lead to significant savings. Additionally, the emergence of low-cost carriers like Allegiant, Spirit, and WOW airlines has increased the pressure on legacy airlines to optimize the system to provide affordable tickets to passengers for leisure travel. As a result, the airline crew scheduling problem has received much attention in both industry and academia recently.

Figure 1. Expense distribution for American Airlines for 2020 Q1.

Kasirzadeh et al. [2] define airline crew scheduling as “the problem of assigning a group of crew members to a set of scheduled flights such that all the scheduled flights are covered, while the rules and collective agreements, imposed mainly by safety and labor organizations, are respected.” These complex restrictions make crew scheduling one of the most difficult scheduling problems in the field of operations management.

Major US airlines schedule 500 flights daily to over 150 destinations with a fleet size of ~800 aircraft. The scheduling operation involves the assignment of pilots and flight attendants for each leg of the flight. Doing this requires scheduling of around 5000 pilots and 10,000 flight attendants on a monthly basis, subject to FAA rules on safety protocols, airline-specific rules, and labor union contract rules. The problem has become increasingly complex over the last two decades, and airlines are now relying more on automated mathematical scheduling models instead of manual deployment. During the COVID-19 pandemic, this problem has been further exacerbated. On an average, 90% of the flight schedules were slashed within a month (March 2020), and crew scheduling and recovery became a nightmare for most of the airlines due to enforced mandatory quarantines in many states/countries, as crew was not able to return to their base location. In this article, we will talk about how airlines mathematically formulate the crew scheduling problem using the tools of optimization. Before we get into crew scheduling modeling, a brief introduction to mathematical optimization is provided.

2. Introduction to optimization

Mathematical optimization/programming is defined in Wikipedia [3] as “the selection of a best element (with regard to some criterion) from some set of available alternatives”. In other words, the problem involves selection of values from a predefined set which maximizes or minimizes a real function. There are different forms of modeling an optimization problem depending on the nature of the best value that is to be selected, and the real function that is to be optimized. Linear and integer optimization are two of the most widely used optimization modelling approaches, and are used to formulate the crew scheduling problem in this article.

Linear optimization/programming is the simplest or the most basic form of optimization. The optimization problem involves an objective function which is being maximized/minimized using the variables. The variables are subjected to constraints which are a set of equations which place limit on how big or small the variable can get. The nature of the variable defines what kind of optimization problem it is. In case of linear optimization, the variables can take any real value (integer or fractional) within the feasible region defined by the constraints. All other optimization programming involves decomposing the given problem into its linear form. One application of linear optimization is in the planning of dietary needs where nutritionist try to calculate the food needed (in kg) to provide nutrition at low cost.

An example of linear program modeling is illustrated in figure 2. The function which is being maximized is 12f + 9s. The set of constraints defined by Equation (1)-(4) impose limit on how large the variables f and s can get. If there were no constraints, both f and s could take value infinity to maximize the function. However, constraint (1) ensures that the maximum value that variable f can take is 1000 while constraint (2) ensures that the maximum value that variable s can take is 15­00. Constraints (3) and (4) enforces limit on linear combination of variables f and s. The intersection of the four constraints defines the feasible region, as highlighted by the grey region in the figure. The optimal value which maximizes the function can now only be selected from this feasible region.

Figure 2. Illustration of modelling of linear programming [4].

In integer programming, the variables can take only integer values in contrast to real values as in case of linear programming. The feasible region of the problem defined above would reduce to only integers enclosed by the bounded set of constraints in case of integer optimization, and is shown by red dots in Figure 3. One way to solve integer programming problems is by rounding the values of the solution obtained by solving the corresponding relaxed linear model. However, this enforces additional challenges. In such cases, it becomes pertinent to check all possible permutations of the solution obtained by rounding the solution from linear model for optimality. However, this simplification creates an issue where the optimality of the solution is not guaranteed. One application of integer optimization is in crew scheduling. In crew scheduling, we assign the whole of a crew to a flight, since assigning fractional crew is meaningless. We use this modeling approach to model the crew scheduling problem in the next section.

Figure 3. Illustration of the feasible region for integer programming.

3. Crew scheduling

Crew scheduling is only one of the many challenges faced by airline industries in their planning process as shown in Figure 4. The planning process starts with schedule generation in which flights that will be flown to different destinations are determined. Once the schedule has been generated, depending on the demand of the corresponding market, aircraft (such as Boeing 737, Airbus 320, etc.) are assigned based on their capacities. The idea is that the capacity and the frequency of a flight should meet the demand of the market. The next step is the maintenance routing in which flights are scheduled to return to one of their maintenance hubs after flying for a set number of hours (usually 50 hours) for maintenance purposes as mandated by the FAA. Finally, crew scheduling completes the planning process.

Figure 4. Process flow leading to crew scheduling.

The crew scheduling problem is solved in two steps: 1) crew pairing and 2) crew assignment. In the crew pairing problem, flights are paired depending on the locations they fly to, the time, and the day of the week of the flight.

Pairing is defined as the sequence of locations and layovers (origin-destination-origin-destination-layover-origin-destination-) for the flights as shown in Figure 5. Once the flights are paired, crews are assigned to the pairs depending on crew preference (decided by seniority) and the aircraft that they are qualified to fly. For a given pair, the crew is supposed to stay together. In Figure 5, all the members of the crew start from Dallas on day 1 on a flight and return back to Dallas at the end of day 2 on the same flight. It is important to note that in crew pairing, only flights are paired, i.e., the locations that the flight will fly to, while the actual assignment of the crew to these flights take place in the crew assignment step. In this article, we expound only on the crew pairing step.

Figure 5. An example of pairing.

The concept of set partitioning method is used to formulate the crew pairing problem. This method involves finding the minimum cost subset such that every flight segment is included in exactly one chosen pairing. To achieve this, we formulate the problem as an optimization model where we minimize the cost of pairing. Let F be the set of flight segments to be covered (a pair of origin and destination constitutes one element of the set) and let P be the set of all feasible pairings. In table 1, we have 7 different flight segments which make the set F. Examples of valid pairs pEP are {flight 4, flight 1, flight 2}, {flight 5, flight 6, flight 2, flight 3} and {flight 4, flight 6, flight 7}. A valid pair is a collection of flight segments which ensures that the flight returns back to its origin. Let c be the pairing cost. Decision variable y is equal to 1 if pairing p is included in the solution, and 0 otherwise. Hence, the decision variable y is a binary integer.

Table 1. A sample example of flight schedule.

We formulate the crew pairing problem as an integer optimization problem shown below [5]:

In the above problem, we minimize the cost of pairing of flights, which is represented by the objective function in Equation 1. While minimizing the cost, we ensure that each flight leg is considered in only one pair as constrained by equation 2. This ensures that we do not cover the same origin-destination twice through different crew.

We see that the model resembles a typical integer optimization model explained earlier. Once the problem has been formulated, it can be solved using exact algorithms like branch and bound, column generation, or using evolutionary based heuristics. There are different commercial solvers available that implements these algorithms to generate optimal solutions. Once the crew pairing is determined by solving the above optimization problem, it is used as an input for crew assignment, which is the last step in the operations planning. It is important to note that manual interventions can still be needed to make adjustments to the schedules generated by solving the problem due to variety of reasons. One possible situation is in case of delay, when the assigned crews are not yet at the required airport. In such cases, crew from backup are manually deployed.

4. Conclusions and further reading

In this article, we explained the importance of crew scheduling in achieving operational efficiencies and highlighted the associated complexity. To address the issue of manual assignment of crew, we modeled the crew scheduling as an optimization problem that can be solved using commercial solvers. For further reading, we direct the interested readers to explore the topic of crew recovery which was in limelight during the COVID-19 pandemic. Crew recovery deals with recovery of crew when the usual operation is disrupted because of bad weather. In such situations, crew are stranded in the middle of their duty period, and will miss the connecting flight in their duty-period because of the delay in their current flight leg. In such cases, the crew scheduling is redone to ensure minimum disruptions in the remaining schedule of the crew.

5. Acknowledgement­­­­­

I would like to thank Ankur Gupta and Deepak Vasisht for their thoughtful feedback and suggestions in improving the article.

6. References

[1] http://s21.q4cdn.com/616071541/files/doc_news/assets/2020/1Q-2020-Financial-Results.pdf

[2] Kasirzadeh A, Saddoune M, Soumis F (2017). Airline crew scheduling: models, algorithms, and data sets. European Journal of Transportation Logistics.

[3] https://en.wikipedia.org/wiki/Mathematical_optimization

[4] Michael Ferris CS 524 class notes.

[5] Notes on airline crew scheduling by Cynthia Barnhart.