MULTIAIRPORT GROUND HOLDING PROBLEM - A COMPUTATIONAL EVALUATION OF EXACT ALGORITHMS

Congestion in the air traffic network is becoming an increasingly seri ous problem that causes inconvenience to passengers, losses to airline s and, last but not least, threats to airspace safety. One way of redu cing the amount of congestion is to use Ground Holding policies, i.e., to impose on selected aircraft a ground holding prior to their depart ure so that congestion during peak periods of time may be smoothed awa y. In this paper we restrict our attention to the Multiairport Ground Holding problem, where congestion may arise only at the airports due t o limited arrival capacity. There are a few algorithms that, under sui table hypotheses, find an ''optimal'' policy for the Multiairport Grou nd Holding problem. In this paper we evaluate and compare computationa lly three of them, namely, the one recently proposed by Vranas, Bertsi mas and Odoni, the one suggested by Andreatta and Tidona and that due to Bertsimas and Stock. The computational evaluation is based on two s ets of test problems. The first set consists of seven problems taken f rom the literature. The second set consists of 32 ''realistic'' test p roblems. The results indicate the superiority of the Bertsimas and Sto ck approach among the three models considered.