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
2 results
Search Results
Item Modeling and Solving Arc Routing Problems in Street Sweeping and Snow Plowing(2012) Dussault, Ben; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In arc routing problems, the goal is to determine an optimal path, or set of paths, that traverse a required subset of arcs on a graph with respect to a set of constraints and objective function. The Chinese Postman Problem (CPP) forms the basis for many arc routing problems. Let graph G =(V,A), where V is a set of vertices and A = {(i,j) | i,j in V} is a set of arcs that each connect exactly two vertices, each with its own cost of traversal cij. The objective of the CPP is to construct a least cost path that traverses each arc in A at least once. There are many practical applications for variants of the CPP, including winter street maintenance, and street sweeping that incorporate: [Rural Instances] Rural Postman Problems (RPP) stipulate that only a subset $A_R \subset A$ require traversal, allowing for non-servicing traversal on the rest of the graph. In the context of street sweeping, a street sweeper isn't responsible for sweeping all the streets. [Windy Graphs] In the CPP, the cost of traversal of an arc is the same, regardless of the direction of traversal. In the Windy Postman Problem (WPP), the cost of traversal is asymmetric. That is, it is possible for cij not equal cji. In the context of snow plowing, it is harder to plow uphill than downhill. [Multi-Vehicle] Instead of a single vehicle with a single tour, multiple tours are found for multiple vehicles. This is often accompanied with an objective function that seeks to minimize the cost of the largest cost route. This is motivated by practical applications, which seek to balance the cost of each route. In the case where route cost is measured in time, route balancing minimizes, for example, paid overtime. [Turn Penalties] UPS reported that it saved three million gallons of gasoline annually by avoiding unnecessary left-hand turns, which take longer to perform than going straight or turning right. Instances with turn penalties incorporate costs of turning, in addition to costs of traversal. The Windy Postman Problem (WPP) incorporates windy graphs and the Rural Postman Problem (RPP) incorporates rural instances. The RPP can be extended to include turn penalties (RPPTP). The Windy Rural Postman Problem (WRPP) incorporates instances that are both windy and rural. The WRPP can be extended to the MM k-WRPP which adds k plows. In this dissertation, we extend these variants to new problems with new problem attributes that are practically motivated. Our new attributes are listed below. [Multi-Period] The CPP solves for a single route, which can be interpreted to be traversed in a single day. It is possible that the set of required arcs is too long to service in a single day and therefore must be split among multiple days. In this case, we need to decide which day to assign service to each arc, before routing can take place. [Downhill Instances] In street snow plowing, it is faster to deadhead (traverse without servicing) a street rather than plowing it. In this case, there are different costs for deadheading and plowing a street. Moreover, it takes longer to plow uphill, resulting in four costs: plowing uphill, plowing downhill, deadheading uphill, and deadheading downhill. [Precedence] When considering downhill instances, the snow may be so deep that it is impossible for a snowplow to deadhead a street before the street is plowed. In this dissertation we present a variety of heuristics to solve these problems, all adaptations of the concept of cycle permutation based on Euclidean cycle decomposition. To our knowledge, the use of moving or permuting sub-cycles as a way to change and improve a Eulerian cycle is novel and we show that it is very robust at improving solutions.Item Prioritizing Patients: Stochastic Dynamic Programming for Surgery Scheduling and Mass Casualty Incident Triage(2011) Herring, William L.; Herrmann, Jeffrey W; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The research presented in this dissertation contributes to the growing literature on applications of operations research models to problems in healthcare through the development and analysis of mathematical models for two fundamental problems facing nearly all hospitals: the single-day surgery scheduling problem and planning for triage in the event of a mass casualty incident. Both of these problems can be understood as sequential decision-making processes aimed at prioritizing between different classes of patients under significant uncertainty and are modeled using stochastic dynamic programming. Our study of the single-day surgery scheduling problem represents the first model to capture the sequential nature of the operating room (OR) manager's decisions during the transition between the generality of cyclical block schedules (which allocate OR time to surgical specialties) and the specificity of schedules for a particular day (which assign individual patients to specific ORs). A case study of the scheduling system at the University of Maryland Medical Center highlights the importance of the decision to release unused blocks of OR time and use them to schedule cases from the surgical request queue (RQ). Our results indicate that high quality block release and RQ decisions can be made using threshold-based policies that preserve a specific amount of OR time for late-arriving demand from the specialties on the block schedule. The development of mass casualty incident (MCI) response plans has become a priority for hospitals, and especially emergency departments and trauma centers, in recent years. Central to all MCI response plans is the triage process, which sorts casualties into different categories in order to facilitate the identification and prioritization of those who should receive immediate treatment. Our research relates MCI triage to the problem of scheduling impatient jobs in a clearing system and extends earlier research by incorporating the important trauma principle that patients' long-term (post-treatment) survival probabilities deteriorate the longer they wait for treatment. Our results indicate that the consideration of deteriorating survival probabilities during MCI triage decisions, in addition to previously studied patient characteristics and overall patient volume, increases the total number of expected survivors.