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 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.Item Integrating Tradeoff Analysis and Plan-Based Evaluation of Designs for Microwave Modules(1996) Trichur, Vinai S.; Ball, Michael O.; Baras, John S.; Hebbar, Kiran; Minis, Ioannis; Nau, Dana S.; Smith, Stephen J.J.; ISRPreviously, we have described two systems, EDAPS and EXTRA, which support design and process planning for the manufacture of microwave modules, complex devices with both electrical and mechanical attributes. EDAPS integrates electrical design, mechanical design, and process planning for both mechanical and electrical domains. EXTRA accesses various component and process databases to help the user define design and process options. It then supports the user in choosing among these options with an optimization bases tradeoff analysis module.In this paper, we describe our current work towards the integration and enhancement of the capabilities of EDAPS and EXTRA. We integrate EXTRA's functionality with the initial design step of EDAPS. in the resultant system, the user, supported by an enhanced tradeoff analysis capability, can select and describe a promising preliminary design and process plan based on the analysis of a variety of alternatives from both an electrical and mechanical perspective. This preliminary design is then subjected top further analysis and refinement using existing EDAPS capabilities. In addition to the integration of these two systems, specific new functions have been developed, including tradeoff analysis over a much broader set of criteria, and the ability of the tradeoff module to query the process planner to determine costs of individual options.
Item An Integrated Model for Manufacturing Shop Design(1995) Ioannou, George; Minis, Ioannis; ISRThis paper presents an integer programming formulation for the manufacturing shop design problem, which integrates decisions concerning the layout of the resource groups on the shop floor with the design of the material handling system. The model reflects critical practical design concerns including the capacity of the flow network and of the transporters, and the tradeoff between fixed (construction and acquisition) and variable (operational) costs. For realistic industrial cases, the size of the problem prevents the solution through explicit or implicit enumeration schemes. The paper addresses this limitation by decomposing the global model into its natural components. The resulting submodels are shown to be standard problems of operations research. The decomposition approach provides ways to solve the integrated shop design problem in an effective manner.Item Reliability, Covering and Balanced Matrices(1993) Ball, Michael O.; Lin, Feng L.; ISRThe paper addresses a certain generalized covering integer program. The original application that motivated the study of this problem was an emergency services vehicle location problem. In this paper, we show that the same model can be applied to a general system reliability optimization problem. The main contribution of this paper is the definition and analysis of a reformulation strategy. Specifically, we show how the original generalized covering problem can be reformulated as a set covering problem. We then show that for a particular special case the associated constraint matrix is balanced. This in turn implies that the integer program can be efficiently solved using linear programming techniques. This result together with the good computational results reported in a previous paper constitute substantial evidence as to the overall effectiveness of the reformulation strategy. Furthermore, they indicate that the generalized covering model addressed can be effectively solved in a fairly wide range of cases.Item A Reliability Model Applied to Emergency Service Vehicle Location(1992) Ball, Michael O.; Lin, Feng L.; ISRThis article proposes a reliability model for the emergency service vehicle location problem. Emergency services planners must solve the strategic problem of where to locate emergency services stations and the tatical problem of the number of vehicles to place in each station. We view the problem as one of optimizing the reliability of a system, where system failure is interpreted as the inability of a vehicle to respond to a demand call within an acceptable amount of time. Our model handles the stochastic problem aspects in a more explicit way than previous models in the literature. Based on a reliability bound on the probability of system failure, we derive a 0-1 integer programming (IP) optimization model. To solve it, we propose valid inequalities as a preprocessing technique to augment the IP and solve the IP using a branch-and-bound-procedure. Our computational results show that the preprocessing techniques and highly effective. We feel that the reliability model should have applications beyond this context and hope that it till lead to ideas for similar optimization models for designing other systems.