Crew scheduling approach based on crew "duty-ing" problem

The crew scheduling problem is well known as the most difficult combinatorial problem, almost impossible to solve without decomposition. Typically, the crew scheduling problem decomposes into crew pairing problem (CPP, paring) and crew assignment problem (CAP, rostering). We propose another decomposition approach. In one first stage, the crew "duty-ing" problem (CDP), we find a set of duties and partially assign pilots to that duties. In the second stage, the Crew pairing/assignment problem (CPAP), we connect these duties into pairings and assign the crew members. Both stages are solved using a MILP solver. Such an approach aims to avoid the combinatorial explosion of pairing generation and leave as many as possible key decisions to the MILP solver.

Airline Crew Pairing Optimization Framework for Large Networks with Multiple Crew Bases and Hub-and-Spoke Subnetworks

Crew Pairing Optimization aims at generating a set of flight sequences (crew pairings), covering all flights in an airlines' flight schedule, at minimum cost, while satisfying several legality constraints. CPO is critically important for airlines' business viability considering that the crew operating cost is second only to the fuel cost. It poses an NP-hard combinatorial optimization problem, to tackle which, the state-of-the-art relies on relaxing the underlying Integer Programming Problem (IPP) into a Linear Programming Problem (LPP), solving the latter through Column Generation (CG) technique, and integerization of the resulting LPP solution. However, with the growing scale and complexity of the airlines' networks (those with large number of flights, multiple crew bases and/or multiple hub-and-spoke subnetworks), the efficacy of the conventionally used exact CG-implementations is severely marred, and their utility has become questionable. This research work proposes an Airline Crew Pairing Optimization Framework, AirCROP, whose constitutive modules include the Legal Crew Pairing Generator, Initial Feasible Solution Generator, and an Optimization Engine built on heuristic-based CG-implementation. AirCROP’s novelty lies in not just the design of its constitutive modules but also in how these modules interact. In that, insights on several important questions which the literature is otherwise silent on, have been shared. These relate to time-efficient initial solution generation, impact of the underlying initialization method on the final solution, the rationale for LPP-IPP interactions, their frequency and the underlying criteria etc. The efficacy of the AirCROP has been: (a) demonstrated on real-world airline flight networks with an unprecedented conjunct scale-and-complexity, marked by over 4200 flights, 15 crew bases, and billion-plus legal pairings, and (b) validated by the research consortium’s industrial sponsor. It is hoped that with the emergent trend of conjunct scale-and-complexity of airline networks, this paper shall serve as an important milestone for affiliated research and applications.

Mathematical Programming Techniques for Solving Crew Planning Problems

Crane Crew solvers are designed to handle multiple objectives and various complex constraints to provide the best possible solutions for large-scale binary integer programming models. In this talk, we will discuss the mathematical programming approaches used to solve those models such as constraint aggregation, column generation and so on and along with the challenges of bringing the models into the practice.      

Let’s Raise the Bar on FRM

The approach for controlling fatigue risk for pilots and cabin crew has become much more sophisticated in recent years but the untapped potential is still significant. Tomas Klemets, Head of Scheduling Safety at Jeppesen, elaborates on experiences to date and the elements he sees as needing improvement.

Towards robust crew pairing optimizer

Obtaining cost savings via pairing optimization has been talked about , but we have spent the past year improving the robustness of pairing solution without much impact on bottom line cost. Specifically in this talk we would present recent enhancements related to new regularity model we have introduced in pairing optimizer that promises more robust operations with related tradeoffs in costs. We also present other enhancements related to using smart crew availability constraints and Sabre Travel AITM powered block time forecasts that help improving robustness of final pairing solution.

Bringing speed to crew roster optimization

Crew Roster Optimization for a large group of Crew Members has perennially been a challenging problem to solve. Given that we pride ourselves in allowing airlines to use a flexible rule engine that allows them to generate rosters that support detailed fairness and legality criteria defined by planners, the eventual run time of optimizers has been a sticking point. With our partnership with Google and our launch of Sabre Travel AITM initiative, we have pioneered the smart and controlled use of legality prediction within the roster optimizer algorithm which provides 60-80% run time improvements without compromising on quality and coverage.

Dynamic evaluation of airline pilots flight request

This work addresses the dynamic problem of assessing pilots’ requests submitted weeks before the flights and while other requests have already been granted and pre-assigned. We propose a simulation-trained neural-network algorithm to evaluate flight requests, providing a systematic way of assessing the requests and supporting the definition of a cost-efficient request granting policy. To train and test this algorithm, we developed an innovative rolling rostering framework that captures the dynamic process in practice. The framework relies on an integer linear programming crew rostering model solved with the help of a column-generation algorithm. The neural-network algorithm is trained and tested in a case study with a major European airline. The results show that the algorithm is more effective than the current practice at the airline, granting 22% more requests while using the same workforce to operate the flight schedule.

A data driven approach that balances the crew schedule operability and cost

