Optimization Approaches for the Dynamic Airspace Configuration Problem

This thesis focuses on a real-world problem arising in the context of air traffic control, where an efficient management of the airspace structure plays a crucial role in maximizing the air traffic volume that can be safely monitored in a specific region. Currently, a set of sectors is available for every airspace region, and a subset of non-overlapping sectors that partitions such region is called a configuration. To guarantee safe and constant monitoring of the flight operations, each sector has a capacity, that is, the maximum air traffic volume it can absorb; a configuration must be defined at each moment in time during the day, such that, ideally, the traffic volume in each sector does not exceed the capacity. Therefore, optimizing the airspace structure in a given time-frame is equivalent to finding the optimal configuration sequence. Specifically, our goal is to determine the configuration sequence that minimizes the total traffic excess, that is computed with respect to the capacity of sectors. In order to guarantee the viability of the sequence from an operational point of view, we formulate some families of constraints that regularize the sequence’s structure and avoid frequent switching, guaranteeing a minimum period of uninterrupted activity for configurations (and, optionally, sectors) and avoiding the reactivation of a configuration after a short time. We also take into account possible restrictions on the compatibility between configurations, only allowing transitions between configurations with a similar structure. We propose, and compare, two Integer Linear Programming formulations to solve the problem at hand, and focus on the polyhedral properties of that one that shows better computational performance. We also study resource constrained shortest path algorithms to tackle the problem on a suitable directed graph and investigate its computational com- plexity. Additionally, we develop two robust optimization frameworks to account for uncer- tainty in the traffic excess parameters, under two different formulations for the uncertainty sets. All the proposed models and frameworks have been tested on real-life instances, and the results we obtained prove that they are suitable for application in the pre-tactical phase of Air Traffic Management.