p13 | Air Traffic Flow Management¶

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 fleet is partitioned into plane classes: planes of the same class are interchangeable and earn the same rewards, but different classes value the same location and time differently. The challenge is to make these assignments in a way that maximizes operational rewards, given the limited capacities of airports and sectors, which are shared by every class.

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.
Competing classes: Classes that value the same location differently compete for the same scarce capacity.
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, counting the planes of all classes present.
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. Both depend on the class of the plane.
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 class-, location-, and time-dependent (constant for sectors, location-dependent for airports).

Formulations¶

Formulation `a` (valid)¶

Parameters¶

Name	Description	Type	Shape
`nK`	Number of plane classes	integer	scalar
`nP`	Number of flights of class \(k\)	integer	`[nK]`
`nA`	Number of airspace sectors/locations	integer	scalar
`nT`	Number of time periods	integer	scalar
`adj`	Adjacency matrix: \(1\) if \(a\) is adjacent to \(a'\), \(0\) otherwise	binary	`[nA, nA]`
`r`	Reward for a class \(k\) flight being at location \(a\) at time \(t\)	continuous	`[nK, nA, nT]`
`cap`	Capacity of location \(a\) at time \(t\)	integer	`[nA, nT]`

Variables¶

Name	Description	Type	Shape / Indices
`n`	Number of class \(k\) flights at location \(a\) at time \(t\)	integer	`[nK, nA, nT]`
`f`	Number of class \(k\) flights moving from \(a\) at time \(t\) to \(a'\) at time \(t+1\)	integer	`[nK, nA, nA, nT]`

Assumptions¶

Description	Formulation	Implicit
Number of plane classes is at least one.	\(nK \geq 1\)	yes
Number of locations is at least one.	\(nA \geq 1\)	yes
Number of time periods is at least one.	\(nT \geq 1\)	yes
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
Class sizes are non-negative.	\(nP_k \geq 0 \quad \forall k \in K\)	yes

Constraints¶

All flights of every class are accounted for at every time period.

\[ \sum_{a \in A} n_{k,a,t} = nP_k \quad \forall k \in K, t \in T \]
The flights of all classes at a location do not exceed the location capacity.

\[ \sum_{k \in K} n_{k,a,t} \leq \text{cap}_{a,t} \quad \forall a \in A, t \in T \]
Flow conservation: class \(k\) flights at location \(a\) at time \(t\) equal those at \(t-1\) plus arrivals minus departures (one-step transitions).

\[ n_{k,a,t} = n_{k,a,t-1} + \sum_{a' \in A} f_{k,a',a,t-1} - \sum_{a' \in A} f_{k,a,a',t-1} \quad \forall k \in K, a \in A, t \in T, t > 0 \]
Movements are only allowed between adjacent locations.

\[ f_{k,a,a',t} \leq nP_k \times \text{adj}_{a,a'} \quad \forall k \in K, a, a' \in A, t \in T \]
No movements out of the final time period (would arrive outside the horizon).

\[ f_{k,a,a',nT-1} = 0 \quad \forall k \in K, 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_{k,a,a',t} \leq n_{k,a,t} \quad \forall k \in K, a \in A, t \in T \]
\(n\) is non-negative. (implicit)

\[ n_{k,a,t} \geq 0 \quad \forall k \in K, a \in A, t \in T \]
\(f\) is non-negative. (implicit)

\[ f_{k,a,a',t} \geq 0 \quad \forall k \in K, a, a' \in A, t \in T \]

Objective¶

Maximize total reward for all flights across all classes, locations, and time periods.

\[ \max \sum_{k \in K} \sum_{a \in A} \sum_{t \in T} r_{k,a,t} \times n_{k,a,t} \]

Formulation `b` (valid)¶

Parameters¶

Name	Description	Type	Shape
`nK`	Number of plane classes	integer	scalar
`nP`	Number of flights of class \(k\)	integer	`[nK]`
`nA`	Number of airspace sectors/locations	integer	scalar
`nT`	Number of time periods	integer	scalar
`adj`	Adjacency matrix: \(1\) if \(a\) is adjacent to \(a'\), \(0\) otherwise	binary	`[nA, nA]`
`r`	Reward for a class \(k\) flight being at location \(a\) at time \(t\)	continuous	`[nK, nA, nT]`
`cap`	Capacity of location \(a\) at time \(t\)	integer	`[nA, nT]`

Variables¶

Name	Description	Type	Shape / Indices
`y`	\(1\) if flight \(p\) of class \(k\) is at location \(a\) at time \(t\), \(0\) otherwise	binary	`[nK, nP[nK], nA, nT]`
`z`	\(1\) if flight \(p\) of class \(k\) moves from \(a\) at time \(t\) to \(a'\) at time \(t+1\), \(0\) otherwise	binary	`[nK, nP[nK], nA, nA, nT]`

Assumptions¶

Description	Formulation	Implicit
Number of plane classes is at least one.	\(nK \geq 1\)	yes
Number of locations is at least one.	\(nA \geq 1\)	yes
Number of time periods is at least one.	\(nT \geq 1\)	yes
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
Class sizes are non-negative.	\(nP_k \geq 0 \quad \forall k \in K\)	yes

Constraints¶

Each flight is at exactly one location at each time period.

\[ \sum_{a \in A} y_{k,p,a,t} = 1 \quad \forall k \in K, p \in P_k, t \in T \]
The flights of all classes at a location do not exceed the location capacity.

\[ \sum_{k \in K} \sum_{p \in P_k} y_{k,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_{k,p,a,t} = y_{k,p,a,t-1} + \sum_{a' \in A} z_{k,p,a',a,t-1} - \sum_{a' \in A} z_{k,p,a,a',t-1} \quad \forall k \in K, p \in P_k, a \in A, t \in T, t > 0 \]
Movements are only allowed between adjacent locations.

\[ z_{k,p,a,a',t} \leq \text{adj}_{a,a'} \quad \forall k \in K, p \in P_k, a, a' \in A, t \in T \]
No movements out of the final time period (would arrive outside the horizon).

\[ z_{k,p,a,a',nT-1} = 0 \quad \forall k \in K, p \in P_k, 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_{k,p,a,a',t} \leq y_{k,p,a,t} \quad \forall k \in K, p \in P_k, a \in A, t \in T \]

Objective¶

Maximize total reward for all flights across all locations and time periods.

\[ \max \sum_{k \in K} \sum_{p \in P_k} \sum_{a \in A} \sum_{t \in T} r_{k,a,t} \times y_{k,p,a,t} \]

Reformulations¶

Each entry below pairs two formulations of this problem, records whether the second is a reformulation of the first, and gives the parameter map carrying the first formulation’s parameters to the second’s.

a → b (valid)¶

Note

Formulation b has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of `a`
`nK`	\(nK = nK\)
`nP`	\(nP_k = nP_k\)
`nA`	\(nA = nA\)
`nT`	\(nT = nT\)
`adj`	\(\text{adj}_{ij} = \text{adj}_{ij}\)
`r`	\(r_{kij} = r_{kij}\)
`cap`	\(\text{cap}_{ij} = \text{cap}_{ij}\)

p13 | Air Traffic Flow Management¶

Description¶

Formulations¶

Formulation a (valid)¶

Parameters¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Formulation b (valid)¶

Parameters¶

Variables¶

Assumptions¶

Constraints¶

Objective¶

Reformulations¶

a → b (valid)¶

Formulation `a` (valid)¶

Formulation `b` (valid)¶