Abstract
Rollout algorithms lead to effective heuristics for the single vehicle routing problem with stochastic demands (VRPSD), a prototypical model of logistics under uncertainty. However, they can be computationally intensive. To reduce their run time, we introduce a novel approach to approximate the expected cost of a route when executing any rollout algorithm for VRPSD with restocking. With a sufficiently large number of customers its theoretical speed-up factor is of big-o order 1/3. On a set of instances from the literature, our proposed technique applied to a known rollout algorithm and three variants thereof achieves speed-up factors that range from 0.26 to 0.34 when there are more than fifty customers, degrading only marginally the quality of the resulting routes. Our method also applies to the a priori case, in which case it is exact.
1. Introduction
Given a set of geographically dispersed customers, a quantity to deliver to each customer, and a fleet of capacitated vehicles located at a depot, the vehicle routing problem consists of determining a set of minimal cost routes, each starting and ending at the depot, such that the demand of all the customers is satisfied without exceeding the capacity of the vehicles. Since its introduction by Dantzig and Ramser (1959), this problem and variants thereof have been well studied (see Fisher, 1995; Laporte, 1992; Toth & Vigo, 2014; and Laporte, 2009 for reviews).
In the vehicle routing problem with stochastic demands (VRPSD), given probability distributions describe the customer demands and the realization of the demand of a customer becomes known upon the first visit to this customer. If the realized demand of a customer exceeds the remaining capacity of a vehicle when this customer is visited then a route failure occurs and a recourse action must be taken. VRPSD is relevant in both strategic distribution planning, when only estimates of customer demands are typically available, and tactical and operational decision making, when there remains residual uncertainty about the demands of the customers.
6. Conclusions
Rollout algorithms are known to yield good solutions for VRPSD with a single vehicle, an important model for research and applications in logistics under uncertainty. Nonetheless, their computational burden can be substantial. To alleviate this issue, we develop a novel approach to approximate the expected cost of a VRPSD route under the restocking strategy that applies to any rollout algorithm. We establish that the theoretical speed-up factor of our technique is of big-o order equal to 1/3 when the number of customers is sufficiently large. Our numerical study, based on a set of instances from the literature and a known rollout algorithm and three variants thereof, indicates that our proposed method yields observed speed-up factors that vary between 0.26 and 0.34 when there are at least 50 customers. These ranges are in line with the 1/3 limiting value for the theoretical big-o order speed-up factor. These savings are achieved by only marginally degrading the quality of the resulting restocking routes.
