Institute for Systems Research Technical Reports
Permanent URI for this collectionhttp://hdl.handle.net/1903/4376
This archive contains a collection of reports generated by the faculty and students of the Institute for Systems Research (ISR), a permanent, interdisciplinary research unit in the A. James Clark School of Engineering at the University of Maryland. ISR-based projects are conducted through partnerships with industry and government, bringing together faculty and students from multiple academic departments and colleges across the university.
Browse
Search Results
Item Measuring Ground Delay Program Effectiveness Using the Rate Control Index(2000) Ball, Michael O.; Hoffman, Robert L.; Ball, Michael O.; ISR; NEXTORThe objective of Air Traffic Flow Management is to maintain safe and efficient use of airspace and airports by regulating the flow of traffic. In this paper, we introduce a single-valued metric for post-operatively rating the performance of achieved traffic flow against targeted traffic flow. We provide variations on the metric, one of which factors out stochastic conditions upon which a plan is formulated, and show how these improve on current traffic control analysis techniques. The core of the metric is intuitive and simple, yet leads to an interesting optimization problem that can be efficiently solved via dynamic programming. Numerical results of the metric are given as well as a sample of the type of analysis that should follow a low rating by the metric. Although this metric was originally developed to rate the performance of Ground Delay Programs, it is equally applicable to any setting in which the flow of discrete objects such as vehicles is controlled and later evaluated.Item Collaborative Decision Making in Air Traffic Management: Current and Future Research Directions(2000) Ball, Michael O.; Hoffman, Robert L.; Chen, Chien-Yu; Vossen, Thomas; ISR; NEXTORCollaborative Decision Making (CDM) embodies a new philosophy for managing air traffic. The initial implementation of CDM in the US has been aimed at Ground Delay Program Enhancements (GDP-E). However, the underlying concepts of CDM have the potential for much broader applicability.This paper reviews on-going and proposed CDM research streams. The topic areas discussed include: ground delay program enhancements; collaborative routing; performance monitoring and analysis; collaborative resource allocation mechanisms; game theory models for analyzing CDM procedures and information exchange; collaborative information collection and distribution.
Item The Rate Control Index for Traffic Flow(2000) Ball, Michael O.; Hoffman, Robert L.; Ball, Michael O.; ISR; NEXTORThe objective of Air Traffic Flow Management is to maintain safe and efficient use of airspace and airports by regulating theflow of traffic. In this paper, we introduce a single-valued metric for post-operatively rating the performance ofachieved traffic flow against targeted traffic flow. We provide variations on the metric, one of which factors out stochastic conditions upon which a plan is formulated, and show how those improve on current traffic control analysis techniques.The core of the metric is intuitive and simple, yet leads to an interesting optimization problem that can be efficiently solved via dynamic programming. Numerical results of the metric are given as well as a sample of the type of analysis that should follow a low rating by the metric.
Although this metric was originally developed to rate the performance of GroundDelay Programs, it is equally applicable to any setting in which the flow of discrete objects such as vehicles is controlled and later evaluated.
Item The Static Stochastic Ground Holding Problem with Aggregate Demands(1999) Ball, Michael O.; Hoffman, Robert L.; Odoni, A.; Rifkin, R.; Ball, Michael O.; ISR; NEXTORThe ground delay program is a mechanism used to decrease the rate of incoming flights into an airport when it is projected that arrival demand into the airport will exceed capacity. In this paper, we present an integer programming model for plannning ground delay programs. The model considers a stochastic capacity profile which is represented by a set of airport capacity scenarios and their probabilities. Both the demand on the airport and the output of the model are represented at an aggregate level in terms of number of flights per unit time. This allows the model to be used in conjunction with arbitrarily complex preprocesses for allocating individual flights to slots. It was specifically designed to be used in the Collaborative Decision Making setting where individual flight assignments result from an iterative process involving both the airlines and traffic flow managers. We show that the linear programming dual of the model can be transformed into a network flow problem. This implies that the integer program can be solved efficiently using linear programming or network flow models.Item Integer Programming Models for Ground-Holding in Air Traffic Flow Management(1998) Hoffman, Robert L.; Ball, M.; ISR; NEXTORIn this dissertation, integer programming models are applied tocombinatorial problems in air traffic flow management. For the two problemsstudied, models are developed and analyzed both theoretically andcomputationally. This dissertation makes contributions to integerprogramming while providing efficient tools for solving air traffic flowmanagement problems.Currently, a constrained arrival capacity situation at an airport in theUnited States is alleviated by holding inbound aircraft at their departuregates. The ground holding problem (GH) decides which aircraft to hold on theground and for how long.
This dissertation examines the GH from twoperspectives. First, the hubbing operations of the airlines are consideredby adding side constraints to GH. These constraints enforce the desire ofthe airlines to temporally group banks of flights. Five basic models andseveral variations of the ground holding problem with banking constraints(GHB) are presented. A particularly strong, facet-inducing model of thebanking constraints is presented which allows one to solve large instancesof GHB in less than half an hour of CPU time.
Secondly, the stochastic nature of arrival capacity is modeled by an integerprogram that provides the optimal trade-off between ground delay andairborne delay. The dual network properties of the integer program allow oneto obtain integer solutions directly from the linear programming relaxation.This model is designed to work in close conjunction with the most recentoperational paradigms developed by the joint venture between the FAA and theairlines known as collaborative decision making (CDM). Both these paradigmsand the impact of CDM on the decision making process in air traffic flowmanagement are thoroughly discussed.
The work on banking constraints analyzes several alternative formulations.It involves the use of auxiliary decision variables, the application ofspecial branching techniques and the use of facet-inducing constraints. Thenet result is to reduce by several orders of magnitude the computation timeand resources necessary to solve the integer program to optimality. The workon the stochastic ground holding problem shows that the model's underlyingmatrix is totally unimodular by transforming the dual into a network flowmodel.
Item Optimization Model with Fairness Objective for Air Traffic Management(1998) Butler, Taryn D.; Ball, Micheal; ISR; NEXTORWith the ever-increasing congestion at airports around the world, studies into ways of minimizing delay costs on the ground while meeting the goals of the airlines are necessary. When arrival capacities are reduced at major airports, the Federal Aviation Administration (FAA) issues revised departure/arrival times to prevent congestion at restricted airports. This is referred to as the National Ground Delay Program Problem. A new approach to developing ground delay programs, called Collaborative Decision Making (CDM), is being developed. CDM goals include more information exchange and greater participation on the part of the airlines in determining landing slot allocations. This thesis develops a model specifically for the CDM setting. A key element is the inclusion of a fairness criterion within the underlying optimization model. The fairness criterion seeks to "pay back" an airline for time slots that it is owed but cannot make use of due to mechanical or other difficulties. It also attempts to provide incentives to the airlines to increase the exchange of information. This thesis investigates the Ground Delay Problem relative to a single airport. Different formulations of the integer programming model are given that take into account airport capacities and airline goals and experiments are conducted with realistic data to determine the solvability of the problem. Results for this model are compared with output from the Flight Schedule Monitor (FSM), the CDM decision support tool.Item A Comparison of Formulations for the Single-Airport Ground Holding Problem with Banking Constraints(1998) Hoffman, Robert L.; Ball, Michael O.; ISR; NEXTORBoth the single-airport ground-holding problem (GH) and the multi-airport ground-holding problem can be extended by the addition of banking constraints to accommodate the hubbing operations of major airlines. These constraints enforce the desire of airlines to land certain groups of flights, called banks, within fixed time windows, thus preventing the propagation of delays throughout their entire operation. GH can be formulated as a transportation problem and readily solved. But in the presence of banking constraints, GH becomes a difficult integer programming problem. In this paper, we construct five different models of the single-airport ground holding problem with banking constraints (GHB). The models are evaluated both computationally and analytically. For two of the models, we show that the banking constraints induce facets of the convex hull of the set of integer solutions. In addition, we explore a linear transformation of variables and a branching technique.