Throughout the United States and Europe, demand for airport use has been increasing rapidly, while airport capacity has been stagnating. Over the last ten years the number of passengers has increased by more than 50 percent and is expected to continue increasing at this rate. Acute congestion in many major airports has been the unfortunate result. For U.S. airlines, the expected yearly cost of the resulting delays is currently estimated at $3 billion. In order to put this number in perspective, the total reported losses of all U.S. airlines amounted to approximately $2 billion in 1991 and $2.5 billion in 1990. Furthermore, every day 700 to 1100 flights are delayed by 15 minutes or more. European airlines are in a similar plight. Optimally controlling the flow of aircraft either by adjusting their release times into the network (ground-holding) or their speed once they are airborne is a cost effective method to reduce the impact of congestion on the air traffic system. This paper makes the following contributions: (a) we build a model that takes into account the capacities of the National Airspace System (NAS) as well as the capacities at the airports, and we show that the resulting formulation is rather strong as some of the proposed inequalities are facet defining for the convex hull of solutions; (b) we address the complexity of the problem; (c) we extend that model to account for several variations of the basic problem, most notably, how to reroute flights and how to handle banks in the hub and spoke system; (d) we show that by relaxing some of our constraints we obtain a previously addressed problem and that the LP relaxation bound of our formulation is at least as strong when compared to all others proposed in the literature for this problem; and (e) we solve large scale, realistic size problems with several thousand flights. Throughout the United States and Europe, demand for airport use has been increasing rapidly during recent years, while airport capacity has been stagnating. Over the last ten years the number of passengers has increased by more than 50 percent and is expected to continue increasing at this rate, while no appreciable increase in capacity is expected. Acute congestion in many major airports has been the unfortunate result. For U.S. airlines, the expected yearly cost of the resulting delays is currently estimated at $3 billion. In order to put this number in perspective, the total reported losses of all U.S. airlines amounted to approximately $2 billion in 1991 and $2.5 billion in 1990. Furthermore, every day 700 to 1100 flights are delayed by 15 minutes or more. European airlines are in a similar plight. Thus, congestion is a problem of undeniable practical significance. Faced with the realities of congestion, the FAA has been using ground-holding policies to reduce delay costs. These short-term policies consider airport capacities and flight schedules as fixed for a given time period, and adjust the flow of aircraft on a real time basis by imposing "ground holds" on certain flights. Such a flight is then held on the ground at its departure airport even if it is otherwise ready for takeoff. Ground-holding makes sense in the following situation. Suppose it has been determined that if an aircraft departs on time, then it will encounter congestion, incurring an airborne delay as it awaits landing clearance at its destination airport. However, by delaying its departure, the aircraft will arrive at its destination at a later time when minimal congestion is expected, thus, incurring no airborne delay. Therefore, the objective of ground-holding policies is to "translate" anticipated airborne delays to the ground. The effectiveness of ground-holding policies lies in the following two fundamental facts. First, while a flight is airborne it incurs costs such as fuel and safety costs that are not applicable before the flight takes off. These costs make airborne delays much costlier than ground delays. Second, airport capacity is highly variable due to its heavy dependence on the weather (visibility, wind, precipitation, cloud ceiling). It is not unusual for the capacity of an airport to be reduced by 50 percent in inclement weather. Given these two facts, there is significant potential to reduce costs when adjusting aircraft flow as weather (hence airport capacity) forecasts change in such a way that ground delays are substituted for the much costlier airborne delays. Currently, the FAA implements a national groundholding policy. This policy uses a computerized procedure based on a first-come, first-served rule, in order to select appropriate ground-holds. These selections are further enhanced through the experience of its air traffic controllers. In the last decade, several models have been developed that use optimization techniques to improve upon current practices. We will briefly review these developments. A Taxonomy of Models. In Odoni (1987), the problem of scheduling flights in real time in order to minimize congestion costs was first conceptualized and introduced. Since
This lead to introduce the Air Traffic Flow Management Problem with sector capacities and rerouting REF .
The air traffic flow management problem with enroute capacities
Oper. Res
Computer Science Mathematics