Building the Most Efficient Tail Assignment Schedule

The Problem: Tail Assignment

Founded in 1933, Air France is the number one French airline and, together with KLM, one of the world’s largest air carriers by revenue and passengers transported. Integrated into the IT department, the Air France Operations Research department optimizes the operation of all company activities by transforming data into smart decisions. The Operations Research department sought to build the most efficient schedule for its entire fleet through the use of mathematical optimization in order to save on fuel and operational costs, while reducing delay propagation. They turned to mathematical optimization to help solve the Tail Assignment Problem – modeling the entire aircraft planning process, from fleet assignment to the day of operation.

Tail Assignment Optimization

Tail assignment optimization consists of assigning flights to aircraft, while respecting operational constraints. This means building a plan for each individual aircraft by building the sequence of flights that each aircraft will perform.

Constraints

The possible operational constraints in planning include:

• A limited authorized number of flight hours before the next scheduled maintenance.
• Some flights cannot be assigned to a given aircraft – For example, only specific aircraft can fly to Papeete, Tahiti, which is located in the middle of the Pacific Ocean and requires the aircraft to be authorized to fly long distances away from emergency airport extended operations (ETOPS).
• Some flights cannot chain on the same aircraft – For example, you cannot plan a flight from Charles de Gaulle Airport to New York City and then a flight from Los Angeles Airport to Charles de Gaulle Airport, as the flights need to comply with the layover.

Sequencing of Flights

In addition to the hard, operational constraints, the way the sequence of flights is built has a direct impact on:

Fleet Utilization – Number of flying hours of an aircraft during the planning horizon divided by the total number of hours in the planning horizon.

On-Time Performance – If a given aircraft is scheduled to have two sequential flights that are very close to one another, then the risk of propagating a possible delay of the first flight is higher.

Fuel Consumption – Some destinations consume more fuel than others because of heat or pollution. In addition, aircraft fuel consumption is not equal. Fuel consumption depends on the age of a plane or on the plane’s last maintenance visit; therefore, assigning a flight to one aircraft or another has a direct impact on the fuel consumption.

Operational Costs – If two flights are scheduled on the same aircraft with a long transit time, then it will probably need to be towed away in order to free a parking spot for another aircraft, which mobilizes towing resources and therefore, costs more money.

Preferential Assignments – If possible, it is preferable to assign specific flights to a given aircraft for commercial reasons, depending on the equipment of the aircraft.

Therefore, there is a need to consider trade-offs between different criteria and the possible impact to build the most efficient schedule for the entire fleet. This makes tail assignment optimization a multi-criteria mixed-integer programming (MIP) problem.

The Solution: Multi-Criteria Modeling and Mathematical Optimization

First, the Operations Research team needed to model three criteria. For this they relied on business expertise and statistical analysis of the past. They built statistical models to estimate the fuel consumption of each aircraft, given what they observed in the past and given the maintenance schedule to repair and/or enhance the performance of parts of the aircraft. For the delay, they estimated a cost that represents the probability of propagating the delay, given a transit time.

The schedules are re-built every day to comply with the disruptions that happened the previous day, so the tool needed to be responsive. The repetitive aspect and complexity of these decisions made this problem a good candidate for optimization, since the expected gains are marginal in percent but apply to huge volumes. The problem can be well-solved for the long-haul fleet with flights lasting from six to 12 hours. The most difficult part is the multi-criteria modeling and how to consider the trade-offs between all the different aspects to get an unbiased optimal solution. The challenge was then to adapt the model to the medium-haul fleet with flights lasting from three to six hours. The problem is much more complex as the number of possibilities is much higher compared to the long-haul fleet. Shorter flights mean more flights to schedule. Therefore, the standard techniques need to be adapted to solve the problem to optimality or the closest possible to it.

The Air France Operations Research team managed to build an efficient model and used the strong performance of the Gurobi Optimizer – a mathematical programming solver – to find an optimal or near-optimal solution for the medium-haul scheduling problem in a reasonable amount of time.

Decision Support Tool

The Operations Research team built a Decision Support Tool powered by the Gurobi Optimizer to recommend a solution that internal users can use to fit their specific needs. The tool provides an optimal solution with respect to the given constraints and the criteria, but the user still has the flexibility to make decisions based on experience, if needed. Therefore, the Data Science team is able to inform the user of the impact of decisions on the solution by highlighting the constraint that could be violated or by displaying the impact on the different costs.

About the Air France Operational Research Team

Integrated into the Air France IT department, the mission of the Operations Research department is to optimize the operation of all company activities by transforming data into smart decisions. It thus contributes to the strategy of the company, through the improvement of the company’s commercial and operational performance. Air France’s Operations Research department is one of the most important in France and in the air transport sector. Employees are simultaneously consultants, innovators and developers. They work on various company domains, from maintenance to customer relations as well as flight crews.