An official website of the United States government
We consider a variant of the vehicle routing problem (VRP) where each customer has a unit demand and the goal is to minimize the total cost of routing a fleet of capacitated vehicles from one or multiple depots to visit all customers. We propose two parallel algorithms to efficiently solve the column-generation-based linear-programming relaxation for this VRP. Specifically, we focus on algorithms for the “pricing problem,” which corresponds to the resource-constrained elementary shortest path problem. The first algorithm extends the pulse algorithm for which we derive a new bounding scheme on the maximum load of any route. The second algorithm is based on random coloring from parameterized complexity which can be also combined with other techniques in the literature for improving VRPs, including cutting planes and column enumeration. We conduct numerical studies using VRP benchmarks (with 50–957 nodes) and instances of a medical home care delivery problem using census data in Wayne County, Michigan. Using parallel computing, both pulse and random coloring can significantly improve column generation for solving the linear programming relaxations and we can obtain heuristic integer solutions with small optimality gaps. Combining random coloring with column enumeration, we can obtain improved integer solutions having less than 2% optimality gaps for most VRP benchmark instances and less than 1% optimality gaps for the medical home care delivery instances, both under a 30-minute computational time limit. The use of cutting planes (e.g., robust cuts) can further reduce optimality gaps on some hard instances, without much increase in the run time. Summary of Contribution: The vehicle routing problem (VRP) is a fundamental combinatorial problem, and its variants have been studied extensively in the literature of operations research and computer science. In this paper, we consider general-purpose algorithms for solving VRPs, including the column-generation approach for the linear programming relaxations of the integer programs of VRPs and the column-enumeration approach for seeking improved integer solutions. We revise the pulse algorithm and also propose a random-coloring algorithm that can be used for solving the elementary shortest path problem that formulates the pricing problem in the column-generation approach. We show that the parallel implementation of both algorithms can significantly improve the performance of column generation and the random coloring algorithm can improve the solution time and quality of the VRP integer solutions produced by the column-enumeration approach. We focus on algorithmic design for VRPs and conduct extensive computational tests to demonstrate the performance of various approaches.
more »
« less
This content will become publicly available on May 21, 2026
Practical and Effective Heuristics for the Backhaul Profit Maximization Problem
Abstract Given an empty delivery vehicle, the backhaul profit maximization problem (BPMP) is to select a profit-maximizing subset of available pick-up-and-delivery requests to accept considering the vehicle’s capacity and a time limit for the vehicle to reach a specified destination or, equivalently, a driving-distance limit. Implemented in our computing environment, the fastest known exact algorithm for BPMP requires approximately 11 hours and 44 minutes on average to solve the largest instances in the literature, which have 70 to 80 potential pick-up/drop-off locations. The fastest available heuristic from the literature is considerably faster, and finds high quality solutions, but requires a state-of-the-art mixed-integer programming solver. We present a heuristic framework for the BPMP based on greedy construction, iterative local search, and randomization. Algorithms developed with the framework are implemented in the freely and widely available C++ language and their effectiveness is demonstrated through an extensive computational experiment on both benchmark and randomly generated problem instances. We find that our approach is competitive with approaches from the literature in solution quality as well as running time.
more »
« less
- Award ID(s):
- 2227548
- PAR ID:
- 10655376
- Publisher / Repository:
- SpringerNature
- Date Published:
- Journal Name:
- Networks and Spatial Economics
- Volume:
- 25
- Issue:
- 4
- ISSN:
- 1566-113X
- Page Range / eLocation ID:
- 957 to 984
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
In this paper, we consider an integrated vehicle routing and service scheduling problem for serving customers in distributed locations who need pick-up, drop-off, or delivery services. We take into account the random trip time, nonnegligible service time, and possible customer cancellations, under which an ill-designed schedule may lead to undesirable vehicle idleness and customer waiting. We build a stochastic mixed-integer program to minimize the operational cost plus expected penalty cost of customers’ waiting time, vehicles’ idleness, and overtime. Furthermore, to handle real-time arrived service requests, we develop K-means clustering-based algorithms to dynamically update planned routes and schedules. The algorithms assign customers to vehicles based on similarities and then plan schedules on each vehicle separately. We conduct numerical experiments based on diverse instances generated from census data and data from the Ford Motor Company’s GoRide service, to evaluate result sensitivity and to compare the in-sample and out-of-sample performance of different approaches. Managerial insights are provided using numerical results based on different parameter choices and uncertainty settings.more » « less
-
Abstract We propose easy‐to‐implement heuristics for time‐constrained applications of a problem referred to in the literature as the facility location problem with immobile servers, stochastic demand, and congestion, the service system design problem, or the immobile server problem (ISP). The problem is typically posed as one of allocating capacity to a set of M/M/1 queues to which customers with stochastic demand are assigned with the objective of minimizing a cost function composed of a fixed capacity‐acquisition cost, a variable customer‐assignment cost, and an expected‐waiting‐time cost. The expected‐waiting‐time cost results in a nonlinear term in the objective function of the standard binary programming formulation of the problem. Thus, the solution approaches proposed in the literature are either sophisticated linearization or relaxation schemes, or metaheuristics. In this study, we demonstrate that an ensemble of straightforward, greedy heuristics can rapidly find high‐quality solutions. In addition to filling a gap in the literature on ISP heuristics, new stopping criteria for an existing cutting plane algorithm are proposed and tested, and a new mixed‐integer linear model requiring no iterating algorithm is developed. In many cases, our heuristic approach finds solutions of the same or better quality than those found by exact methods implemented with expensive, state‐of‐the‐art mathematical programming software, in particular a commercial nonlinear mixed‐integer linear programming solver, given a five‐minute time limit.more » « less
-
The offline pickup and delivery problem with time windows (PDPTW) is a classical combinatorial optimization problem in the transportation community, which has proven to be very challenging computationally. Due to the complexity of the problem, practical problem instances can be solved only via heuristics, which trade-off solution quality for computational tractability. Among the various heuristics, a common strategy is problem decomposition, that is, the reduction of a large-scale problem into a collection of smaller sub-problems, with spatial and temporal decompositions being two natural approaches. While spatial decomposition has been successful in certain settings, effective temporal decomposition has been challenging due to the difficulty of stitching together the sub-problem solutions across the decomposition boundaries. In this work, we introduce a novel temporal decomposition scheme for solving a class of PDPTWs that have narrow time windows, for which it is able to provide both fast and high-quality solutions. We utilize techniques that have been popularized recently in the context of online dial-a-ride problems along with the general idea of rolling horizon optimization. To the best of our knowledge, this is the first attempt to solve offline PDPTWs using such an approach. To show the performance and scalability of our framework, we use the optimization of paratransit services as a motivating example. Due to the lack of benchmark solvers similar to ours (i.e., temporal decomposition with an online solver), we compare our results with an offline heuristic algorithm using Google OR-Tools. In smaller problem instances (with an average of 129 requests per instance), the baseline approach is as competitive as our framework. However, in larger problem instances (approximately 2,500 requests per instance), our framework is more scalable and can provide good solutions to problem instances of varying degrees of difficulty, while the baseline algorithm often fails to find a feasible solution within comparable compute times.more » « less
-
Driverless or fully automated vehicles (AVs) are expected to fundamentally change how individuals and households travel and how vehicles use roadway infrastructure. The first goal of this study is to develop a modeling framework of activity-constrained household travel in a future multi-modal network with private AVs, shared-use AVs, transit, and intermodal AV-transit travel options. The second goal is to analyze the potential impacts of AVs—including intermodal AV-transit travel—on (a) household-level travel behavior, (b) household travel costs, (c) demand for transport modes, including transit, and (d) vehicle kilometers traveled or VKT. To meet the first goal, we propose and formulate the Household Activity Pattern Problem with AV-enabled Intermodal Trips (HAPP-AV-IT) that incorporates AV deadheading and intermodal AV-transit trips. The modeling framework extends prior HAPP-based formulations that model household-level travel decisions as vehicle (and person) routing and scheduling problems, similar to the pickup and delivery problem with time-windows. To meet the second goal, we apply the HAPP-AV-IT to two case studies and conduct many computational experiments. We use synthetic activity location data for synthetic households and a fictitious medium-size network with a road network, transit network, residential locations, activity locations, and parking locations. The computational results illustrate (a) the critical role that household AV ownership plays in terms of household travel decisions, modal demand, and VKT, (b) that with AVs, deadheading accounts for 30–40 % of vehicle operating distances, (c) that around 10 % of households in the study region benefit from AV-based intermodal trips, and (d) that those 10 % of households see 5 % reductions in household travel costs and 25 % reductions in VKT on average in the most transit friendly scenario. This last finding suggests that intermodal AV-transit trips may exist in a driverless vehicle future, and therefore, transit agencies and transportation planners should consider how to serve this market. We also propose and test a simple heuristic algorithm that quickly solves HAPP-AV-IT problem instances.more » « less
