Vehicle routing with stochastic demands: Models & computational methods

In this paper we provide an overview and modeling details regarding vehiclerouting in situations in which customer demand is revealed only when the vehiclearrives at the customer’s location. Given a fixed capacity vehicle, this settinggives rise to the possibility that the vehicle on arrival does not have sufficientinventory to completely supply a given customer’s demand. Such an occurrenceis called a route failure and it requires additional vehicle trips to fully replenishsuch a customer. Given a set of customers, the objective is to design vehicleroutes and response policies which minimize the expected delivery cost by afleet of fixed capacity vehicles. We survey the different problem statements andformulations. In addition, we describe a number of the algorithmic developmentsfor constructing routing solutions. Primarily we focus on stochastic programmingmodels with different recourse options. We also present a Markov decisionapproach for this problem and conclude with a challenging conjecture regardingfinite sums of random variables.