p13 | Air Traffic Flow Management¶
See also
This problem is sourced from Ferchtandiker2025.
Note
We identify a number of modeling inconsistencies in the original pair of formulations. To address this, we propose a new pair of flow-based formulations. The efficient formulation
p13.bis an aggregated version ofp13.a.
Description¶
Optimizing Air Traffic Flow Management
In the context of increasingly congested airspaces and strained airport capacities, the Air Traffic Flow Management Problem (TFMP) seeks to optimize the allocation of aircraft across a network of airports and airspace sectors over time. This problem is critical for airlines who must efficiently utilize their fleet while respecting operational and capacity constraints.
Core Challenge Airlines must decide, for each time period, where each plane in their fleet should be located—either at an airport or within an airspace sector. The challenge is to make these assignments in a way that maximizes operational rewards, given the limited capacities of airports and sectors.
Key challenges include:
Airport congestion: Limited runway and gate availability during peak hours or adverse weather.
Sector bottlenecks: Airspace regions with strict capacity limits.
Interconnected delays: Congestion at one location can propagate through the network.
Reward asymmetry: The reward for a plane being in the air (in a sector) is a constant, while the reward for being at an airport is location-dependent and may reflect operational priorities or incentives.
In this specific case, an airline seeks to determine the optimal position of each plane in its fleet at every time period, balancing the rewards for being at different locations and the constraints imposed by the system.
Operational Components
Each plane must be assigned to exactly one location (airport or sector) at each time period.
Each location (airport or sector) has a capacity limit for each time period.
The reward for a plane being in a sector (in air) is a constant value, while the reward for being at an airport depends on the specific airport.
Flow preservation: Planes can only move between adjacent locations from one time period to the next, as defined by the adjacency structure of the network. This ensures that the presence of a plane at a location and time is consistent with feasible transitions from previous locations.
Key Constraints:
Location capacities: No more planes than the allowed capacity at any location and time.
Unique assignment: Each plane is in exactly one location at each time.
Flow preservation: For each plane, the number of times it enters a location at time t must equal the number of times it leaves at time t+1, except at the initial and final time periods. This is enforced by only allowing transitions between adjacent locations.
Objective Function: Maximize the total reward, defined as the sum of rewards for all planes, locations, and times, where the reward is location- and time-dependent (constant for sectors, location-dependent for airports).
Formulations¶
Formulation a (valid)¶
See also
This formulation is sourced from Ferchtandiker2025 (formulation id: inefficient).
Note
This is the disaggregate (inefficient) formulation.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
Number of flights |
integer |
scalar |
|
Number of airspace sectors/locations |
integer |
scalar |
|
Number of time periods |
integer |
scalar |
|
Adjacency matrix: 1 if a is adjacent to a’, 0 otherwise |
binary |
|
|
Reward for being at location a at time t |
continuous |
|
|
Capacity of location a at time t |
integer |
|
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
1 if flight p is at location a at time t, 0 otherwise |
binary |
|
|
1 if flight p moves from a at time t to a’ at time t+1, 0 otherwise |
binary |
|
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
Every location is adjacent to itself. |
\(\text{adj}_{a,a} = 1 \quad \forall a \in A\) |
yes |
Capacity values are non-negative. |
\(\text{cap}_{a,t} \geq 0 \quad \forall a \in A, t \in T\) |
yes |
Constraints¶
Each flight is at exactly one location at each time period.
\[ \sum_{a \in A} y_{p,a,t} = 1 \quad \forall p \in P, t \in T \]The number of flights at each location does not exceed the location capacity.
\[ \sum_{p \in P} y_{p,a,t} \leq \text{cap}_{a,t} \quad \forall a \in A, t \in T \]Flow conservation: flights at location a at time t equal those at t-1 plus arrivals minus departures (one-step transitions).
\[ y_{p,a,t} = y_{p,a,t-1} + \sum_{a' \in A} z_{p,a',a,t-1} - \sum_{a' \in A} z_{p,a,a',t-1} \quad \forall p \in P, a \in A, t \in T, t > 0 \]Movements are only allowed between adjacent locations.
\[ z_{p,a,a',t} \leq \text{adj}_{a,a'} \quad \forall p \in P, a, a' \in A, t \in T \]No movements out of the final time period (would arrive outside the horizon).
\[ z_{p,a,a',nT-1} = 0 \quad \forall p \in P, a, a' \in A \]Movements at time t require the flight to be present at time t (depart only from where you are).
\[ \sum_{a' \in A} z_{p,a,a',t} \leq y_{p,a,t} \quad \forall p \in P, a \in A, t \in T \]
Objective¶
Maximize total reward for all flights across all locations and time periods.
Formulation b (valid)¶
See also
This formulation is sourced from Ferchtandiker2025 (formulation id: efficient).
Note
This is the aggregate (efficient) formulation.
Parameters¶
Name |
Description |
Type |
Shape |
|---|---|---|---|
|
Number of flights |
integer |
scalar |
|
Number of airspace sectors/locations |
integer |
scalar |
|
Number of time periods |
integer |
scalar |
|
Adjacency matrix: 1 if a is adjacent to a’, 0 otherwise |
binary |
|
|
Reward for being at location a at time t |
continuous |
|
|
Capacity of location a at time t |
integer |
|
Variables¶
Name |
Description |
Type |
Shape / Indices |
|---|---|---|---|
|
Number of flights at location a at time t |
integer |
|
|
Number of flights moving from a at time t to a’ at time t+1 |
integer |
|
Assumptions¶
Description |
Formulation |
Implicit |
|---|---|---|
Every location is adjacent to itself. |
\(\text{adj}_{a,a} = 1 \quad \forall a \in A\) |
yes |
Capacity values are non-negative. |
\(\text{cap}_{a,t} \geq 0 \quad \forall a \in A, t \in T\) |
yes |
Constraints¶
All flights are accounted for at every time period.
\[ \sum_{a \in A} n_{a,t} = nP \quad \forall t \in T \]The number of flights at each location does not exceed the location capacity.
\[ n_{a,t} \leq \text{cap}_{a,t} \quad \forall a \in A, t \in T \]Flow conservation: flights at location a at time t equal those at t-1 plus arrivals minus departures (one-step transitions).
\[ n_{a,t} = n_{a,t-1} + \sum_{a' \in A} f_{a',a,t-1} - \sum_{a' \in A} f_{a,a',t-1} \quad \forall a \in A, t \in T, t > 0 \]Movements are only allowed between adjacent locations.
\[ f_{a,a',t} \leq nP \cdot \text{adj}_{a,a'} \quad \forall a, a' \in A, t \in T \]No movements out of the final time period (would arrive outside the horizon).
\[ f_{a,a',nT-1} = 0 \quad \forall a, a' \in A \]Aggregate departures at time t do not exceed presence at time t (stay-flow non-negativity).
\[ \sum_{a' \in A} f_{a,a',t} \leq n_{a,t} \quad \forall a \in A, t \in T \]n is non-negative. (implicit)
\[ n_{a,t} \geq 0 \quad \forall a \in A, t \in T \]f is non-negative. (implicit)
\[ f_{a,a',t} \geq 0 \quad \forall a, a' \in A, t \in T \]
Objective¶
Maximize total reward for all flights across all locations and time periods.