The traffic flow management rerouting problem in air traffic control: A dynamic network flow approach

We address the problem of determining how to reroute aircraft in the air tr affic control system when faced with dynamically changing weather condition s. The overall objective of this problem is the minimization of delay costs . This problem is of primary concern in the European air traffic control sy stem and in particular regions within the US air traffic control system. We present an integrated mathematical programming approach that consists of s everal methodologies. To address the high dimensionality, we begin by prese nting an aggregate model, in which the problem is formulated as a dynamic, multicommodity, integer network flow problem with certain side constraints. Using Lagrangian relaxation, we generate aggregate flows. We decompose the aggregate flows into a collection of flight paths for individual aircraft using a randomized rounding heuristic. This collection of paths is then use d in a packing integer programming formulation, the solution of which gener ates feasible and near-optimal routes for individual flights. The overall L agrangian Generation Algorithm is used to solve real problems in the southw estern portion of United States. In computational experiments, the solution s returned by our algorithm are within 1% of the corresponding lower bounds .