The air traffic flow management problem with enroute capacities

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.