Mathematics

Permanent URI for this communityhttp://hdl.handle.net/1903/2261

Browse

End date: 2009Subject: search.filters.subject.Operations Research

Search Results

Now showing 1 - 10 of 12
  • Thumbnail Image
    Item
    Applications of Operations Research Models to Problems in Health Care
    (2009) Price, Carter Claiborne; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This dissertation is divided into two parts. In the first portion, we study inflection points in biobjective variants of the traveling salesman problem (TSP) related to health care applications. In the second portion, we use a variety of techniques from operations research to improve hospital efficiency. We used a TSP variant that prioritizes the ability to return to the depot, in addition to the standard distance, to study the collection of blood from remote collection sites. In an application related to emergency response, we looked into behavior of tours generated using the target visitation problem, a TSP variant that also includes node priority in the objective function. Working with the University of Maryland Medical Center, we did three projects related to hospital efficiency. We used stochastic modeling and simulation to optimize the throughput of a cardiac surgery post-operative unit. We found that altering the mix of post-operative beds could significant increase the effective capacity. After unsuccessfully attempting to use data mining and survival analysis to predict hospital census, we performed a statistical analysis of patient length of stay patterns and discovered surgeons were improving their chances of having available beds for incoming cases by adjusting their discharge practices by day of week. In the final project, we used integer programming and heuristics to develop schedules that match incoming surgical patients with the discharge of earlier patients. The results indicate that altering the surgical schedule can substantially improve the flow of patients through the hospital.
  • Thumbnail Image
    Item
    THE VEHICLE ROUTING PROBLEM WITH DEMAND RANGES
    (2009) Cornick, Namrata Uppal; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The classic Capacitated Vehicle Routing Problem (CVRP) has been studied in the Operations Research field for over 5 decades. This thesis formulates the vehicle routing problem with a variation that has not been studied in detail. It is called the Vehicle Routing Problem with Demand Ranges (VRPDR). With increasing competition, corporations are looking to minimize costs. This problem aims to reduce the cost of distributing goods by allowing flexibility in the delivered or dropped off quantity. This benefits the customer as well, by reducing storage and other inventory costs. We solve the VRPDR problem where the customer gives the distributor a demand range. The distributor is rewarded for delivering more. A metaheuristic, record-to-record travel with demand range (RTRDR), is developed which is capable of solving large problem instances. The metaheuristic is a modification of a successful CVRP metaheuristic used in the past. In this thesis, we report results on problems ranging in size from 560 to 1200 customers. The developed metaheuristic uses the Clarke-Wright procedure to get initial solutions and then applies record-to-record travel in conjunction with two-opt moves, one point moves, and two point moves. Since the problem has not been studied yet from a computational point of view, we have developed a comparison algorithm, which takes advantage of the demand range flexibility of this problem only after the algorithm has optimized for distance alone. We use the results from this algorithm as a benchmark to compare with our proposed metaheuristic RTRDR.
  • Thumbnail Image
    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.
  • Thumbnail Image
    Item
    Applications of Genetic Algorithms, Dynamic Programming, and Linear Programming to Combinatorial Optimization Problems
    (2008-10-16) Wang, Xia; Golden, Bruce L.; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Combinatorial optimization problems are important in operations research and computer science. They include specific, well-known problems such as the bin packing problem, sequencing and scheduling problems, and location and network design problems. Each of these problems has a wide variety of real-world applications. In addition, most of these problems are inherently difficult to solve, as they are NP-hard. No polynomial-time algorithm currently exists for solving them to optimality. Therefore, we are interested in developing high-quality heuristics that find near-optimal solutions in a reasonable amount of computing time. In this dissertation, we focus on applications of genetic algorithms, dynamic programming, and linear programming to combinatorial optimization problems. We apply a genetic algorithm to solve the generalized orienteering problem. We use a combination of genetic algorithms and linear program to solve the concave cost supply scheduling problem, the controlled tabular adjustment problem, and the two-stage transportation problem. Our heuristics are simple in structure and produce high-quality solutions in a reasonable amount of computing time. Finally, we apply a dynamic programming-based heuristic to solve the shortest pickup planning tour problem with time windows.
  • Thumbnail Image
    Item
    Global Optimization of Finite Mixture Models
    (2007-05-31) Heath, Jeffrey Wells; Fu, Michael; Jank, Wolfgang; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The Expectation-Maximization (EM) algorithm is a popular and convenient tool for the estimation of Gaussian mixture models and its natural extension, model-based clustering. However, while the algorithm is convenient to implement and numerically very stable, it only produces solutions that are locally optimal. Thus, EM may not achieve the globally optimal solution in Gaussian mixture analysis problems, which can have a large number of local optima. This dissertation introduces several new algorithms designed to produce globally optimal solutions for Gaussian mixture models. The building blocks for these algorithms are methods from the operations research literature, namely the Cross-Entropy (CE) method and Model Reference Adaptive Search (MRAS). The new algorithms we propose must efficiently simulate positive definite covariance matrices of the Gaussian mixture components. We propose several new solutions to this problem. One solution is to blend the updating procedure of CE and MRAS with the principles of Expectation-Maximization updating for the covariance matrices, leading to two new algorithms, CE-EM and MRAS-EM. We also propose two additional algorithms, CE-CD and MRAS-CD, which rely on the Cholesky decomposition to construct the random covariance matrices. Numerical experiments illustrate the effectiveness of the proposed algorithms in finding global optima where the classical EM fails to do so. We find that although a single run of the new algorithms may be slower than EM, they have the potential of producing significantly better global solutions to the model-based clustering problem. We also show that the global optimum matters in the sense that it significantly improves the clustering task. Furthermore, we provide a a theoretical proof of global convergence to the optimal solution of the likelihood function of Gaussian mixtures for one of the algorithms, namely MRAS-CD. This offers support that the algorithm is not merely an ad-hoc heuristic, but is systematically designed to produce global solutions to Gaussian mixture models. Finally, we investigate the fitness landscape of Gaussian mixture models and give evidence for why this is a difficult global optimization problem. We discuss different metrics that can be used to evaluate the difficulty of global optimization problems, and then apply them to the context of Gaussian mixture models.
  • Thumbnail Image
    Item
    Simulation Optimization of Traffic Light Signal Timings via Perturbation Analysis
    (2006-07-12) Howell, William Casey; Fu, Michael C; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    We develop simulation optimization algorithms for determining the traffic light signal timings for an isolated intersection and a network of two-signalized intersections modeled as single-server queues. Both problem settings consider traffic flowing in one direction. The system performance is estimated via stochastic discrete-event simulation. In the first problem setting, we examine an isolated intersection. We use smoothed perturbation analysis to derive both left-hand and right-hand gradient estimators of the queue lengths with respect to the green/red light lengths within a signal cycle. Using these estimators, we are able to apply stochastic approximation, which is a gradient-based search algorithm. Next we extend the problem to the case of a two-light intersection, where there are two additional parameters that we must estimate the gradient with respect to: the green/red light lengths within a signal cycle at the second light and the offset between the two light signals. Also, the number of queues increases from two to five. We again derive both left-hand and right-hand gradient estimators of the all queue lengths with respect to the three aforementioned parameters. As before, we are able to apply gradient-based search based on stochastic approximation using these estimators. Next we reexamine the two aforementioned problem settings. However, this time we are solely concerned with optimization; thus, we model the intersections using three different stochastic fluid models, each incorporating different degrees of detail. From these new models, we derive infinitesimal perturbation analysis gradient estimators. We then implement these estimators on the underlying discrete-event simulation and are able to apply gradient-based search based on stochastic approximation using these estimators. We perform numerical experiments to test the performance of the three gradient estimators and also compare these results with finite-difference estimators. Optimization for both the one-light and two-light settings is carried out using the gradient estimation approaches.
  • Thumbnail Image
    Item
    Modeling and Solving Variants of the Vehicle Routing Problem: Algorithms, Test Problems, and Computational Results
    (2005-08-30) Li, Feiyue; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    In the standard version of the capacitated vehicle routing problem (VRP), a sequence of deliveries is generated for each vehicle in a homogeneous fleet based at a single depot so that all customers are serviced and the total distance traveled by the fleet is minimized. Each vehicle has a fixed capacity and must leave from and return to the depot. Each vehicle might have a route-length restriction that limits the maximum distance it can travel. Each customer has a known demand and is serviced by exactly one visit of a single vehicle. For more than 45 years, the standard VRP has attracted an enormous amount of attention in the operations research literature. There are many practical applications of vehicle routing in the distribution of products such as soft drinks, newspapers, groceries, and milk and in street sweeping, solid waste collection,and mail delivery. In this dissertation, we model and solve variants of the standard VRP. First, we focus on very large VRPs. We develop new, benchmark instances via a problem generator with as many as 1,200 customers along with estimated solutions. We also develop a simple, flexible, fast, and powerful heuristic solution procedure based on the record-to-record travel algorithm and apply our heuristic to the new problems and generate high-quality solutions very quickly. Next, we turn our focus to five interesting variants of the VRP that have received little attention in the literature but have practical application in the real world: (1) the time dependent traveling salesman problem (TDTSP), (2) the noisy traveling salesman problem (NTSP), (3) the heterogeneous vehicle routing problem (HVRP), (4) the open vehicle routing problem (OVRP), and (5) the landfill routing problem (LRP). For each variant, we develop an effective solution procedure and report computational results. In particular,we solve the TDTSP, HVRP, OVRP, and LRP with our record-to-record travel-based heuristic and generate high-quality results. For the NTSP, we develop a new procedure based on quad trees that outperforms existing solution methods. Finally, for the HVRP and the OVRP, we generate new test problems and solve each new problem using our record-to-record travel-based heuristic.
  • Thumbnail Image
    Item
    Ranking U.S. Army Generals of the Twentieth Century Using the Group Analytic Hierarchy Process
    (2005-07-26) Retchless, Todd; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The group analytic hierarchy process (GAHP) is a mathematically based decision making tool that allows groups of individuals to participate in the decision making process. In this thesis, we use the GAHP and the expert opinions of 10 professional and amateur military historians to rank seven U.S. Army generals of the 20th Century. We use two methods to determine the priority vectors: the traditional eigenvector method and the recently introduced interval linear programming method. We consider the effects of removing outlier data and compare the rankings obtained by each method.
  • Thumbnail Image
    Item
    MODELING AND OPTIMIZATION OF TRANSMISSION NETWORKS
    (2005-04-19) Frommer, Ian; Hunt, Brian; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This dissertation focuses on transmission networks. These networks play an important role in communication (including data and voice), energy transmission (such as gas, electrical, and oil), and micro-electronics among other areas. In this dissertation, we consider two different problems associated with transmission networks: the dynamics on a data communication network and the optimal design of a general transmission network located on a non-uniform landscape. The first two parts of this dissertation develop and apply mathematical models of congested Internet connections and describe possible extensions to network traffic state estimation and network security. The third part looks at an optimal network design problem through a variation on the Euclidean Steiner tree problem, a well-known network optimization problem.
  • Thumbnail Image
    Item
    Two Applications Involving the Analytic Hierarchy Process
    (2004-12-06) Alford, Brian David; Golden, Bruce L; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The analytic hierarchy process (AHP) is a popular tool used in decision making for ranking alternatives based on quantitative and qualitative criteria. In this thesis, we investigate two applications involving the AHP: determining the greatest sports records and generating priority vectors for inconsistent interval judgments. We determine rankings of the greatest active single-season, career, and single-event sports records by applying the ratings mode of the AHP. In addition, we present an extension to a linear programming method used for generating priority vectors for interval pairwise comparison matrices. By introducing multiplicative stretch factors for each interval comparison, our linear programming method with stretching can be used to solve problems when inconsistent interval judgments are present. We describe the linear programming method, apply it to three problems, and compare its performance to other methods for solving inconsistent interval AHP problems.