Mathematical Optimization of Matching Problems with Precedence Constraints: An Application to Runway Scheduling

Runways are one of the most valuable resources in air traffic management. For a runway used in mixed-mode, exact times and sequences of arriving and departing aircraft are usually determined by two scheduling components which are linked by a coordination tool. In this work, we will explore the question of how useful this approach is, for the specific case of the so-called runway scheduling problem with precedence constraints. We examine two opposing cases profoundly. On the one hand, namely in the best-case scenario, both planners work together and can be seen as an integrated planning tool. This case is modeled using a mixed-integer program (MIP). Structural investigations and the resulting cutting planes lead to algorithms with shorter computing times in the holistic approach. On the other hand, we have the worst-case scenario, in which the two planners act as opponents. This scenario is modeled using quantified integer programming (QIP), simulating a game of the two competing planners. As the gap between makespans of best and worst case schedules is huge, the obtained results form the basis for deciding whether the development, implementation, and maintenance of an integrated arrival and departure planner at airports will pay off. This means that, while keeping the same level of safety, optimal plans can be computed quickly, and the throughput on the scarce resource runway can be increased considerably.