COMPUTATIONALLY TRACTABLE STOCHASTIC INTEGER PROGRAMMING MODELS FOR AIR TRAFFIC FLOW MANAGEMENT

dc.contributor.advisorBall, Michael Oen_US
dc.contributor.authorGlover, Charles N.en_US
dc.contributor.departmentApplied Mathematics and Scientific Computationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2010-10-07T06:13:56Z
dc.date.available2010-10-07T06:13:56Z
dc.date.issued2010en_US
dc.description.abstractA primary objective of Air Traffic Flow Management (ATFM) is to ensure the orderly flow of aircraft through airspace, while minimizing the impact of delays and congestion on airspace users. A fundamental challenge of ATFM is the vulnerability of the airspace to changes in weather, which can lower the capacities of different regions of airspace. Considering this uncertainty along with the size of the airspace system, we arrive at a very complex problem. The development of efficient algorithms to solve ATFM problems is an important and active area of research. Responding to predictions of bad weather requires the solution of resource allocation problems that assign a combination of ground delay and route adjustments to many flights. Since there is much uncertainty associated with weather predictions, stochastic models are necessary. We address some of these problems using integer programming (IP). In general, IP models can be difficult to solve. However, if "strong" IP formulations can be found, then problems can be solved quickly by state of the art IP solvers. We start by describing a multi-period stochastic integer program for the single airport stochastic dynamic ground holding problem. We then show that the linear programming relaxation yields integer optimal solutions. This is a fairly unusual property for IP formulations that can significantly reduce the complexity of the corresponding problems. The proof is achieved by defining a new class of matrices with the Monge property and showing that the formulation presented belongs to this class. To further improve computation times, we develop alternative compact formulations. These formulations are extended to show that they can also be used to model different concepts of equity and fairness as well as efficiency. We explore simple rationing methods and other heuristics for these problems both to provide fast solution times, but also because these methods can embody inherent notions of fairness. The initial models address problems that seek to restrict flow into a single airport. These are extended to problems where stochastic weather affects en route traffic. Strong formulations and efficient solutions are obtained for these problems as well.en_US
dc.identifier.urihttp://hdl.handle.net/1903/10961
dc.subject.pqcontrolledOperations Researchen_US
dc.subject.pqcontrolledApplied Mathematicsen_US
dc.subject.pqcontrolledEngineering, Civilen_US
dc.subject.pquncontrolledair traffic flow managementen_US
dc.subject.pquncontrolledground delay programen_US
dc.subject.pquncontrolledinteger programmingen_US
dc.subject.pquncontrolledlinear programmingen_US
dc.subject.pquncontrolledMonge matrixen_US
dc.subject.pquncontrolledstochastic programmingen_US
dc.titleCOMPUTATIONALLY TRACTABLE STOCHASTIC INTEGER PROGRAMMING MODELS FOR AIR TRAFFIC FLOW MANAGEMENTen_US
dc.typeDissertationen_US

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Glover_umd_0117E_11627.pdf
Size:
2.19 MB
Format:
Adobe Portable Document Format