News & Events

In this series of blogs, we explore the dynamics of Tail Assignment. After the first blog “Unlocking Efficiency in Airline Scheduling with Tail Assignment Optimization” giving an introduction to tail assignment and the second blog “Navigating Complexity: The Cost Model and Constraints Behind Tail Assignment Optimization” providing an overview of which data is provided as input to the optimization and how the cost model and constraints are defined, this third blog dives deeper into the mechanics of the optimization calculation.

The optimization process in tail assignment optimization involves finding the most cost-effective assignment of aircraft to flights, while taking into account the costs and constraints as described in the previous blog. In order to do this effectively, airlines need sophisticated algorithms and software that can quickly find the optimal solution out of an almost infinite number of possibilities.

Before we can solve the problem as a large-scale optimization problem, we first need to translate all inputs into a mathematical model. We can do this by modelling the movement of each aircraft with the help of a periodic space-time graph, i.e.

• The vertices in the graph are the airports in the input flight plan, while
• The movement of the aircraft is represented by the edges on this graph.
• A flight connects the (source) vertex of the departure airport at the departure time with the (target) vertex of the arrival airport at the arrival time.
• Similar to flights, we can model the turnaround times, standby time, buffer time or maintenance as an edge connecting two vertices at the same airport.
• Since the schedule is periodic, flights that depart at the end of the period and that would normally arrive in the next optimization period will now arrive at the beginning of the optimization period (in simple terms the end of the planning period joins up with the beginning).

Once all flights, constraints, costs and restrictions are modelled, the graph model is translated into a large-scale constrained optimization problem and solved. For this different mathematical solvers exist on the market.

The optimization problem itself will basically try out a specific tail assignment of aircraft (which meets all constraints) and then calculate the corresponding cost function to determine the total (fictive) cost associated with the proposed tail assignment.  It will then adapt certain variables in the model and repeat the above calculation. If this solution has a better cost outcome than all previous solutions, it will be the best proposal (thus far). The solver will repeat these iterations, till it has found the solution it considers as the best possible solution.

As there are almost an infinite number of combinations, it is however impossible to “try out” every possible combination, as this would take too long and would also make the compute too costly.
As such there are all kinds of special techniques required for determining:

• The first iteration to start with (obviously this solution would not be randomly selected).
• Adjusting the variables in a next iteration to converge as quickly as possible to the optimal solution.
• Knowing when to stop. Obviously, you do not want to stop iterating too soon as this would provide a sub-optimal solution, but at the same time you want to avoid spending time and compute resources on iterating, while there is no improvement anymore.

For the first two issues, we can use mathematical functions to determine the likelihood that a specific variable in the model will have a specific value. The result of this can be used to give a first value to each variable and to determine a good evolution of the value of a variable in a next iteration step.

For the last issue, we need to ensure we do not end up in a local minimum of the cost function, but ideally that we can find the absolute minimum (i.e. optimal solution). For this also different mathematical techniques exist to determine if we are not in a local minimum.

As you can see, the quality of the proposed (optimized) tail assignment depends heavily on:

• The quality of the input data, i.e. how accurate does the input data (aircraft movements, all costs and all constraints) represent reality
• The optimization software, using different techniques to accurately convert all input data into a large mathematical optimization model and then solving this mathematical optimization model in the most efficient way possible.

In the next and final blog post in this series, we will provide a real-live example of the results a good tail assignment can deliver.

Photo by Towfiqu barbhuiya on Unsplash