The Vehicle Routing Problem with Stochastic Travel Times

This paper considers vehicle routing problems (VRPs) with stochastic service and travel times, in which vehicles incur a penalty proportional to the duration of their route in excess of a preset constant. Three mathematical programming models are presented: a chance constrained model, a three-index simple recourse model and a two-index recourse model. A general branch and cut algorithm for the three models is described. Computational results indicate that moderate size problems can be solved to optimality.