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

The paper addresses 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 for which otpimal solution procedures can solve only small problems. Presently, it cannot even begin testing optimal solution procedures for the SVRP for any problem size exceeding 3 nodes. Thus, the paper needs to examine modeling approaches to this problem in order to exploit the structure and solution properties. It presents a multistage stochastic model for the SVRP. The paper proves that this model has an interesting minimal graph representation in which a SVRP solution corresponds to a Hamiltonian cycle. It also presents a Markov decision model for the problem, concluding with a discussion of solution prospects and directions.