Mathematics Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2793
Browse
4 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 HYBRID ROUTING MODELS UTILIZING TRUCKS OR SHIPS TO LAUNCH DRONES(2018) Poikonen, Stefan Allan; Golden, Bruce L; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Technological advances for unmanned aerial vehicles, commonly referred to as drones, have opened the door to a number of new and interesting applications in areas including military, healthcare, communications, cinematography, emergency response, and logistics. However, limitations due to battery capacity, maximum take-off weight, finite range of wireless communications, and legal regulations have restricted the effective operational range of drones in many practical applications. Several hybrid operational models involving one or more drones launching from a larger vehicle, which may be a ship, truck, or airplane, have emerged to help mitigate these range limitations. In particular, the drones utilize the larger vehicle as both a mobile depot and a recharging or refueling platform. In this dissertation, we describe routing models that leverage the tandem of one or more drones with a larger vehicle. In these models, there is generally a set of targets that should be visited in an efficient (usually time-minimizing) manner. By using multiple vehicles, these targets may be visited in parallel thereby reducing the total time to visit all targets. The vehicle routing problem with drones (VRPD) and traveling salesman problem with a drone (TSP-D) consider hybrid truck-and-drone models of delivery, where the goal is to minimize the time required to deliver a set of packages to their respective customers and return the truck(s) and drone(s) to the origin depot. In both problems, the drone can carry one homogeneous package at a time. Theoretical analysis, exact solution methods, heuristic solution methods, and computational results are presented. In the mothership and drone routing problem (MDRP), we consider the case where the larger launch vehicle is free to move in Euclidean space (the open seas) and launch a drone to visit one target location at a time, before returning to the ship to pick up new cargo or refuel. The mothership and high capacity drone routing problem (MDRP-HC) is a generalization of the mothership and drone routing problem, which allows the drone to visit multiple targets consecutively before returning to the ship. MDRP and MDRP-HC contain elements of both combinatorial optimization and continuous optimization. In the multi-visit drone routing problem (MVDRP), a drone can visit multiple targets consecutively before returning to the truck, subject to energy constraints that take into account the weight of packages carried by the drone.Item Vehicle Routing Problems that Minimize the Completion Time: Heuristics, Worst-Case Analyses, and Computational Results(2016) Wang, Xingyin; Golden, Bruce; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In the standard Vehicle Routing Problem (VRP), we route a fleet of vehicles to deliver the demands of all customers such that the total distance traveled by the fleet is minimized. In this dissertation, we study variants of the VRP that minimize the completion time, i.e., we minimize the distance of the longest route. We call it the min-max objective function. In applications such as disaster relief efforts and military operations, the objective is often to finish the delivery or the task as soon as possible, not to plan routes with the minimum total distance. Even in commercial package delivery nowadays, companies are investing in new technologies to speed up delivery instead of focusing merely on the min-sum objective. In this dissertation, we compare the min-max and the standard (min-sum) objective functions in a worst-case analysis to show that the optimal solution with respect to one objective function can be very poor with respect to the other. The results motivate the design of algorithms specifically for the min-max objective. We study variants of min-max VRPs including one problem from the literature (the min-max Multi-Depot VRP) and two new problems (the min-max Split Delivery Multi-Depot VRP with Minimum Service Requirement and the min-max Close-Enough VRP). We develop heuristics to solve these three problems. We compare the results produced by our heuristics to the best-known solutions in the literature and find that our algorithms are effective. In the case where benchmark instances are not available, we generate instances whose near-optimal solutions can be estimated based on geometry. We formulate the Vehicle Routing Problem with Drones and carry out a theoretical analysis to show the maximum benefit from using drones in addition to trucks to reduce delivery time. The speed-up ratio depends on the number of drones loaded onto one truck and the speed of the drone relative to the speed of the truck.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.