Motivated by the important problem of congestion costs (they were estimated to be $2 billion in 1991) in air transportation and observing that ground delays are more preferable than airborne delays, we have formulated and studied several integer programming models to assign ground-holding delays optimally 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 formulate several models, and then propose a heuristic algorithm which finds a feasible solution to the integer program by rounding the optimal solution of the LP relaxation. Finally, we present extensive computational results with the goal of obtaining qualitative insights on the behavior of the problem under various combinations of the input parameters. 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. Congestion problems are becoming increasingly I ~~ acute in many major European and American airports. For European airlines, the total yearly delay cost due to congestion (including cost to passengers) was estimated to be $5 billion in 1989 (Terrab 1990). For U.S. airlines, the direct delay cost due to congestion is claimed to amount to approximately $2 billion per year. Given the fact that the total profits of the U.S. airline industry rarely exceed $1 billion, congestion problems are a phenomenon of undeniable significance. Limited capacity is the major cause of congestion. The problem with airport capacity is that it is highly variable, because it is heavily influenced by, among other factors, weather conditions (visibility, wind, precipitation). It is not unusual to encounter 2:1 and even 3:1 ratios between the highest and the lowest capacity of an airport. Solution approaches to this problem vary according to the contemplated time horizon. Long-term approaches include construction of additional airports, construction of additional runways at existing airports, improved air traffic control technologies and procedures and use of larger aircraft. Medium-term approaches include modification of the temporal pattern of aircraft flow to eliminate periods of "peak" demand. Short-term approaches have a planning horizon of 6-12 hours and include, most importantly, ground-holding policies. These policies are motivated by the fundamental fact that airborne delays are much costlier than ground delays, because the former include fuel, maintenance, depreciation, and safety costs. Thus, the premise underlying ground-holding policies is that one may hold an aircraft on the ground before take-off so that, when the aircraft arrives at its destination, it will not have to wait in the air before landing. Ground-holding has been in use for several years. The Federal Aviation Administration operates an Air Traffic Control System Command Center (ATCSCC, formerly called the Central Flow Control Facility) in Washington, D.C., equipped with outstanding information-gathering capabilities. ATCSCC, however, relies primarily on the judgment of its expert air traffic controllers rather than on any decision-support or optimization models to develop flow management and ground-holding strategies. The problem of determining how much (if at all) each aircraft must be held on the ground before takeoff (and also, possibly, in the air during the flight, e.g., by means of a speed reduction en route) to minimize the total (ground plus airborne) delay cost will be referred to as the ground-holding problem (GHP). Static and dynamic versions of the GHP can be distinguished. In the static versions, the ground (and airborne) holds are decided once at the beginning of Because each of a large number of aircraft performs more than one flight on any given day, "network" (or "down-the-road") effects may be important: When a specific aircraft is delayed, in many cases the next flight performed by the same aircraft will also be delayed. Moreover, at a hub airport, a late-arriving aircraft may delay the departure of several flights, given current airline scheduling practices which emphasize passenger transfers. To the best of our knowledge, previous research on the GHP has neglected network effects, and has been restricted to the single-airport problem. Odoni (1987) seems to be the first to have given a systematic description of the problem. Andreatta and Romanin-Jacur (1987) proposed a dynamic programming algorithm for the single-airport static probabilistic GHP with one time period. Terrab proposed an efficient algorithm to solve the single-airport static deterministic GHP, as well as several heuristics for the single-airport probabilistic GHP. He also suggested a two-airport formulation and a closed three-airport formulation for the static deterministic GHP. Finally, Richetta (1 991) dealt with the single-airport dynamic probabilistic GHP. It seems that no significant research has been done to date concerning the effects of ground-holding policies on an entire network of airports. In this paper, the multi-airport GHP is addressed for the first time. By using a mathematical programming approach, we solve the deterministic network GHP in a general setting. We propose several integer programming formulations which have the important advantages of being remarkably simple, while capturing the essential apects of the problem, and sufficiently flexible to accommodate various degrees of modeling detail. We present several structural insights on the parameters that influence the problem, based on extensive computational experience. Most importantly, our approach enables one to solve realistic-size problems involving, e.g., 6 airports and 3,000 flights in reasonable computation times. Our approach can thus be used to assign ground holds for at least a major part of the network of the most important U.S. or European airports. Although we focus on the static multi-airport GHP, our algorithms could also be used dynamically by solving the problem, say, every two hours, as better capacity estimates become available. The outline of this paper is as follows. Section 1 defines the problem and gives integer programming formulations of three versions of it. Section 2 proposes a heuristic based on the solution of a linear programming relaxation. Section 3 gives insights on the parameters influencing the behavior of the problem, based on an extensive series of actual runs. Finally, Section 4 summarizes the results of the paper and points out directions for future research.
Then, the Multi-Airport Ground Holding Problem was addressed by REF .
The Multi-Airport GroundHolding Problem in Air Traffic Control
Computer Science Mathematics