Multiairport Ground Holding Problem: A Computational Evaluation of Exact Algorithms

Congestion in the air traffic network is becoming an increasingly serious problem that causes inconvenience to passengers, losses to airlines and, last but not least, threats to airspace safety. One way of reducing the amount of congestion is to use Ground Holding policies, i.e., to impose on selected aircraft a ground holding prior to their departure so that congestion during peak periods of time may be smoothed away. In this paper we restrict our attention to the Multiairport Ground Holding problem, where congestion may arise only at the airports due to limited arrival capacity. There are a few algorithms that, under suitable hypotheses, find an “optimal” policy for the Multiairport Ground Holding problem. In this paper we evaluate and compare computationally three of them, namely, the one recently proposed by Vranas, Bertsimas and Odoni, the one suggested by Andreatta and Tidona and that due to Bertsimas and Stock. The computational evaluation is based on two sets of test problems. The first set consists of seven problems taken from the literature. The second set consists of 32 “realistic” test problems. The results indicate the superiority of the Bertsimas and Stock approach among the three models considered.