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
9 results
Search Results
Item Exact and Heuristic Methods for Emerging Vehicle Routing Problems(2022) Oden, Eric John; Golden, Bruce; Raghavan, S.; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The rise of global supply chains and e-commerce in recent decades have intensified the relevance of the transportation industry to both the individual and the economy. With rising consumer expectations and slim profit margins, the various sectors within the transportation industry rely on the development of carefully designed routes to remain competitive. Despite the wealth of research on route design, and the responsiveness of the research community to practical considerations, there remain gaps between the work done in practice and that appearing in the literature. Correspondingly, the work in this dissertation is directly in response to conversations had with contacts from real-world companies within the transportation domain. We consider problems presented, verbally, by companies representing three distinct segments of the industry: freight routing, last-mile delivery, and on-demand passenger transport. Each problem is centered around an innovative strategy with the potential to dramatically disrupt its corresponding domain. First, we consider the Shared Truckload (STL) freight shipping model, an alternative to the dominant Less-than-Truckload (LTL) model. Both models pool shipments from multiple customers into a single trailer, but, in the latter, consolidation is facilitated by a hub-and-spoke routing network, whereas, in the the former, freight moves directly from origin to destination. This strategy minimizes travel times and the risk of damage. We then investigate a novel strategy to facilitate last-mile, last-minute delivery, through coordinating a fleet of trucks and a fleet of smaller vehicles, referred to as shuttles. In order to accommodate requests which come in after trucks have been dispatched, shuttles are allowed to pick up packages from a depot and intercept trucks along their routes. This strategy can enable a shipper to make highly competitive service guarantees. Finally, we consider the emerging field of Urban Air Mobility (UAM), a vision of air taxis conveying passengers at lower altitudes throughout urban areas as an efficient alternative to gridlock traffic. In particular, we consider a UAM service company in the early stages of its development, where the chief goal is to maximize market share. These innovations represent significant deviations from the status quo in their respective fields, and, thus, the existing research for each is slim, if existent. Therefore, we introduce precise mathematical formulations of each of the problems to the research community. We then develop both exact and heuristic approaches to solve the problems, and carry out extensive computational studies comparing the solution methodologies. Furthermore, for each of the problems, we offer a sensitivity analysis and managerial insights. Among our contributions are original algorithms based on solving a set-partitioning formulations via column generation, a highly successful paradigm for solving large linear programs. Among the advantages of this approach is the ability to include highly general route costs and constraints. We illustrate this expressiveness by demonstrating its application to each of the three highly distinct problems we consider.Item Mathematical Programming and Heuristic Approaches for Three Novel Vehicle Routing Problems(2022) Luo, Yuchen; Golden, Bruce; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Vehicle routing problems (VRPs) arise in key real-world domains including mail delivery, police patrol, and snow plowing. Due to the inherent complexity of the VRP, no algorithm currently exists that can solve the VRP exactly in polynomial time. In the meantime, high quality solutions are needed to tackle challenging issues such as rising mail and package delivery costs and surging crime rates. In this dissertation, we design efficient routing solutions for three applications of the VRP. First, we consider the application of the hot spot police patrol, where hot spots refer to locations with high crime rates. We examine the routing problem for a patrol car that visits locations in a region and remains close to the center of the region modeling a high-crime neighborhood (HCN). We formulate this problem as the traveling salesman problem with a center (TSPC), in which we minimize an energy function including L (the length of a tour) and C (the distance from a tour to the center, defined by some metric). To address the TSPC, we propose a metric to measure C rather accurately and also introduce the idea of a triangular path, in which the patrol car no longer travels in a straight line between two nodes. We show that under identical circumstances, the tour with triangular paths remains closer to the center than a tour using all direct edges in both a Euclidean graph and a grid network. Second, we extend the hot spot police patrol to a fleet of patrol cars. Given the disorder and chaos in the HCN, we require at least one patrol car in the HCN at any given time during the patrol. We call this routing problem the hot spot coverage patrol problem (HSCPP). In the HSCPP, the importance of a patrol location is quantified by a prize and our objective is to maximize the sum of prizes collected by the patrol cars while obeying all operations requirements. We propose mathematical formulations and develop several solution approaches for the HSCPP. These solution approaches are based on integer programming and column generation. We then conduct a detailed computational study to compare these approaches using real crime data from Montgomery County, Maryland. We point out the best solution approaches in terms of optimality gap, runtime, and workload balancing. Third, we consider mail deliveries. To reduce the fleet size and carbon emissions of a postal service, we allow two mail carriers per truck. We call this problem the paired mail carrier problem (PMCP). Our objective is to minimize the route completion time while ensuring that each service stop is fully serviced and obeys all feasibility constraints. We develop a mixed integer programming formulation and two fast heuristics for the PMCP. We evaluate the impact of the paired mail carriers (PMC) setting on both a one-truck situation and a fleet (multiple trucks) situation, relative to the single mail carrier (SMC) setting. Overall, the PMC setting can not only accomplish over 50% more work within the same shift hours but can also lead to a 22% cost savings.Item Algorithms for Online Advertising Portfolio Optimization and Capacitated Mobile Facility Location(2017) Sahin, Mustafa; 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 large-scale optimization techniques including column generation and heuristic approaches to problems in the domains of online advertising and mobile facility location. First, we study the online advertising portfolio optimization problem (OAPOP) of an advertiser. In the OAPOP, the advertiser has a set of targeting items of interest (in the order of tens of millions for large enterprises) and a daily budget. The objective is to determine how much to bid on each targeting item to maximize the return on investment. We show the OAPOP can be represented by the Multiple Choice Knapsack Problem (MCKP). We propose an efficient column generation (CG) algorithm for the linear programming relaxation of the problem. The computations demonstrate that our CG algorithm significantly outperforms the state-of-the-art linear time algorithm used to solve the MCKP relaxation for the OAPOP. Second, we study the problem faced by the advertiser in online advertising in the presence of bid adjustments. In addition to bids, the advertisers are able to submit bid adjustments for ad query features such as geographical location, time of day, device, and audience. We introduce the Bid Adjustments Problem in Online Advertising (BAPOA) where an advertiser determines base bids and bid adjustments to maximize the return on investment. We develop an efficient algorithm to solve the BAPOA. We perform computational experiments and demonstrate, in the presence of high revenue-per-click variation across features, the revenue benefit of using bid adjustments can exceed 20%. Third, we study the capacitated mobile facility location problem (CMFLP), which is a generalization of the well-known capacitated facility location problem that has applications in supply chain and humanitarian logistics. We provide two integer programming formulations for the CMFLP. The first is on a layered graph, while the second is a set partitioning formulation. We develop a branch-and-price algorithm on the set partitioning formulation. We find that the branch-and-price procedure is particularly effective, when the ratio of the number of clients to the number of facilities is small and the facility capacities are tight. We also develop a local search heuristic and a rounding heuristic for the CMFLP.Item Multi-level, Multi-stage and Stochastic Optimization Models for Energy Conservation in Buildings for Federal, State and Local Agencies(2016) Champion, Billy Ray; Gabriel, Steven A; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Energy Conservation Measure (ECM) project selection is made difficult given real-world constraints, limited resources to implement savings retrofits, various suppliers in the market and project financing alternatives. Many of these energy efficient retrofit projects should be viewed as a series of investments with annual returns for these traditionally risk-averse agencies. Given a list of ECMs available, federal, state and local agencies must determine how to implement projects at lowest costs. The most common methods of implementation planning are suboptimal relative to cost. Federal, state and local agencies can obtain greater returns on their energy conservation investment over traditional methods, regardless of the implementing organization. This dissertation outlines several approaches to improve the traditional energy conservations models. Any public buildings in regions with similar energy conservation goals in the United States or internationally can also benefit greatly from this research. Additionally, many private owners of buildings are under mandates to conserve energy e.g., Local Law 85 of the New York City Energy Conservation Code requires any building, public or private, to meet the most current energy code for any alteration or renovation. Thus, both public and private stakeholders can benefit from this research. The research in this dissertation advances and presents models that decision-makers can use to optimize the selection of ECM projects with respect to the total cost of implementation. A practical application of a two-level mathematical program with equilibrium constraints (MPEC) improves the current best practice for agencies concerned with making the most cost-effective selection leveraging energy services companies or utilities. The two-level model maximizes savings to the agency and profit to the energy services companies (Chapter 2). An additional model presented leverages a single congressional appropriation to implement ECM projects (Chapter 3). Returns from implemented ECM projects are used to fund additional ECM projects. In these cases, fluctuations in energy costs and uncertainty in the estimated savings severely influence ECM project selection and the amount of the appropriation requested. A risk aversion method proposed imposes a minimum on the number of “of projects completed in each stage. A comparative method using Conditional Value at Risk is analyzed. Time consistency was addressed in this chapter. This work demonstrates how a risk-based, stochastic, multi-stage model with binary decision variables at each stage provides a much more accurate estimate for planning than the agency’s traditional approach and deterministic models. Finally, in Chapter 4, a rolling-horizon model allows for subadditivity and superadditivity of the energy savings to simulate interactive effects between ECM projects. The approach makes use of inequalities (McCormick, 1976) to re-express constraints that involve the product of binary variables with an exact linearization (related to the convex hull of those constraints). This model additionally shows the benefits of learning between stages while remaining consistent with the single congressional appropriations framework.Item Optimization Models for Speed Control in Air Traffic Management(2015) Jones, James Calvin; Lovell, David J; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In a typical air traffic control environment, the precise landing times of en route aircraft are not set until each aircraft approaches the airspace adjacent to the destination airport. In times of congestion, it is not unusual for air traffic controllers to subject arriving aircraft to various maneuvers to create an orderly flow of flights onto an arrival runway. Typical maneuvers include flying in zig-zag patterns, flying in race track shaped patterns and tromboning. These maneuvers serve to delay the arrival time of the flight while also burning additional fuel. On the other hand, if the arrival time was established much earlier, then such delay could be realized by simply having flights fly slower while still at a higher altitude, which would incur much less fuel burn than the described maneuvers. Yet despite its potential benefit, thus far little has been done to promote the management of flights using speed control in the presence of uncertainty. This dissertation presents a set of models and prescriptions designed to use the mechanism of speed control to enhance the level of coordination used by FAA managers at the tactical and pre-tactical level to better account for the underlying uncertainty at the time of planning. Its models deal with the challenge of assigning delay to aircraft approaching a single airport, well in advance of each aircraft’s entry into the terminal airspace. In the first approach, we assume control of all airborne flights at a distance of 500 nm while assuming no control over flights originating less than 500 nm from the airport. We propose a set of integer programming models designed to issue arrival times for controlled flights in the presence of the uncertainty associated with the unmanaged flights. In the second approach, we assume control over all flights by subjecting flights to a combination of air and ground delay. Both approaches show strong potential to transfer delay from the terminal to the en route phase of flight and achieve fuel savings. Building on these ideas we then formulate an approach to incorporate speed control into Ground Delay Programs. We propose enhancements for equitably rationing airport access to carriers and develop a revised framework to allow carriers to engage in Collaborative Decision Making. We present new GDP control procedures and also new flight operator GDP planning models. While the ability to achieve all the benefits we describe will require NextGen capabilities, substantial performance improvements could be obtained even with a near-term implementation.Item Problems and Models in Strategic Air Traffic Flow Management(2013) Swaroop, Prem; Ball, Michael O; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The thesis comprises of three essays. The first essay is titled "Do more US airports need slot controls? A welfare based approach to determine slot levels." It analyzes the welfare effects of slot controls on major US airports. We consider the fundamental trade-off between benefits from queuing delay reduction and costs due to simultaneous schedule delay increase to passengers while imposing slot limits at airports. A set of quantitative models and simulation procedures are developed to explore the possible airline scheduling responses through reallocating and trimming flights. We find that, of the 35 major US airports, a more widespread use of slot controls would improve travelers' welfare. The results from our analyses suggest that slot caps at the four airports that currently have slot controls (Washington Reagan, Newark, New York LaGuardia, New York John F. Kennedy) are set too high. Further slot reduction by removing some of the flights at these airports could generate additional benefits to passengers. Slot controls can potentially reduce two thirds of the total system delays caused by congestion. A number of implementation and design issues related to the use of slot controls are also discussed in the paper. The second essay is titled "Designing the Noah's Ark: A Multi-objective Multi-stakeholder Consensus Building Method." A significant challenge of effective air traffic flow management (ATFM) is to allow for various competing airlines to collaborate with an air navigation service provider (ANSP) in determining flow management initiatives. This challenge has led over the past 15 years to the development of a broad approach to ATFM known as collaborative decision making (CDM). A set of CDM principles has evolved to guide the development of specific tools that support ATFM resource allocation. However, these principles have not been extended to cover the problem of providing strategic advice to an ANSP in the initial planning stages of traffic management initiatives. In the second essay, we describe a mechanism whereby competing airlines provide ``consensus'' advice to an ANSP using a voting mechanism. It is based on the recently developed Majority Judgment voting procedure. The result of the procedure is a consensus real-valued vector that must satisfy a set of constraints imposed by the weather and traffic conditions of the day in question. While we developed and modeled this problem based on specific ATFM features, it appears to be highly generic and amenable to a much broader set of applications. Our analysis of this problem involves several interesting sub-problems, including a type of column generation process that creates candidate vectors for input to the voting process. The third essay is titled "Strategic Opportunity Analysis in COuNSEL -- A Consensus-Building Mechanism for Setting Service Level Expectations." The consensus-building mechanism described in the second essay has been accepted as a technically viable solution for the stated problem -- although many practical challenges still remain before it may be deployed in operations. A key issue worthy of further investigation is its strong strategy-resistance -- as claimed by the authors of Majority Judgment, the voting procedure embedded in COuNSEL. Using the broad ideas of Nash Equilibria, we characterize the necessary and sufficient conditions for an airline to benefit from unilaterally deviating from truthfully grading one or more candidates. The framework provides the airline with all the other airlines' grades on a set of candidates, and allows it an opportunity to present new grades. The analysis is repeated over multiple instances, and likelihood of beneficial strategic opportunity is presented.Item Methods for Employing Real Options Models to Mitigate Risk in R&D Funding Decisions(2011) Eckhause, Jeremy Michael; Gabriel, Steven A; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Government acquisitions requiring research and development (R&D) efforts are fraught with uncertainty. The risks are often mitigated by employing a multi-stage competition, with multiple projects funded initially until a single successful project is selected. While decision-makers recognize they are using a real options approach, analytical tools are often unavailable to evaluate optimal decisions. The use of these techniques for R&D project selection to reduce the uncertainties has been shown to increase overall project value. This dissertation first presents an efficient stochastic dynamic programming (SDP) approach that managers can use to determine optimal project selection strategies and apply the proposed approach on illustrative numerical examples. While the SDP approach produces optimal solutions for many applications, this approach does not easily accommodate the inclusion of a budget-optimal allocation or side constraints, since its formulation is scenario specific. Thus, we then formulate an integer program (IP), whose solution set is equivalent to the SDP model, but facilitates the incorporation of these features and can be solved using available commercial IP solvers. The one-level IP formulation can solve what is otherwise a nested two-level problem when solved as an SDP. We then compare the performance of both models on differently sized problems. For larger problems, where the IP approach appears to be untenable, we provide heuristics for the two-level SDP formulation to solve problems efficiently. Finally, we apply these methods to carbon capture and storage (CCS) projects in the European Union currently under development that may be subject to public funding. Taking the perspective of a funding agency, we employ the real options models presented in this dissertation for determining optimal funding strategies for CCS project selection. The models demonstrate the improved risk reduction by employing a multi-stage competition and explicitly consider the benefits of knowledge spillover generated by competing projects. We then extend the model to consider two sensitivities: 1) the flexibility to spend the budget among the time periods and 2) optimizing the budget, but specifying each time period's allocation a priori. State size, scenario reduction heuristics and run-times of the models are provided.Item Integer Programming-Based Heuristics for Vehicle Routing Problems(2010) Gulczynski, Damon John; 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) has been an active field of study by operations researchers for over 50 years. Many practical applications have been presented in the literature, and many solution techniques have been developed. We discuss, develop, and computationally test integer programming-based heuristics for several variants of the standard VRP. We use integer programming to model the split delivery VRP with minimum delivery amounts, the multi-depot split delivery VRP, the period VRP, the standard VRP, and the multi-depot VRP. We apply our heuristics to benchmark problems from the literature and generate many new problems with high-quality, visually-estimated solutions. Our heuristics produce high-quality solutions in a reasonable amount of computer time. Overall, our new IP-based heuristics are very competitive with the best methods found in the VRP literature to date.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.