Optimal a priori tour and restocking policy for the single-vehicle routing problem with stochastic demands

We present a model for the single-vehicle routing problem with stochastic demands (SVRPSD) with optimal restocking. The model is derived from a characterization of the SVRPSD as a Markov decision process (MDP) controlled by a certain class of policies, and is valid for general discrete demand probability distributions. We transform this MDP into an equivalent mixed-integer linear model, which is then used to solve small instances to optimality. By doing so, we are able to quantify the drawbacks associated with the detour-to-depot restocking policy, an assumption of many exact approaches for the (multivehicle) VRPSD. We also examine the tradeoff between the deterministic a priori cost and the stochastic restocking cost for varying route load scenarios. Finally, a wait-and-see model for the SVRPSD is proposed, and is used within a parallel heuristic to solve larger literature instances with up to 150 nodes and Poisson distributed demands. Computational experiments demonstrate the effectiveness of the heuristic approach, and also indicate under which circumstances near-optimal solutions can be obtained by the myopic strategy of a priori route cost minimization.