Deterministic and Stochastic Optimization For Heterogeneous Decision Phases In The Air Traffic Domain

Scheduling is a complex activity that is needed in a large number of fields, which can involve heterogeneous factors and that may have different goals. In this thesis, scheduling problems that involve the air traffic field at different phases are faced. At each phase, the different characteristics of the problems are considered, devoting special attention to uncertainty. Given the heterogeneous characteristics and goals of the problems, different models and methods are proposed to solve each of them. The first analyzed phase is the strategic phase. It takes place around six months before the operation of flights, when they need to be assigned scheduled departure and arrival times at the airports where they operate. Future capacity realizations are very difficult to forecast at this phase, as capacity is influenced by weather conditions. A two-stage stochastic programming model with two alternative formulations is proposed to capture this uncertainty. Since the number of scenarios may be extreme, Sample Average Approximation is used to solve the model. The utilization of the proposed model allows to identify advantageous tradeoffs between schedule/request discrepancies, i.e., the distance between the allocated schedule and airline requests, and operational delays. This tradeoff can result in substantial reductions of the cost of delays for airlines. In the computational experiments, delays were reduced up to 45% on an instance representing a network of European airports. The second considered phase is the tactical phase, which takes place on the day of operation of flights. At this time, complete flight plans need to be defined, specifying the route and operation times of flights. This is done considering two different sources of uncertainty. First, uncertainty on capacity availability is taken into account, similarly to the strategic phase. However, the number of capacity realization scenarios is now small, as they can be defined using available weather forecasts. The problem of minimizing delay costs considering this source of uncertainty is the Stochastic Air Traffic Flow Management problem. A two-stage stochastic programming model with two alternative formulations is proposed to solve this problem. An ad-hoc heuristic that takes advantage of the good structure of the model is used to solve problem instances within short computation times. The analysis of the Value of the Stochastic Solution shows that the proposed stochastic model can significantly reduce delay costs when bad weather affects the whole network. Second, the implicit uncertainty on the departure time of flights is taken into account. This kind of uncertainty involves operations that may cause a delay on the scheduled departure time of a flight. The flexibility of the scheduled time of departure, as well as the other flight operations, is determined defining time windows within which flights are granted capacity resources to operate. The narrower a time window, the more critical a flight operation. The problem of minimizing delay cost and maximizing time windows is faced by the Air Traffic Flow Management Problem with Time Windows. The problem is formulated with two alternative deterministic models, one of which is able to provide time windows in 40" on average for instances involving over 6,000 flights. Less conservative criteria to reserve capacity within time windows can also be used. Despite not granting the possibility for a flight to execute its operations at every instant of a time window, the implementation of these alternative criteria is shown to be viable. In fact, less than 0.14% of flights were subject to capacity shortages in the analyzed cases. Finally, the operational phase takes place when operations are being executed. The goal at this phase is to manage the final departure times announced by flights - with uncertain information becoming deterministic - allowing them to depart at the announced time even if this time exceeds the assigned departure time window. This problem is named Real Time Flight Rescheduling with Time Windows. Resources are provided to flights that need them by reallocating previously reserved capacity with an algorithm that follows the Ration-By-Schedule mechanism. Both the practical usage of time windows and the impact of collaboration among airlines are studied. While airline collaboration limits time window flexibility up to some time before the scheduled departure of a flight, it can allow to reduce additional flight delays by over 14%. This thesis is a first work that involves determining flight schedules from the moment of their definition to the time of execution of flights. Providing cost reductions by considering the different factors that influence each decision phase can lead to a global improvement of the management of flight operations, whose delays are very expensive in practice for airlines.