UMD Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/3
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 given thesis/dissertation in DRUM.
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
5 results
Search Results
Item AN INTEGER PROGRAMMING MODEL FOR DYNAMIC TAXI-SHARING CONSIDERING PROVIDER PROFIT(2018) Hao, Yeming; Haghani, Ali; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This thesis proposes an integer programming model for Dynamic Taxi-Sharing (DTS), which allows two groups of taxi users to ride on the same taxi together. The model matches taxi drivers and user pairs in certain sequences with the goal of maximizing taxi providers’ profit. We also develop a DTS fare calculation scheme which can automatically calculate the fare for each DTS user and self-adjust to balance the taxi occupancy rate in real time. A customized spectral clustering approach for preselection on DTS trips is also designed to narrow down the search space for the model. Real-world taxi trip data is used to demonstrate the DTS system is beneficial to providers, taxi users, and taxi drivers.Item Mathematical Programming Models for Influence Maximization on Social Networks(2016) Zhang, Rui; Raghavan, Subramanian; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation, we apply mathematical programming techniques (i.e., integer programming and polyhedral combinatorics) to develop exact approaches for influence maximization on social networks. We study four combinatorial optimization problems that deal with maximizing influence at minimum cost over a social network. To our knowl- edge, all previous work to date involving influence maximization problems has focused on heuristics and approximation. We start with the following viral marketing problem that has attracted a significant amount of interest from the computer science literature. Given a social network, find a target set of customers to seed with a product. Then, a cascade will be caused by these initial adopters and other people start to adopt this product due to the influence they re- ceive from earlier adopters. The idea is to find the minimum cost that results in the entire network adopting the product. We first study a problem called the Weighted Target Set Selection (WTSS) Prob- lem. In the WTSS problem, the diffusion can take place over as many time periods as needed and a free product is given out to the individuals in the target set. Restricting the number of time periods that the diffusion takes place over to be one, we obtain a problem called the Positive Influence Dominating Set (PIDS) problem. Next, incorporating partial incentives, we consider a problem called the Least Cost Influence Problem (LCIP). The fourth problem studied is the One Time Period Least Cost Influence Problem (1TPLCIP) which is identical to the LCIP except that we restrict the number of time periods that the diffusion takes place over to be one. We apply a common research paradigm to each of these four problems. First, we work on special graphs: trees and cycles. Based on the insights we obtain from special graphs, we develop efficient methods for general graphs. On trees, first, we propose a polynomial time algorithm. More importantly, we present a tight and compact extended formulation. We also project the extended formulation onto the space of the natural vari- ables that gives the polytope on trees. Next, building upon the result for trees---we derive the polytope on cycles for the WTSS problem; as well as a polynomial time algorithm on cycles. This leads to our contribution on general graphs. For the WTSS problem and the LCIP, using the observation that the influence propagation network must be a directed acyclic graph (DAG), the strong formulation for trees can be embedded into a formulation on general graphs. We use this to design and implement a branch-and-cut approach for the WTSS problem and the LCIP. In our computational study, we are able to obtain high quality solutions for random graph instances with up to 10,000 nodes and 20,000 edges (40,000 arcs) within a reasonable amount of time.Item Coordinated and robust aviation network resource allocation(2010) Churchill, Andrew Michael; Lovell, David J; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In the United States, flight operators may schedule flights to most airports at whatever time best achieves their objectives. However, during some time periods, both at airports and in the airspace, these freely-developed schedules may become infeasible because weather or other factors reduce capacity. A plan must then be implemented to mitigate this congestion safely, efficiently, and equitably. Current planning processes treat each congested resource independently, applying various rules to increase interoperation times sufficiently to match the reduced capacity. However, several resources are occasionally congested simultaneously, and ignoring possible dependencies may yield infeasible allocations for flights using multiple resources. In this dissertation, this problem of developing coordinated flight-slot allocations for multiple congested resources is considered from several perspectives. First, a linear optimization model is developed. It is demonstrated that optimally minimizing flight arrival delays induces an increasing bias against flights using multiple resources. However, the resulting allocations reduce overall arrival delay, as compared to the infeasible independent allocations, and to current operational practice. The analytic properties of the model are used to develop a rule-based heuristic for allocating capacity that achieves comparable aggregate results. Alternatively, minimizing delay assigned at all resources is considered, and this objective is shown to mimic the flights' original schedule order. Recognizing that minimizing arrival delays is attractive because of its tangible impact on system performance, variations to the original optimization model are proposed that constrain the worst-case performance of any individual user. Several different constraints and cost-based approaches are considered, all of which are successful to varying degrees in limiting inequities. Finally, the model is reformulated to consider uncertainty in capacity. This adds considerable complexity to the formulation, and introduces practical difficulties in identifying joint probability distributions for the capacity outcomes at each resource. However, this new model is successful in developing more robust flight-slot allocations that enable quick responses to capacity variations. Each of the optimization models and heuristics presented here are tested on a realistic case study. The problem studied and the approaches employed represent an important middle ground in air traffic flow management research between single resource models and comprehensive ones.Item COMPUTATIONALLY TRACTABLE STOCHASTIC INTEGER PROGRAMMING MODELS FOR AIR TRAFFIC FLOW MANAGEMENT(2010) Glover, Charles N.; Ball, Michael O; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)A primary objective of Air Traffic Flow Management (ATFM) is to ensure the orderly flow of aircraft through airspace, while minimizing the impact of delays and congestion on airspace users. A fundamental challenge of ATFM is the vulnerability of the airspace to changes in weather, which can lower the capacities of different regions of airspace. Considering this uncertainty along with the size of the airspace system, we arrive at a very complex problem. The development of efficient algorithms to solve ATFM problems is an important and active area of research. Responding to predictions of bad weather requires the solution of resource allocation problems that assign a combination of ground delay and route adjustments to many flights. Since there is much uncertainty associated with weather predictions, stochastic models are necessary. We address some of these problems using integer programming (IP). In general, IP models can be difficult to solve. However, if "strong" IP formulations can be found, then problems can be solved quickly by state of the art IP solvers. We start by describing a multi-period stochastic integer program for the single airport stochastic dynamic ground holding problem. We then show that the linear programming relaxation yields integer optimal solutions. This is a fairly unusual property for IP formulations that can significantly reduce the complexity of the corresponding problems. The proof is achieved by defining a new class of matrices with the Monge property and showing that the formulation presented belongs to this class. To further improve computation times, we develop alternative compact formulations. These formulations are extended to show that they can also be used to model different concepts of equity and fairness as well as efficiency. We explore simple rationing methods and other heuristics for these problems both to provide fast solution times, but also because these methods can embody inherent notions of fairness. The initial models address problems that seek to restrict flow into a single airport. These are extended to problems where stochastic weather affects en route traffic. Strong formulations and efficient solutions are obtained for these problems as well.Item Determining the Number of Slots to Submit to a Market Mechanism at a Single Airport(2007-05-09) Churchill, Andrew Michael; Lovell, David J; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this thesis, several stochastic optimization models are presented to determine the number of airport arrival slots that should be made available for distribution via a market mechanism. Considerable attention is paid to the structure and mathematical properties of each of these models, with regards to obtaining integer-valued solutions. Calibration of the various parameters is undertaken using historical data. In addition, an analysis of the average pecuniary valuations assigned to each slot is presented, as this is an essential input to these models. Several methods are suggested by which each of these values can be estimated. The models are intended to be taken in a general context, but extensive computational examples making use of data for LaGuardia Airport are provided as a case study in the application of the various techniques presented herein.