In the current business process, a crew schedule is being built several weeks in advance. The operability of the schedule on day of operation is subject to many factors and distributions, including air traffic control, weather, maintenance delays.  The closer the schedule is built to legality limit, the more likely the schedule will be broken on day of operation. In this talk, we will present a data driven approach that combines the use of machine learning and optimization to calculate an adaptive crew duty buffer that achieves a trade-off between operability and cost.

What kind of disruptive changes are needed in crew management in times of uncertainty and beyond?

The way Crew Management has been approached and solved has not changed dramatically over the past years and decades. Automation and optimization have added value and increased efficiency, whereas the general approach to cutting and delivering the process have not evolved that much. Especially during the past year with decreased planning certainty and major changes to Crew Management processes we have collected hypothesis on what changes will actually bring long-term benefits to Crew Management and what other disruptive changes will be needed to evolve further and tackle future challenges.

Wearable Sleep Measurements to Improve Fatigue Risk Management

Biomathematical models have become a standard technology for forecasting fatigue hazards during flight crew scheduling.  This is an efficient and effective way to meet internationally accepted requirements for fatigue risk management systems (FRMS) in aviation.  One key input to any biomathematical model is an estimate of one key fatigue factor: the pattern, duration, and quality of sleep likely to be obtained under a series of duty events.  Indeed, the accuracy of predictions can be dramatically altered with different sleep assumptions, but those assumptions are seldom questioned or validated.

In addition to refining our assumption about sleep during the planning process, sleep is a key variable that can be adjusted by the individual crew member.  A schedule may model well based on one set of sleep assumptions but be fatiguing if the crew member adopts a different pattern of sleep.  The crew member may be unaware of their vulnerability from cumulative sleep debt.

In this presentation, we will focus on technologies to address sleep assumptions as they impact the two sides of the fatigue equation:  sleep opportunities in the schedule and sleep decisions by the crew member.  We will focus on historical methods to guide sleep assumptions in modeling and emerging technologies for better refining those assumptions, especially commercially available wearables that have become common place for many crew members.  Specifically, we will review the capabilities and limitations of commercial wearables and layout the ideal wearable characteristics for providing a data driven process to measure, forecast, and improve sleep within the larger FRMS framework. 

Re-imagining Crew Planning in the times of pandemic

The COVID-19 pandemic has caused unprecedented challenges for airlines and their ability to plan and execute their operations. Airline crew planning has had to adapt to a new reality and learn how to manage constant change to flight schedules, protect crew members and minimize the risk of infection, anticipate and prepare for future disruptions. We will share experiences and trends we have encountered, how we have had to adapt to support airlines and discuss whether the pandemic has altered crew planning for the foreseeable future. Specifically we’ll go into how the concept of Crew Teaming can be modelled in support of creating social bubbles for crew.

Manpowerplanning in times of a pandemic and its aftermath - The Challenge of assessing flight schedule changes and crew demand in just minutes.

Continously changing demands and hence flight schedules are pushing the crew planning process together. Manpower planning is facing never seen before needs for flexibility and speed in decision-making. Flight schedule changes and crew demand have to be assessed within minutes or hours - not days. Therefore, traditional approaches to assessing demand and managing crew supply have reached their limits. Manpower Planning will change from a horizontal process to a "continuously vertical assessment" of crew demand and supply. We show which solutions help to manage this new speed and how to asses crew costs of a flight schedule in just minutes.

Integrated Crew Pairing and Rostering

Traditionally,  a crew roster is the result of two steps:  In the first step, an anonymous set of pairings is generated and optimized (CPP). A pairing is a sequence of tasks over consecutive days for a crew member leaving and returning to his/her base station. These combine flight segments, positionings between airports and overnight hotels. Individual duties are separated by rest periods or other constraints. The set of pairings is generated and optimized for each base station. 

In the second step, the crew rostering problem constructs a personalised schedule for each crew member (CAP). It assigns sequences of pairings to the available days of the crew member taking into account pre-assigned activities, crew member's qualifications, biddings or any other roster constraints.

The problem with this approach is that it might generate very optimal anonymous pairings in the CPP, which can then not be assigned in the CAP. This can be due to pre-assigned activities, base manpower imbalances or other  roster constraints not known by the CPP (due to the anonymous nature). In the end it might generate an infeasible or sub-optimal Roster.

In this talk we present a single step approach. One integrated calculation solves the combined crew pairing and rostering problem. Here, every crew member gets a set of personalized pairings that fit his/her available days, preferences, pre-assigned activities or any other crew related constraints. The integrated crew solution automatically copes with manpower or availability imbalances between different bases. This results in large-scale planning problems that are solved on parallel cloud computing using the latest algorithms.

This approach results in a lower total roster cost, a higher productivity and reduced open time due to the fact that the CPP problem has prior knowledge of space and constraints in individual crew members rosters, therefore creating better fit pairings for the CAP problem.

The technology has proven itself on a wide variety of benchmark data and is now in production at a European Airline. 

Smarter Planning

Looking in the future, how can airlines change their processes to create better plans

Achieving better standby forecasting through machine learning based models

The session introduces the promising area of using machine learning/ deep learning models for forecasting standby crew count more effectively and IBS Software shares their experience on the results of real-world studies it has conducted in this area.