THE MULTI-AIRPORT GROUND-HOLDING PROBLEM IN AIR-TRAFFIC-CONTROL

Motivated by the important problem of congestion costs (they were esti mated to be $ 2 billion in 199 1) in air transportation and observing that ground delays are more preferable than airborne delays, we have f ormulated and studied several integer programming models to assign gro und-holding delays optimally in a general network of airports, so that the total (ground plus airborne) delay cost of all flights is minimiz ed. All previous research on this problem has been restricted to the s ingle-airport case, which neglects ''down-the-road'' effects due to tr ansmission of delays between successive flights performed by the same aircraft. We formulate several models, and then propose a heuristic al gorithm which finds a feasible solution to the integer program by roun ding the optimal solution of the LP relaxation. Finally, we present ex tensive computational results with the goal of obtaining qualitative i nsights on the behavior of the problem under various combinations of t he input parameter's. We demonstrate that the problem can be solved in reasonable computation times for networks with at least as many as 6 airports and 3,000 flights.