Stochastic Vehicle Routing with Random Travel Times

We consider stochastic vehicle routing problems on a network with random travel and service times. A fleet of one or more vehicles is available to be routed through the network to service each node. Two versions of the model are developed based on alternative objective functions. We provide bounds on optimal objective function values and conditions under which reductions to simpler models can be made. Our solution method embeds a branch-and-cut scheme within a Monte Carlo sampling-based procedure.