The MultiAirport Ground-Holding Problem in Air Traffic Control

In 1986, the total profits of the U.S. airline industry were of the order of $800 million, while its total delay costs due to congestion approached the figure of $2 billion. Motivated by this important problem of congestion costs and observing that ground delays are far more preferable than airborne delays, we have formulated and studied generic integer programming models in order to assign optimal ground holding delays in a general network of airports, so that the total (ground plus airborne) delay cost of all flights is minimized. All previous research on this problem has been restricted to the single-airport case, which neglects "down-the-road " effects due to transmission of delays between successive flights performed by the same aircraft. We give three general pure 0-1 integer programming formulations of the problem, one of which also takes into account the possibility of cancelling flights. 1 We then present a heuristic algorithm which finds a feasible solution to the inte