Air France: Tail Assignment Optimization

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.