A vehicle routing problem with stochastic demand and capacity constraints on the edges

We consider an interesting variation of the classical vehicle routing problem, in which demands are stochastic and capacity constraints are on the edges. Given a probabilistic description of the demand we use the approach of find an a priori sequence among all customers of minimal expected total length. Depending on when information about a customer's demand becomes available we can define two different strategies for updating the routes. We find expressions to compute the expected length of an a priori sequence under the two updating strategies. Based on these expressions we find upper and lower bounds for the optimal expected length. Finally we apply simulated annealing algorithm to find an a priori sequence of minimal expected total length.