Theses and Dissertations from UMD
Permanent URI for this communityhttp://hdl.handle.net/1903/2
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
3 results
Search Results
Item PROBLEMS ORIGINATING FROM THE PLANNING OF AIR TRAFFIC MANAGEMENT INITIATIVES(2018) Estes, Alexander; Ball, Michael O; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)When weather affects the ability of an airport to accommodate flights, a ground delay program is used to control the rate at which flights arrive at the airport. This prevents excessive congestion at the airport. In this thesis, we discuss several problems arising from the planning of these programs. Each of these problems provides insight that can be applied in a broader setting, and in each case we develop generalizations of these results in a wider context. We show that a certain type of greedy policy is optimal for planning a ground delay program when no air delays are allowed. More generally, we characterize the conditions under which policies are optimal for a dynamic stochastic transportation problem. We also provide results that ensure that certain assignments are optimal, and we apply these results to the problem of matching drivers to riders in an on-demand ride service. When flights are allowed to take air delays, then a greedy policy is no longer optimal, but flight assignments can be produced by solving an integer program. We establish the strength of an existing formulation of this problem, and we provide a new, more scalable formulation that has the same strength properties. We show that both of these methods satisfy a type of equity property. These formulations are a special case of a dynamic stochastic network flow problem, which can be modeled as a deterministic flow problem on a hypergraph. We provide strong formulations for this general class of hypergraph flow problems. Finally, we provide a method for summarizing a dataset of ground delay programs. This summarization consists of a small subset of the original data set, whose elements are referred to as "representative" ground delay programs. More generally, we define a new class of data exploration methods, called "representative region selection" methods. We provide a framework for evaluating the quality of these methods, and we demonstrate statistical properties of these methods.Item Parallel and Serial Algorithms for Vehicle Routing Problems(2008) Groer, Christopher Sebastian; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The vehicle routing problem (VRP) is a widely studied combinatorial optimization problem that has many applications. Due to its intrinsic difficulty and the size of problems encountered in practice, most solution methods for the VRP are heuristic in nature and lead to high quality, yet probably not optimal solutions. When one considers the additional constraints that can be encountered in practice, the need for high quality heuristic methods is clear. We present two new variations of the VRP suggested to us by industry contacts, the Consistent VRP and the Balanced Billing Cycle VRP. We develop solution algorithms that incorporate heuristic methods as well as integer programming. Additionally, we develop a highly effective cooperative parallel algorithm for the classical VRP that generates new best solutions to a number of well-studied benchmark instances. We present extensive computational results and describe the C/C++ library that we developed to solve these vehicle routing problems. We describe the features and design philosophy behind this library and discuss how the framework can be used to implement additional heuristic algorithms and incorporate additional constraints.Item Primal-Dual Algorithms for Combinatorial Optimization Problems(2007-08-10) Mestre, Julian Diego; Khuller, Samir; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Combinatorial optimization problems such as routing, scheduling, covering and packing problems abound in everyday life. At a very high level, a combinatorial optimization problem amounts to finding a solution with minimum or maximum cost among a large number of feasible solutions. An algorithm for a given optimization problem is said to be exact if it always returns an optimal solution and is said to be efficient if it runs in time polynomial on the size of its input. The theory of NP-completeness suggests that exact and efficient algorithms are unlikely to exist for the class of NP-hard problems. Unfortunately, a large number of natural and interesting combinatorial optimization problems are NP-hard. One way to cope with NP-hardness is to relax the optimality requirement and instead look for solutions that are provably close to the optimum. This is the main idea behind approximation algorithms. An algorithm is said to be an r-approximation if it always returns a solution whose cost is at most an r factor away from the optimal cost. Arguably, one of the most important techniques in the design of combinatorial algorithms is the primal-dual schema in which the cost of the primal solution is compared to the cost of a dual solution. In this dissertation we study the primal-dual schema in the design of approximation algorithms for a number of covering and scheduling problems.