The Air Traffic Flow Management Problem with Enroute Capacities

THE AIR TRAFFICFLOW MANAGEMENT

PROBLEMWITH

ENROUTE CAPACITIES

DIMITRIS BERTSIMAS and SARAH STOCK PATTERSON

MassachusettsInstitute of Technology, Cambridge,Massachusetts

(Received August 1994; revision received October 1995; accepted May 1996)

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...