The Air Traffic Flow Management Rerouting Problem

As part of a short student project, I had the opportunity to work with the Swedish state company LFV that regulates and oversee all aspects of aviation in Sweden. In this article, I will be covering the Air Traffic Flow Management Rerouting Problem (TFMRP).

I. Problem defintion and the state of the art

Throughout the last decade, the DCB problem (Demand and capacity balancing) for airport use has been a real issue in the United States and Europe. The demand for airport use has been rapidly increasing and airport capacity has been stagnating. That obviously is coming from the fact that the number of passengers has increased by more than 50 percent during the last years while no actual increase in capacity has been noted. Acute congestion in many major airports has been the unfortunate result. For U.S. airlines, the expected yearly cost of the resulting delays is currently estimated at $3 billion. Every day 700 to 1100 flights are delayed by 15 minutes or more. Thus, congestion is a problem of undeniable practical significance.

To face off the congestion problem and its costs, some policies have been used. The major ones are ground-holding policies. The idea behind ground-holding flights is that for fixed airport capacities and flights schedules, we can adjust the flow of aircraft on a real time basis by imposing “ground holds” on certain flights. Such a flight is then held on the ground at its departure airport even if it is otherwise ready for takeoff. Ground-holding makes sense in the situation when it has been determined that if an aircraft departs on time, then it will encounter congestion, incurring an airborne delay as it awaits landing clearance at its destination airport. By delaying its departure, the aircraft will arrive at its destination at a later time when minimal congestion is expected, thus, incurring no airborne delay. Therefore, the objective of ground-holding policies is to “translate” anticipated airborne delays to the ground. The effectiveness of ground-holding policies can be justified by two major facts. First, while a flight is airborne it incurs costs such as fuel and safety that not applicable before the flight takes off. These costs make airborne delays much costlier than ground delays. Second, airport capacity is highly variable due to its heavy dependence on the weather (visibility, wind, precipitation, cloud ceiling). It is not unusual for the capacity of an airport to be reduced by 50 percent in inclement weather. Given these two facts, there is significant potential to reduce costs when adjusting aircraft flow as weather (hence airport capacity) forecasts change in such a way that ground delays are substituted for the much costlier airborne delays.

Currently, The FFA (Federal Aviation Administration US) implements a ground-holding policy. Using the air traffic controllers computerized procedure has been developed based on a first-come, first-served rule, in order to select appropriate ground-holds.

The problem of scheduling flights in real time in order to minimize congestion
costs was first conceptualized and introduced in 1987. The first implementation considers a single airport and makes decisions about the ground-holds for this Single-Airport Problem (SAGHP). Then, the next implementation deals with Multi-Airport- Ground-Holding Problem in order to make ground holding decisions for an entire network of airports. Later on, the Air Traffic Flow Management Problem came to not only determine release times for aircraft but also determines the optimal speed adjustment of aircraft while airborne for a network of airports taking into account the capacitated airspace. Adding the possibility of rerouting flights due to drastic fluctuations in the available capacity of airspace regions, we obtain the Air Traffic Flow Management Rerouting Problem (TFMRP).

This article will cover a 0–1 integer programming dertministic modeling, starting from scratch to build a model that is going to enable us to minimize the cost related to all flights in a network and produce an opening scheme for our configurations. So many notions are said, if you are having trouble to understand everything now, that is completly normal, things will get clearer as we are building our model.

II. Strating from scratch

We will start with some easy examples of network airports, and step by step we will add complexities to the model.
Let us start with this simple network in this next figure:

Figure 1: A simple network

• 1, 2, 3 and 4 represent airports.
• The white area is the area that we are going to controll, for example it is the Swedish airspace, where we have set up our controllers.
• The grey area represents everything outside the controlled airspace.

The last figure shows that some airports are going to be inside our zone of interest and others are going to be outside. Thus, we will have to deal mainly with 4 different types of flights as shown here:

Figure 2: Flights types

• The First type In-In: for a flight starting from an inside airport and heading towards an inside airport. (The aircraft in black)
• The Second type In-Out: for a flight starting from an inside airport and heading towards an outside airport. (The aircraft in red)
• The Third type Out-In: for a flight starting from an outside airport and heading towards an inside airport. (The aircraft in yellow)
• The Fourth type Out-Out: for a flight starting from an outside airport and heading towards an outside airport. (The aircraft in blue)

Obviously, we will not consider flights like the one in the green color since they do not pass through our area of interest.

