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
8 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 INTRODUCING MEETING LOCATIONS IN TAXI-SHARING SYSTEMS(2021) Aliari, Sanaz; Haghani, Ali A.H.; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Taxi-sharing is admittedly a promising solution to reduce travel costs and mitigate congestion. However, sharing a ride with other passengers may impose long detours. Taxi-sharing can be more beneficial if the vehicle miles traveled for the detours can be reduced when serving additional passengers. In this study, we propose incorporating alternative meeting points in taxi-sharing routing to further boost efficiency by eliminating unnecessary detours and improving the chances of passengers being matched. Unlike traditional taxi-sharing systems, passengers are not necessarily picked up at their original location in the proposed system. Instead, they are serviced within a walkable distance of their origin (meeting points). This can be especially beneficial in heavily congested road networks in dense urban areas.There are several challenges in the real-world implementation of a ride-sharing system with alternative pick-up points in a dense high-demand network. The first challenge is to find appropriate passenger matches that may share a ride. The second challenge is to effectively find a set of specific locations as the potential alternative pick-up points that are likely to reduce total travel times. Once possible matches and the corresponding set of candidate pickup points are selected, the last challenge is to obtain optimal/near-optimal routes to satisfy the passengers’ demand with a reasonable computational time. In this study, we formulate a mixed integer programming model for the ride-sharing problem with alternative pick-up points and introduce strategies to cope with these challenges in a real-world setting. We use the New York City taxi demand data that may sometimes have hundreds of demands per minute in a relatively small geographical area. We first introduce a decomposition procedure to break down such a large-scale problem into smaller subproblems by pre-matching groups of passengers that are more likely to share a ride. We then create an initial set of candidate locations for all pick-up points in each group. Then, different strategies are proposed to reduce the set of candidate locations into smaller subsets, including alternative locations with higher potentials of constructing better routes. The experimental results show that incorporating alternative pick-up points results in significant savings in total travel times, total wait times, and the number of vehicles used compared to a baseline ride-sharing system that picks up each passenger exactly from their requested location. Finally, given the high computational cost of the optimization problem, we propose a genetic algorithm to find near-optimal solutions for the formulated problem, and we show that the proposed algorithm achieves solutions that are very close to the optimal solutions, with significantly lower computational times. We design specific operations to implement basic components of the genetic algorithm in the context of our algorithm. This includes strategies to diversify and create random sets of feasible solutions (individuals), select the fittest individuals in each generation, and create new generations through mutations and ordered cross-over such that the new individuals can inherit from their parents while still representing a feasible solution.Item DATA-DRIVEN OPTIMIZATION AND STATISTICAL MODELING TO IMPROVE DECISION MAKING IN LOGISTICS(2019) Sinha Roy, Debdatta; Golden, Bruce; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation, we develop data-driven optimization and statistical modeling techniques to produce practically applicable and implementable solutions to real-world logistics problems. First, we address a significant and practical problem encountered by utility companies. These companies collect usage data from meters on a regular basis. Each meter has a signal transmitter that is automatically read by a receiver within a specified distance using radio-frequency identification (RFID) technology. The RFID signals are discontinuous, and each meter differs with respect to the specified distance. These factors could lead to missed reads. We use data analytics, optimization, and Bayesian statistics to address the uncertainty. Second, we focus on an important problem experienced by delivery and service companies. These companies send out vehicles to deliver customer products and provide services. For the capacitated vehicle routing problem, we show that reducing route-length variability while generating the routes is an important consideration to minimize the total operating and delivery costs for a company when met with random traffic. Third, we address a real-time decision-making problem experienced in practice. In one application, routing companies participating in competitive bidding might need to respond to a large number of requests regarding route costs in a very short amount of time. In another application, during post-disaster aerial surveillance planning or using drones to deliver emergency medical supplies, route-length estimation would quickly need to assess whether the duration to cover a region of interest would exceed the drone battery life. For the close enough traveling salesman problem, we estimate the route length using information about the instances. Fourth, we address a practical problem encountered by local governments. These organizations carry out road inspections to decide which street segments to repair by recording videos using a camera mounted on a vehicle. The vehicle taking the videos needs to proceed straight or take a left turn to cover an intersection fully. Right turns and U-turns do not capture an intersection fully. We introduce the intersection inspection rural postman problem, a new variant of the rural postman problem involving turns. We develop two integer programming formulations and three heuristics to generate least-cost vehicle routes.Item Efficient People Movement through Optimal Facility Configuration and Operation(2013) Feng, Lei; Miller-Hooks, Elise; Civil Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)There are a variety of circumstances in which large numbers of people gather and must disperse. These include, for example, carnivals, parades, and other situations involving entrance to or exit from complex buildings, sport stadiums, commercial malls, and other type of facilities. Under these situations, people move on foot, commonly, in groups. Other circumstances related to large crowds involve high volumes of people waiting at transportation stations, airports, and other types of high traffic generation points. In these cases, a myriad of people need to be transported by bus, train, or other vehicles. The phenomenon of moving in groups also arises in these vehicular traffic scenarios. For example, groups may travel together by carpooling or ridesharing as a cost-saving measure. The movement of significant numbers of people by automobile also occurs in emergency situations, such as transporting large numbers of carless and mobility-impaired persons from the impacted area to shelters during evacuation of an urban area. This dissertation addresses four optimization problems on the design of facilities and/or operations to support efficient movement of large numbers of people who travel in groups. A variety of modeling approaches, including bi-level and nonlinear programming are applied to formulate the identified problems. These formulations capture the complexity and diverse characteristics that arise from, for example, grouping behavior, interactions in decisions by the system and its users, inconvenience constraints for passengers, and interdependence of strategic and operational decisions. These models aim to provide: (1) estimates of how individuals and groups distribute themselves over the network in crowd situations; (2) an optimal configuration of the physical layout to support large crowd movement; (3) an efficient fleet resource management tool for ridesharing services; and (4) tools for effective regional disaster planning. A variety of solution algorithms, including a meta-heuristic scheme seeking a pure-strategy Nash equilibrium, a multi-start tabu search with sequential quadratic programming procedure, and constraint programming based column generation are developed to solve the formulated problems. All developed models and solution methodologies were employed on real-world or carefully created fictitious examples to demonstrate their effectiveness.Item Solving the Inventory Slack Routing Problem for Emergency Medication Distribution(2010) Montjoy, Adam Wesley; Herrmann, Jeffrey W; Mechanical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)A bioterrorist attack, or natural disaster, would prompt an immediate government response in order to efficiently address the possible health effects of the population. Such a scenario would create a logistics problem of delivering medication (or other supplies) to makeshift dispensing centers in a short period of time and in high quantities while operating. These makeshift centers, or Points of Dispensing, require schedules of delivery that are robust against uncertainty. This inventory slack routing problem is a novel vehicle routing problem. The objective function is to maximize the slack in the schedule. This thesis presents heuristic approaches that separate the problem into routing and scheduling. The routing problem is solved using a route first-cluster second method. The scheduling problem is solved using a heuristic and an improvement approach. This thesis also presents a search approach that uses heuristics to search various neighborhoods in the solution space. These heuristics are chosen randomly based on probabilities that adapt during the search according to their performance. The inventory slack routing problem is also formulated as a mixed-integer program and solved using a column generation procedure that utilizes simulated annealing to generate new vehicle schedules. This thesis presents the results of testing these three approaches on a set of 432 instances that were generated from real-world data to evaluate solution quality and computational effort. The search approach outperformed the heuristic approach with a reasonable amount of computational effort. The column generation approach did not generate desirable vehicle schedules and therefore was not productive in solving the problem.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.