Mathematics Theses and Dissertations

Permanent URI for this collectionhttp://hdl.handle.net/1903/2793

Browse

Subject: search.filters.subject.Heuristics

Search Results

Now showing 1 - 5 of 5
  • Thumbnail Image
    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.
  • Thumbnail Image
    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.
  • Thumbnail Image
    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.
  • Thumbnail Image
    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.
  • 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.