Cracking The Crew-Recovery Conundrum
A New Approach To Solving The Crew-Recovery Problem That Minimizes Disruption Impacts
Harsh storms in the northeastern United States played havoc with schedules, severely disrupting airline traffic during the winter of 2013-14. As the future unfolds, there are newer and more efficient data-analysis and optimization techniques that can help carriers recover from irregular operations in a much quicker timeframe.
Throughout time since the early days when commercial flying began, the causes of disruptions in airline schedules have been many and varied. But particularly harsh winter storms that severely affected traffic of all types in the northeastern United States made January 2014 the worst month for flight disruptions in recent history.
According to masFlight (a prominent aviation operations data warehouse and Big Data analytics platform), airlines operating in the United States suffered heavy impact from the storms — canceling approximately 49,000 flights in January and delaying an additional 300,000 flights.
Best guesses and calculations placed airline losses in January 2014 that were directly attributable to the brutal winter weather in a broad but undeniably costly range of between US$75 million and US$150 million.
A significant part of the storm cost was spent in the documented process of rerouting flight crews — and paying crew overtime wages.
Considering operational losses caused by delays alone, Airlines for America (A4A — formerly ATA, the Air Transport Association of America) has estimated full-year 2012 incremental crew costs for U.S. passenger airlines at US$1.5 billion. Clearly, crew operational efficiency during disruptions has an extremely critical economic impact on airlines.
Furthermore, due to the complexities of crew scheduling, restrictive legalities and real-time mandates, crew schedule recovery is one of the most difficult problems that must be solved in the entire realm of operational recovery.
Currently, the crew-recovery process is heavily dependent on human experience and judgment, even though those hands-on figures and calculations can be highly constrained in terms of cost effectiveness.
During the January 2014 winter storms, airlines in the northeastern United States were affected the most, with an extremely high percentage of canceled flights.
This semi-disastrous weather situation resulted in an utterly overwhelming volume of manual work by crew-services experts to process the cancellation package and repair the crews’ schedules.
Clearly, a powerful automated and optimized crew-recovery tool is in high demand to reduce workload and substantial economic losses.
Traditional Crew-Recovery Approaches
An airline crew’s published roster line includes a series of assigned pairings, plus other items such as administrative ground activity, training, leave and so forth.
A pairing is a sequence of duties that starts and ends at a crew base. The duties in a pairing, each of which represents roughly a day’s worth of flying, are separated by periods of rest, and are composed of a sequence of flights. A crew’s published roster line is the output and ultimate result from the crew-planning stage.
During the day of operations, disruptions such as inclement weather, mechanical problems, ground delays and crew unavailability make it impossible to carry out the scheduled plan.
The primary goal of crew recovery is to repair disrupted roster lines while making sure all flights have the crews needed to operate them and return the airline back to normal operations as quickly and efficiently as possible.
Crew disruptions are usually addressed through application of the following tactics:
- Use crewmembers who are on reserve or standby — In addition to regular flying crews, most airlines maintain additional crews that can be called out during irregular operations.
- Deadhead (reposition) crews — Airlines can use their own or other airlines’ flights to reposition crews back to the base or to their next flight. When ground transportation is available for nearby airports, limo or shuttle service can also be used for repositioning.
- Swap flying among disrupted and non-disrupted crewmembers — To recover from the disruption, it is often necessary to use crewmembers who were not initially affected by the disruption. A non-disrupted regular crew is called a move-up crew.
There are few disruption-management tools available in the industry, and many airlines are still manually applying recovery tactics (such as those described) for crew recovery.
Detailed guidelines and procedures may be developed to help with the manual process. And different airlines have different crew-recovery guidelines. Furthermore, even within the same airline — and guided by the same procedures — different “crew trackers” (those who solve the disrupted crew problem) can come up with different ways to repair the disrupted crew schedule, which causes inconsistencies.
An automated disruption-management tool that combines the strengths of both operations research and the computing system figures to be best for dealing effectively with these highly combinational circumstances.
However, the crew-recovery problem still represents an extremely challenging conundrum due not only to its combinational nature, but also to the complex business settings and real-time airline requirements when recovering from irregular operations.
Among the automated crew-recovery tools applied within airlines or in academic studies, some use a “buy-time” approach. As the name of this approach indicates, the near-term disruptions that have occurred in a crew’s current duty or pairing are given top priority and repaired first. This buys the airline time to deal with more of the disruption issues at a later time — including those potential new issues that have been created while fixing the near-term disruptions.
Other tools apply a two-step approach — that is, to repair the disrupted pairings first, and assign the newly created pairings to the crews’ roster lines later. When repairing the disrupted pairings, the airline’s scope of attention is across the entire disruption period. Thus, the two-step approach is different from the buy-time approach, and is based on a different problem-decomposition strategy.
All these described approaches, although practical, lack a holistic view of the crewrecovery problem, which can result in unsatisfying crew-recovery solutions, with additional uncovered flights or unrepaired crews.
An inefficient crew-recovery solution will induce further flight delays, extra cancellations and inevitably high disruption costs.
Crew Recovery Solution
Sabre AirCentre Recovery Manager (Crew) is built on an advanced IT infrastructure and a user-friendly application interface. The crew recovery solution obtained from solving the optimization problem can be displayed nicely by showing both input and modified schedules for each crew. It can provide an intuitive view of how disrupted crew schedules are repaired, as well as how reserve, move-up crew and repositioning flights/limos are used to help with the recovery.
Advanced Problem Solving
With traditional crew-recovery approaches, airlines still struggle to recover from disruptions in the crew department.
Some airlines have one or two automated crew-recovery tools installed but find them difficult to put to practical use due to the large gap between system capability and realistic requirements.
More than a decade ago, Sabre Airline Solutions® started out with a different focus to solve the hugely complex crew-recovery problem — beginning with a customer council to help define the primary objectives and the important business rules and requirements related directly to crew recovery. In addition to the technology company’s research group, academic institutes, such as the Georgia Institute of Technology, joined the team to evaluate and experiment with different solutions options.
With a thorough understanding of business requirements and complexities, the combined team set forth to develop a holistic crewrecovery approach that leverages simultaneous pairing and roster recovery (as compared, for example, to the two-step approach, which addresses only one aspect at a time).
A holistic approach affords a carrier the opportunity to take a broader view of the crewrecovery problem, as well as more accurately addresses the elusive yet central objective of minimizing the impact of disruptions on an airline’s crew operations.
Through the customer council mentioned above, three critical objectives were identified:
- Minimizing the time to get all crew back on plan,
- Minimizing the total number of off-plan operations,
- Minimizing the total number of crew reassignments.
Each objective addresses a unique aspect of the disruption impact. The objectives can be applied individually or in combination, with different weight factors for each according to business needs.
Along with the primary objectives, this approach also incorporates other controls and costs to define the preferences of one solution over another. In Sabre Airline Solutions’ real-life test cases, for example, repositioning penalties were added to manage deadhead and ground travel, crew-usage penalties were implemented to control the tradeoff between reserves/standbys and move-up crew, and controls were developed to restrict instances of whether “non-fly” activities (e.g., training, days off, etc.) can be replaced by “fly” assignments (e.g., operating a flight or repositioning).
Throughout the design of the holistic approach, many other realistic situations and requirements were put into play so the crew-recovery decision-support tool would be flexible, capable and powerful.
Deadhead limits, for example, can be enforced to control the maximum number of seats taken by repositioning crew on each flight, while standby limits can be added to restrict reserve usage (and to thereby prevent reserve shortages in the future).
In accordance with real-life airline practices, crews can be located at a temporary base during specific time periods, or have pairings start and end at co-terminal stations. For reserve crew, some airlines have order-of-assignment rules to determine which crewmembers should be assigned new pairings.
Every extension, enhancement and addition to the business requirements entails one extra level of complexity in building mathematical models and solving the problem.
To capture all government, contractual and airline rules, it’s essential to build a separate and flexible rules engine, and to make sure the problem-solving engine can be seamlessly integrated with that rules engine.
All these factors make the optimization engine extremely configurable and flexible, enabling the solution of both pilot and flight attendant recovery problems for different airlines, despite different rules.
The configurability, flexibility and capability to support realistic business requirements are critical factors in determining whether an automated decision-support tool can be adopted in solving real-life airline day-of-operation problems and solving them in a holistic manner.
This new, holistic view of crew recovery leads to advanced problem-solving techniques.
Applying Operations Research Methodology
Crew recovery is an optimization problem that aims at minimizing the disruption impacts by using all allowed recovery tactics to repair disrupted roster lines while making sure all flights have the crews needed to operate them.
In most cases, the options for recovering crew are innumerable — typically, there could be hundreds of crew on reserve or standby, tens of thousands of repositioning choices and several thousand non-disrupted crewmembers.
If a mathematical model were designed to take into account all these alternatives, the model would be overwhelmingly massive and complex. Considering the time and hardware constraints, solving the problem would be both impractical and computationally intractable.
It is critical to design the right operations research methodology and techniques to intelligently determine the right scope of the problem — so as to generate quality solutions in a realistic timeframe.
An important aspect of how the right scope of the problem must be defined is the concept of a recovery window, which is a time interval that dictates the horizon within which the mathematical model will be permitted to make modifications to crew assignments. The model generates assignments that have continuity with the rosters before and after the recovery window.
Another aspect of how the right scope of the problem must be defined is the selection of proper repositioning choices, non-disrupted crew and other crew on reserve and standby.
These problem-reduction techniques serve to seriously limit the potential explosion in numbers of alternatives, while at the same time retaining all of the ideal candidate recovery solutions.
Even after the reduction, the crew-recovery problem can still be vast. Therefore, special care must be applied in modeling and solving such large-scale optimization problems as those involved in crew recovery.
A mathematical optimization model is formulated containing a set of decision variables, an objective function and a set of constraints that define the feasible region of the decision variables. The decision variables in this crew-recovery model are valid assignments through the recovery window for each crew.
The objective function is to minimize the total crew-assignment costs, which are, among other things, a weighted sum of the three primary business objectives.
The primary constraints include the coverage requirements for operating flights, as well as for each crew to have one valid assignment.
Typically, this is a model with more decision variables than constraints.
To solve an optimization problem is to find values for the decision variables that achieve the optimal or near-optimal objective-function value.
Holistic Optimization Approach To Crew Recovery
A simulated Hurricane Sandy disruption scenario was created based on real airline data that involved two days east coast shutdown in the United States. It comprises more than 600 cancelled flights and more than 900 disrupted crew schedules. Using the holistic optimization approach, within reasonable time, all crew schedules were back on plan in less than 3 days with more than 99 percent open-flight coverage and disrupted crew-recovery rate.
In most cases, it is impractical to cope with all possible crew assignments directly via a single, all-inclusive model. Therefore, Sabre Airline Solutions has developed a new operations research method for decomposing and solving this complex large-scale problem.
In solving such models, a delayed-column-generation method based on Dantzig-Wolfe Decomposition is a suitable algorithm. In general, the algorithm iteratively solves a restricted master problem and its corresponding pricing problems.
The restricted master problem uses a much smaller subset of feasible crew assignments as decision variables. And the dual optimal solution, which is derived from solving the restricted master problem, is used in the pricing problems to generate better crew assignments for constructing the next restricted master problem.
This mathematical process must be repeated until no better crew assignments can be found (indicating, in mathematical terms, the arrival at an optimal solution to the crew recovery problem).
To overcome the potential convergencespeed issue, which is typically found in a column-generation algorithm, Sabre Airline Solutions collaborated with Georgia Tech and adopted the primal-dual subproblem method, which was originally developed by Georgia Tech mathematicians.
On that basis, Sabre Airline Solutions has developed its own delayed-column-generation approach, utilizing the power of both the primal-dual subproblem and Dantzig-Wolfe Decomposition.
The resultant algorithm has a dual-improvement step at each iteration and generates a large number of suitable columns at each iteration (instead of just a few good columns, as in most calculations that are based more directly on the Dantzig-Wolfe Decomposition).
In this manner, the number of iterations needed to reach optimality is greatly reduced, thus speeding up the process and opening the door to being able to solve even larger problems.
Ideal Crew-Recovery Solution
A progressive crew recovery tool is essential in quickly absorbing disruptions and reducing their impact. A recovery tool needs to demonstrate fast response times, the ability to take into consideration a wide variety of recovery tactics and the capability to handle all kinds and magnitudes of disruptions. The crew-recovery tool should also solve large disruption scenarios, as well as effectively manage day-to-day operational disruptions.
Applying cutting-edge operations research advancements, Recovery Manager (Crew) uses a holistic optimization approach to solve complex crew-recovery problems. It leverages simultaneous pairing and roster recovery and provides airlines with superior recovery solutions. With this approach, directly deployable crew rosters can be generated, greatly improving an airline’s response time to disruptions and reducing operational costs.
The holistic approach can handle a broad range of disruption scenarios that can be as small as an open flight or pairing assignment dropped by a sick crew, or they can be as large as major airport shutdowns.
In short, the operational efficiency gained through the holistic, optimization-based crew-recovery solution enables airlines to gain a competitive edge in the marketplace — and to better serve their customers, which is the ultimate goal and achievement of all airline procedures.