Multistage Air Traffic Flow Management under Capacity Uncertainty: A Robust and Adaptive Optimization Approach

摘要

In this paper, we study the first application of robust and adaptive optimization in the Air Traffic Flow Management (ATFM) problem. The existing models for network-wide ATFM assume deterministic capacity estimates across airports and sectors without taking into account the uncertainty in capacities induced by weather. We introduce a weather-front based approach to model the uncertainty inherent in airspace capacity estimates resulting from the impact of a small number of weather fronts moving across the National Airspace (NAS). The key advantage of our uncertainty set construction is the low-dimensionality (uncertainty in only two parameters govern the overall uncertainty set for each airspace element). We formulate the consequent ATFM problem under capacity uncertainty within the robust and adaptive optimization framework and propose tractable solution methodologies. Our theoretical contributions are as follows: i) we propose a polyhedral description of the convex hull of the discrete uncertainty set; ii) we prove the equivalence of the robust problem to a modified instance of the deterministic problem; and iii) we solve optimally the LP relaxation of the adaptive problem using piece-wise affine policies where the number of pieces in an optimal policy are governed by the number of extreme points in the uncertainty set. A particularly attractive feature is that for most practically encountered instances, an affine policy suffices to solve the adaptive problem optimally. Finally, we report empirical results from the proposed models on real world flight schedules augmented with simulated weather fronts that illuminate the merits of our proposal. The key insights from our computational results are: i) the robust problem inherits all the attractive properties of the deterministic problem (e.g., superior integrality properties and fast computational times); and ii) the price of robustness and adaptability is typically small.