Integer Programming Models for Ground-Holding in Air Traffic Flow Management

Abstract

In this dissertation, integer programming models are applied tocombinatorial problems in air traffic flow management. For the two problemsstudied, models are developed and analyzed both theoretically andcomputationally. This dissertation makes contributions to integerprogramming while providing efficient tools for solving air traffic flowmanagement problems.<p>Currently, a constrained arrival capacity situation at an airport in theUnited States is alleviated by holding inbound aircraft at their departuregates. The ground holding problem (GH) decides which aircraft to hold on theground and for how long.<p>This dissertation examines the GH from twoperspectives. First, the hubbing operations of the airlines are consideredby adding side constraints to GH. These constraints enforce the desire ofthe airlines to temporally group banks of flights. Five basic models andseveral variations of the ground holding problem with banking constraints(GHB) are presented. A particularly strong, facet-inducing model of thebanking constraints is presented which allows one to solve large instancesof GHB in less than half an hour of CPU time.<p>Secondly, the stochastic nature of arrival capacity is modeled by an integerprogram that provides the optimal trade-off between ground delay andairborne delay. The dual network properties of the integer program allow oneto obtain integer solutions directly from the linear programming relaxation.This model is designed to work in close conjunction with the most recentoperational paradigms developed by the joint venture between the FAA and theairlines known as collaborative decision making (CDM). Both these paradigmsand the impact of CDM on the decision making process in air traffic flowmanagement are thoroughly discussed.<p>The work on banking constraints analyzes several alternative formulations.It involves the use of auxiliary decision variables, the application ofspecial branching techniques and the use of facet-inducing constraints. Thenet result is to reduce by several orders of magnitude the computation timeand resources necessary to solve the integer program to optimality. The workon the stochastic ground holding problem shows that the model's underlyingmatrix is totally unimodular by transforming the dual into a network flowmodel.