MILP in Air Traffic Management: Engineering Efficient Airspace

Imagine 60 aircraft approaching Hong Kong terminal airspace during a thunderstorm, each burning approximately 1000 HKD worth of fuel per minute while circling. Every decision—which plane lands first, which uses which runway—has cascading effects throughout the entire air traffic system. How do air traffic managers solve this complex puzzle efficiently?

Enter Mixed Integer Linear Programming (MILP), a powerful mathematical approach that's revolutionizing how we manage our increasingly crowded skies. As researchers in air traffic management (ATM), we rely on this technique to tackle some of aviation's most challenging optimization problems.

Why MILP for Air Traffic Management?

ATM involves balancing competing goals like safety, efficiency, and capacity. Key decisions often have a discrete nature:

Assigning a flight to a specific runway.
Choosing a departure slot.
Determining the landing sequence for aircraft.

MILP excels at combining these "yes/no" or "which one" choices (using integer variables) with continuous variables like precise timings or flight levels, all within a structured mathematical framework.

The MILP Framework: A Quick Primer

In essence, MILP aims to optimize (minimize or maximize) a linear objective function subject to a set of linear constraints. The "mixed integer" part means some decision variables must take integer values (often 0 or 1), while others can be continuous.

The general form looks like this:

\begin{aligned} \text{Minimize } & c^T x \\ \text{Subject to } & Ax \leq b \\ & x_j \in \mathbb{Z} \quad \forall j \in I \\ & x_k \in \mathbb{R}_{\ge 0} \quad \forall k \notin I \end{aligned}

Where $x$ represents our decisions, $c^T x$ is the goal we optimize, $Ax \leq b$ are the rules we must follow, and $I$ identifies the variables that must be integers.

A Classic Example: The Traveling Salesperson Problem (TSP)

To see MILP in action, consider the famous Traveling Salesperson Problem (TSP): Find the shortest possible route visiting a set of cities exactly once and returning to the start.

We can model this using binary variables $x_{ij}$ (1 if traveling from city $i$ to $j$ , 0 otherwise) and distances $d_{ij}$ :

\begin{aligned} \text{Minimize } & \sum_{i} \sum_{j \neq i} d_{ij} x_{ij} \quad &&\text{(Total distance)} \\ \text{Subject to } & \sum_{j \neq i} x_{ij} = 1 \quad &&\forall i \quad \text{(Leave each city once)} \\ & \sum_{i \neq j} x_{ij} = 1 \quad &&\forall j \quad \text{(Enter each city once)} \\ & \text{(Subtour elimination)} && \text{(Ensure one single tour)} \\ & x_{ij} \in \{0, 1\} \end{aligned}

The binary variables $x_{ij}$ capture the discrete choice of which path segments to include in the tour. The "Subtour elimination constraints" prevent solutions where the salesperson completes smaller loops without visiting all cities. These can be formulated using the Miller-Tucker-Zemlin (MTZ) approach, which introduces auxiliary variables $u_i$ for each city and constraints:

u_i - u_j + n \cdot x_{ij} \leq n - 1 \quad \forall i,j \geq 2, i \neq j

1 \leq u_i \leq n \quad \forall i \geq 2

Where $n$ is the number of cities. These constraints create a kind of "ordering" that ensures all cities are visited in a single tour.

An ATM Application: Aircraft Arrival Scheduling (ASP)

Now, let's connect this to my own research, as detailed in the paper "Gradient-based smart predict-then-optimize framework for aircraft arrival scheduling problem". We tackle the Aircraft Arrival Scheduling Problem (ASP) within the Terminal Maneuvering Area (TMA).

The Challenge: Determine the optimal sequence and landing times for a set of arriving aircraft at a runway (or multiple runways) to minimize delays while respecting safety separation requirements between consecutive landings. Like TSP, this is also an NP-hard problem.

Our MILP Approach (based on Beasley et al. [4] from the paper):

Decision Variables:
- $y_i$ : The actual landing time for aircraft $i$ (continuous variable).
- $\omega_i$ : A binary variable indicating if aircraft $i$ lands after its target/expected time $T_i$ (1 if delayed, 0 otherwise).
- $\delta_{ij}$ : A binary variable indicating the sequence: 1 if aircraft $i$ lands before aircraft $j$ , 0 otherwise.
Objective Function:
- Minimize the total weighted delay. In our paper, we simplify this by using the predicted transit time $\hat{T}_i$ as a proxy for the cost coefficient $c_i$ , aiming to minimize $\sum_{i \in \mathcal{A}} c_i \omega_i$ . The goal is to reduce the overall delay impact.
Key Constraints:
1. Time Windows: Each aircraft $i$ must land within its earliest possible time $E_i$ and latest possible time $L_i$ : $E_i \leq y_i \leq L_i$
2. Delay Definition: Link the landing time $y_i$ to the delay variable $\omega_i$ using the "Big M" method: $y_i - T_i \leq M \cdot \omega_i$ $y_i - T_i \geq -M \cdot (1 - \omega_i)$ (Where $M$ is a large constant. These ensure $\omega_i$ becomes 1 if $y_i > T_i$ ).
3. Sequencing: For any pair of aircraft $(i, j)$ , one must land before the other: $\delta_{ij} + \delta_{ji} = 1$
4. Separation: If aircraft $i$ lands before $j$ ( $\delta_{ij}=1$ ), then $j$ must land at least $s_{ij}$ seconds after $i$ , where $s_{ij}$ is the minimum required separation time (often based on wake turbulence categories): $y_j - y_i \geq s_{ij} - M \cdot \delta_{ji}$ (The $M \cdot \delta_{ji}$ term effectively switches off this constraint if $j$ lands before $i$ ).

This MILP formulation captures the core scheduling logic. Our research focused on how to best determine the cost coefficients ( $c_i$ ) and target times used within this MILP framework, integrating machine learning predictions, but the underlying optimization engine relies on solving this type of MILP model.

The ASP is just one example; MILP is also used for runway configuration management, departure sequencing, airspace sector configuration, and more.

Conclusion

Mixed Integer Linear Programming provides an expressive way to model many optimization problems in Air Traffic Management. Its ability to handle both discrete choices and continuous adjustments makes it invaluable for finding efficient and safe solutions to complex operational challenges like sequencing aircraft or routing flights. While solving large MILPs can be computationally intensive, ongoing advances in algorithms and solvers continue to expand their applicability in making our skies operate more smoothly.

ATM Optimization Glossary

MILP: Mixed Integer Linear Programming, an optimization technique using both integer and continuous variables
TMA: Terminal Maneuvering Area, the airspace surrounding an airport where arriving aircraft are sequenced for landing
ASP: Aircraft Arrival Scheduling Problem, the optimization challenge of sequencing aircraft for landing
Wake Turbulence Categories: Classifications of aircraft based on the turbulence they generate, determining required separation distances
NP-hard: A class of computational problems for which no efficient solution algorithm is known