To manage the airspace, it will be divided into Sectors. These Sectors are like 3D jigsaw puzzle pieces with differing heights and sizes that interlock to cover the sky. Each sector is controlled and guided by our Air Traffic Controllers. Airspace Sectors can be created and reduced dynamically to deal with demand: at times when there are high levels of air traffic, more sectors may be opened with more Controllers allocated to manage the aircraft within an area of airspace. This is done to maintain safety as a controller can only manage a certain number of aircraft at one time. The following two pictures show examples of a set of sectors:

USA airspace sectors 3D

USA airspace 2D

Each flight passes through contiguous sectors while it is en route to its destination. With a limit number of controllers on each sector, the sector’s capacity will be evidently limited, in other words, there is a restriction on the number of airplanes that may fly within a sector at a given time. Thus, there is a risk of congestion at these sectors, and it is as critical as congestion in the terminal areas, since the cost of holding an airborne aircraft is not dependent on the location of the aircraft. Thus, airborne delay costs could further be reduced if we could determine the optimal time for a flight to traverse the capacitated sectors.

As a first step to build our model, we will be dealing with First type of flight In-In, and we will see later that the other types could be included in our model with some little changes.

Let us consider a flight starting from Airport1 and heading towards Airport2 (both of the airports are within the area of interest).

Path for a single flight (type In-In)

• A, B,…,K are the sectors
• 1 the departure airport
• 2 the destination airport

The path of the flight will be written in the following form:
Path={1,A,D,C,G,I,K,2}

A flight can have different routes to follow, for example for the same flight we can have the next possibilities:

Different routes for a single flight

As shown in the figure, a flight can have different routes, but there is always a scheduled route that it should normally follow to get to the destination and the others are alternatives to avoid congestion. In other words, a flight should follow the scheduled route in normal conditions, rerouting adds costs. For example, let the path in black be the scheduled route, all the others are alternatives, for example the one in yellow would be considered, when the flight cannot pass through the sector C and G due to congestion or weather conditions.

We will build a scenario in order to define all the parameters and the possible decisions that we can make.

Let us consider a flight denoted by f, starting from Airport1 and heading towards Airport2.

• First: we choose which route the flight will follow. For example let it be the one in black. So the path now is known and it is: Path_of_f_along_black_route={1,A,D,C,G,I,K,2}
• Second: we choose the time when the aircraft should take off. Each flight has a time interval of possible departures time periods. Should we hold the aircraft on the ground or not? Or maybe cancel the flight?
• Third: now the aircraft is airborne, we should decide for each sector when to enter and when to leave with a possible airborne hold.
• Fourth: For landing in the destination airport, we should check if the runaways are available and that is by choosing the time to land in.

Things are starting to get clearer, the decisions are made on the flight, the route that the flight should follow, the time for entering or exiting each sector or airport.

II. The 0–1 IP formulation

Since we are dealing with an optimisation problem that aims to minimize the costs related to ground-holding, airborne holding, rerouting and cancellation, we will formulate the problem with integer programming, define our decision variables and the objective function.

Let us define:

The sets

Comments on the sets:

• As shown in the set of time periods, we will be working with discrete time.
• A resource could be an airport or a sector.

The parameters

Decision variables

The first decision variable that one could think off would be:

This is a good choice and it will work perfectly to describe the whole problem, but when we are dealing with ATFMP we tend to use a classic decision variable than enable us to do some good representation and interpretation of the results at the end, the decision variable that we are going to use is:

Comments:

• The difference in defining the two variables is in the two words “at” and “by”.
• Our decision variable has four dimensions.

Let us take an example to understand how this works:

The aircraft is at the sector G, heading always towards Airport2.
Suppose that the flight was expected to take off at the time period t=2 and the picture was taken at t=10, a possible table for the decision variable in the different resources along the followed route would be:

The scheduled departure time is t=2, but the actual departure time according to the table is t=3, here we are talking about ground-holding the aircraft.

The table would be as the following for the other decision variable

Actually, there is a relation that links the two decision variables:

But as mentioned before we will be working with:

How to include cancellation in our model?

We can say that a flight has been cancelled, if it does not arrive at the latest possible time at tha arrival airport along all the routes, here j is the arrival airport.

How to include different types of flights in our model?

Since, we are dealing with the flights only when they are inside our area of interest. We will add a virtual airport with an infinite arrival capacity and null departure capacity. As shown in the next figure, all the other types of flights can now be seen like the type In-In.

The Objective function

The problem aims to minimize the sum of all costs related to ground-holding, air holding, rerouting and cancellation.

