Distributionally Robust Airport Ground Holding Problem under Wasserstein Ambiguity Sets

Haochen Wu, Max Z. Li, Li, Max Z.arXiv 2023 · DOI · arXiv

Abstract: Ground Delay Programs (GDPs) mitigate demand-capacity imbalances by holding flights on the ground when an airport's arrival capacity is reduced, thereby reducing costly airborne holding. A central challenge is that day-to-day demand-capacity balancing relies on accurate predictions of airport capacities. However, these predictions are deeply uncertain: forecast errors, operational disruptions, and climate change-driven shifts in weather severity can induce distribution shifts in capacity outcomes. Thus, policies optimized for a single predicted distribution may be brittle out of sample. We address this challenge by developing a \emph{distributionally robust} framework for the single airport ground holding problem (dr-SAGHP). We also propose a method integrates Kelly's cutting plane method with the integer L-shaped method, and that is applicable more broadly to two-stage distributionally robust integer programs with relatively complete recourse and continuous second-stage decision variables. Our method includes a novel dual bisection and primal recovery algorithm that makes use of the structure of the distributionally robust integer program in order to quickly generate subgradients required by Kelly's cutting plane method. In computational experiments, our proposed algorithm delivers up to two orders-of-magnitude speedups compared to solving the convex reformulation directly, while maintaining negligible optimality gaps. We generate capacity scenarios via Gaussian process regression and evaluate out-of-sample performance by perturbing the posterior mean and variance. The numerical experiment results show that dr-SAGHP delivers significant out-of-sample gains under moderate-to-severe shifts, improving the resilience and effectiveness of GDP decision-making under capacity uncertainty.

Introduction

When an airport's arrival capacity drops—typically due to adverse weather—air traffic managers implement Ground Delay Programs (GDPs). It is significantly safer and more cost-effective to hold an aircraft at its departure gate (ground holding) than to have it circling in a fuel-intensive holding pattern near its destination (airborne holding). However, the effectiveness of these programs depends heavily on accurate capacity predictions.

Traditional stochastic models assume a known probability distribution for airport capacity. In reality, forecast errors and climate change-driven shifts in weather severity introduce "distribution shift," where the actual probability of capacity outcomes differs from the forecast. If a model is optimized for a single, potentially incorrect distribution, the resulting flight schedule becomes "brittle," leading to excessive delays and operational costs when reality deviates from the forecast. This paper introduces a Distributionally Robust Optimization (DRO) framework to address this "uncertainty about uncertainty."

Methodology

The researchers developed the distributionally robust single airport ground holding problem (dr-SAGHP). Instead of optimizing for a single predicted distribution, the DRO framework optimizes for the worst-case distribution within a "neighborhood" of possibilities, defined by a Wasserstein Ambiguity Set. This set encompasses all distributions that are statistically close to historical data, providing a hedge against distribution shifts.

To solve the resulting complex two-stage integer program, the authors proposed a novel decomposition algorithm (K-IL) that combines Kelly’s Cutting Plane method with the Integer L-shaped method. A key innovation is a dual bisection and primal recovery algorithm that rapidly generates the subgradients needed for the cutting plane method by exploiting the problem's structure. The mathematical notation defining the sets, parameters, and decision variables for this model is summarized below:

Notation for the single airport ground holding problem (SAGHP) model.

Empirical Evaluation

The study utilized high-fidelity historical data to validate the framework:

  • FAA ASPM Data: Historical airport capacity and weather factors from 2021–2022.
  • BTS Flight Schedules: Actual flight data for Newark Liberty International Airport (EWR) from August 1, 2023, comprising 543 flights.
  • Gaussian Process Regression (GPR): GPR was used to model the relationship between weather and capacity, generating 1,000 realistic capacity scenarios for testing.

Key Results and Insights

The computational experiments revealed significant advantages for the dr-SAGHP approach:

  • Computational Efficiency: The proposed K-IL algorithm achieved speedups of 12x to 102x compared to solving the standard deterministic equivalent formulation directly. This efficiency makes the robust approach operationally viable for real-time air traffic management.
  • Out-of-Sample Resilience: When tested against severe capacity drops (simulating extreme weather shifts), the distributionally robust model reduced expected costs by up to 27.2% compared to standard stochastic models.
  • Tail Risk Mitigation: The model improved the Conditional Value-at-Risk (CVaR)—a metric for worst-case outcomes—by up to 26%, effectively preventing the most disruptive "nightmare days" at airports.
  • Robustness Saturation: The researchers identified a "saturation regime" where increasing the robustness radius beyond a certain point no longer changes the optimal decision, suggesting a clear "sweet spot" for hedging against uncertainty without being overly conservative.

Conclusion and Future Work

While the dr-SAGHP provides a robust insurance policy against capacity uncertainty, the current study focuses on a single airport. Because delays often ripple through the entire aviation network, future work will aim to extend this framework to Multi-Airport Ground Holding Problems (MAGHP). Additionally, transitioning from a "here-and-now" static decision model to a multi-stage DRO framework could allow for real-time updates as weather forecasts evolve throughout the day. Finally, expanding the model to handle "black swan" events not present in historical training data remains an open challenge for enhancing global aviation resilience.

Summary updated

Abstract

Ground Delay Programs (GDPs) mitigate demand-capacity imbalances by holding flights on the ground when an airport's arrival capacity is reduced, thereby reducing costly airborne holding. A central challenge is that day-to-day demand-capacity balancing relies on accurate predictions of airport capacities. However, these predictions are deeply uncertain: forecast errors, operational disruptions, and climate change-driven shifts in weather severity can induce distribution shifts in capacity outcomes. Thus, policies optimized for a single predicted distribution may be brittle out of sample. We address this challenge by developing a \emph{distributionally robust} framework for the single airport ground holding problem (dr-SAGHP). We also propose a method integrates Kelly's cutting plane method with the integer L-shaped method, and that is applicable more broadly to two-stage distributionally robust integer programs with relatively complete recourse and continuous second-stage decision variables. Our method includes a novel dual bisection and primal recovery algorithm that makes use of the structure of the distributionally robust integer program in order to quickly generate subgradients required by Kelly's cutting plane method. In computational experiments, our proposed algorithm delivers up to two orders-of-magnitude speedups compared to solving the convex reformulation directly, while maintaining negligible optimality gaps. We generate capacity scenarios via Gaussian process regression and evaluate out-of-sample performance by perturbing the posterior mean and variance. The numerical experiment results show that dr-SAGHP delivers significant out-of-sample gains under moderate-to-severe shifts, improving the resilience and effectiveness of GDP decision-making under capacity uncertainty.
BibTeX
@misc{wu2023distributionally,
  author = {Haochen Wu and Max Z. Li and Li, Max Z.},
  title = {{Distributionally Robust Airport Ground Holding Problem under Wasserstein Ambiguity Sets}},
  year = {2023},
  eprint = {2306.09836},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.09836},
}
Figure