Modeling vehicle routing with uncertain demands as a stochastic program: Properties of the corresponding solution

In this paper we address the issue of different mathematical models for the stochastic vehicle routing problem (SVRP). This problem is inherently much more difficult than the generic deterministic vehicle routing problem (VRP) for which optimal procedures can solve only small problems. Presently, we cannot even begin optimal solution procedures for the SVRP for any problem size exceeding 3 nodes. Thus, we need to examine modeling approaches to this problem in order to exploit the structure and solution properties. We present a multistate stochastic model for the SVRP. We prove that this model has an interesting minimal graph representation in which a SVRP solution corresponds to a Hamiltonian cycle. We also present a Markov decision model for the problem, concluding with a discussion of solution prospects and directions.