To calculate the ground hold cost for one single flight following some route, first we need to calculate the ground hold time which is the difference between the time when the aircraft actually takes off and the scheduled time for departure. Then the ground hold cost is the ground hold time multiplied by the ground hold cost per unit of time.

For the air holding cost for one single flight following some route, we need to calculate the air holding time that is the difference between the time when the aircraft land in and the time when it was supposed to land in taking into account the delay due to the ground holding. We multiply the difference by the air holding cost per unit of time to get the following expression:

In order to see if a flight is cancelled, at the arrival airport and at the latest possible time, if the decision variable takes a value of 0 that means the flight did not arrive using that route, we should sum up over all the possible routes. The cancellation cost is then

For the rerouting penalty we should check if we followed the scheduled route or not, at any point of the path, we will consider the origin

The objective function that is the sum of all the previous terms over the flights and the routes, expect for the cancellation penalty that is going to be summed up for the flights only:

The constraints

Now, we will write the constraints of the problem.

Constraint 1: Departure capacity

The number of flights taking off from an airport k at time t must not exceed the departure capacity, so for each airport, we should verify that the number of flights departing is not more than its capacity.

Constraint 2: Arrival capacity

The number of flights arriving to an airport k at time t must not exceed the arriving capacity:

Constraint 3: Sector capacity

The number of flights within a sector j at time t should not exceed the sector capacity

Constraint 4: Path connectity constraint

A flight cannot access the following sector unless it has spent at least the required time in the current sector.

Constraint 5: Time connectity constraint

If a flight arrives at ressource j at time t-1, then it should have a value of 1 for all t’≥t-1.

Constraint 6: Turn around time

Suppose f is the next flight after the flight f’ using the same aircraft, the turn around time is the time needed to clean, refuel, unload and load, and further prepare the aircraft for the next flight.

Constraint 7: If a flight takes off, it should land in

We should compare the variable decisions at the departure airport and the arrival airport, they must have the same value at their latest possible times.

We can sum the whole problem in the following equations

Model (A)

And now we can say that we have built the first model that we are going to name (A). However, there are some changes to make on the model, because actually sectors are just part of a big structure called configurations. This big structure helps to control the network more efficiently.

III. Configurations instead of sectors

A configuration is a set of sectors, an example of a configuration could be {A,B,D,I}. Each configuration has an opening scheme for each day. Some configurations could have a common sector, thus cannot be active at the same time. A configuration has its own capacity and that depends on the sectors that contains.

Let us consider the following configurations Config1={A}, Config2={B}, Config3={A,D,E}, Config4={C,H,I} and Config5={I}. An opening scheme for this configuration could be:

The table shows that Config3 and Config1 cannot be active at the same time because they have in common the sector A, same for the Config4 and Config5.
It shows also that a configuration can be activated and deactivated multiple times.

Suppose we have a given opening scheme for the whole configurations in the network, what are the things that we have to change in our model to include these new changes?

The only change that we are going to make in the constraint related to the sectors capacities, because we are no longer dealing with sectors but instead configurations, the constraint alters and it becomes:

Comment: When a configuration is not open, its capacity has value of 0.

And with that, we have built the model (B) that aims to minimize the total cost in our network taking into consideration the configurations and their opening scheme.

IV. Towards a bi-objective optimisation problem

When a configuration is open, we should have enough controllers available to monitor the sectors within. It requires the human effort, energy and devices to keep a configuration open. We will now extend our model in order to not only minimize the total cost but also minimize the total unused capacity of all the configurations, in other words, we should look for the best opening scheme in order to open them efficiently. For example, if a configuration is not expecting any flights passing through after t=12, then it should be closed, if two configurations respond to my constraints which one to choose so that the unused capacity in minimal?

We will define a new decision variable, that is going to be binary and that tells us if a configuration is open at a certain time period t.

The first constraint: at most one configuration among other configurations that contains an elementary sector should be active at any time.

The second constraint: we cannot activate a configuration for a duration less than fixed number for hours.
Let us consider that we have 97 time periods and that each time period lasts 15 minutes (that is going to give exactly 24 hours, time periods start with t=1). And let 4.5 hours that fixed number of hours that each configuration should be open for once activated. Then, the corresponding number of time periods is N=18.

The constraint includes the product of two decision variables, it is no longer a linear problem!!! We can solve this by defining a new decision variable that acts like the product and works perfectly in this situation.

The third constraint: the limit number of activations is limited to 3. To do so we have to count how many times the decision variable goes up from 0 to 1. Another way is to count how many times the decision variable changes the value by either going from 0 to 1 or the opposite way.

