The Traffic Flow Management Rerouting Problem in Air Traffic Control: A Dynamic Network Flow Approach

Dimitris Bertsimas and Sarah Stock Patterson
Additional contact information
Dimitris Bertsimas: Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Sarah Stock Patterson: The Fuqua School of Business, Duke University, Durham, North Carolina 27708

Transportation Science, 2000, vol. 34, issue 3, 239-255

Abstract: We address the problem of determining how to reroute aircraft in the air traffic control system when faced with dynamically changing weather conditions. The overall objective of this problem is the minimization of delay costs. This problem is of primary concern in the European air traffic control system and in particular regions within the US air traffic control system. We present an integrated mathematical programming approach that consists of several methodologies. To address the high dimensionality, we begin by presenting 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 used in a packing integer programming formulation, the solution of which generates feasible and near-optimal routes for individual flights. The overall Lagrangian Generation Algorithm is used to solve real problems in the southwestern portion of United States. In computational experiments, the solutions returned by our algorithm are within 1% of the corresponding lower bounds.

Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (39)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.34.3.239.12300 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:34:y:2000:i:3:p:239-255

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().