OPTIMAL-ALGORITHMS AND A REMARKABLY EFFICIENT HEURISTIC FOR THE GROUND-HOLDING PROBLEM IN AIR-TRAFFIC-CONTROL

Since it is safer and less expensive to absorb delays on the ground, a ir traffic control management tries to limit the duration of airborne delays by holding aircraft previous to departure when congestion at th e airport of destination is anticipated. The problem of assigning appr opriate ground-holds to aircraft is known as the ground-holding proble m. Ground-holding decisions must be implemented in real time and for m ultiple airports; therefore, the speed of solution for algorithms is c ritical. This paper tests static and dynamic optimal solutions, and a very fast heuristic for the assignment of ground-holds in air traffic control. The optimal solutions are based on stochastic linear programm ing. The heuristic incorporates elements of stochastic modeling by uti lizing information conveyed by a probabilistic forecast of airport lan ding capacity, while taking into consideration the dynamic nature of t he problem. In extensive computational experiments based on data for L ogan airport, the heuristic performed significantly better than the op timal static solution, a deterministic solution, and the passive strat egy of no-ground-holds; and within 5% of the optimal dynamic solution at a fraction of the computational time. Due to its remarkable efficie ncy, the stochastic-dynamic heuristic appears to be a promising buildi ng block in the development of fast ground-holding algorithms for the complete network of airports.