Another objective function: we want to minimize for all the configuration and unused capacity. We can do that by subtracting from the total capacity of the configurations and the number of flights passing through them.

The whole model now can be summarized as follows:

Solving the bi-objective function:

First of all we should keep in mind that the two objective function are not homogeneous, the first one is a cost and the second one is a capacity.

We can think of using the weighted sum, but it is not easy to pick the most accurate weights.

So, we are going to use the ∈-constraint method in order to find all the points on the Pareto frontier. The algorithm is as follows:

V. Test the model on real data

To solve this optimzation problem we can use any solver in any programming language that we are most comfortable with. I would recommend using Julia with the solver Gurobi.
A big set of data was given by LFV, but unfortunately due to confidentiality and privacy reasons I am not able to publicly share it. But if you are interested in testing your model, you can create your own data set.
Once the model is implemented, optimizing the bi-objective problem takes too much time more than hours for some data sets. More precisely, optimizing the second objective function that is the unused capacity the build the opening scheme takes so much time. As a solution to this issue we are going to develop some heuristics.

VI. Genetic Algorithm

The genetic algorihm is based on the idea of natural selection. The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.
The five phases of the GA are:

• Initial population
• Fitness function
• Selection
• Crossover
• Mutation

We are going to perform GA on the decision variable Y

Generating the initial population

Since we are dealing with an optimization problem with so many constraints, the initial population, which is a large set of possible solutions that evidently verify all the constraints is not easy to generate. To do so, we should look at one of the solution using the direct optimization and setting a time limit for the solver. The opening scheme looks like:

As we can see, to generate the population ,we should pick for each configuration a random times to activate and deactivate, but also these random times should be chosen so that the constraints are always respected.

The First constraint: Configuration lasts 18 time periods once activated
For example, let t be a random time period to activate a configuration, then the random time to deactivate it must be greater than t+18, because one the constraints on the configurations is that it should be kept open for 18 time periods at least once activated.

The Second constraint: Configuration should be activated at most 3 times
For this constraint, the random times to pick for activate and deactivate should not exceed a total of 6.

The Third constraint: Two configurations having a common sector cannot be active at the same time
This the most tricky constraint. Let us define a first function Link

Let us define a second fonction Way

The function Link is going to help us when we want to activate a configuration to verify another with a common sector is active or not.

The function Way verifies this constraint too but it is going to help us with the crossover. Yes, sometimes we should think about the crossover and the mutation when generating the population. The crossover is going to be done over the configurations.

Performing the Crossover

Let config3 and config4 two configurations having a common sector, config4 and config7 have a common sector and config3 and config7 have no sector in common.

And that is why we need the function Way to create sets of configurations, and the perform the Crossover on the sets not on the configurations, this way after each crossover we get always a feasible solution.

If we generate a large initial population and because of the difficulties to perform mutation it is possible to not do it.

• Once the initial population is generated, the Fitness score function is going to be the first objective function that means the total cost since the optimisation problem related to minimzing the total cost only can be solved in seconds
• We create our mating pool, by taking the elite members of our population.
• We perform crossover on the mating pool
• We get the first generation
• We perform the GA as much as we want until we get a pleasing solution

VII. Fix and Relax

The Fix and Relax algorithm is based on the idea of relaxing the binary decision variables, instead of having a value of 0 or 1, some of them can be real.

The idea is that some the variables are going to be real, some are binaries and some are fixed to the values found in the previous iteration when solving the bi-objective problem. Step by step we keep moving the window, until all the variables are fixed and we get the final solution.

Bibliography

• The Air Traffic Flow Management Problem: An Integer Optimization Approach: Dimitris Bertsimas, Guglielmo Lulli, and Amedeo Odoni, MIT.
• THE AIR TRAFFIC FLOW MANAGEMENT PROBLEM WITH
  ENROUTE CAPACITIES: DIMITRIS BERTSIMAS and SARAH STOCK PATTERSON, Massachusetts Institute of Technology, Cambridge, Massachusetts
• https://www.nats.aero/ae-home/introduction-to-airspace/
• A relax-and-fix with fix-and-optimize heuristic applied to multi-level lot-sizing problems, Claudio Fabiano Motta Toledo,Márcio da Silva Arantes,Marcelo Yukio Bressan Hossomi,Paulo Morelato França & Kerem Akartunalı.
• https://towardsdatascience.com/introduction-to-optimization-with-genetic-algorithm-2f5001d9964b