Vehicle Routing with Probabilistic Capacity Constraints

What is it about?

We study chance-constraint vehicle routing with stochastic demands. We propose a set partitioning formulation for the underlying problem and solve it via a branch-and-price method. Our method is flexible in modeling different types of demand randomness while ensuring that the resulting problem is tractable. An extensive computational analysis, which includes simulation tests and a sensitivity analysis, is carried out to investigate the solution quality and computational efficiency. Some large instances of the underlying problems from the VRP library are solved to optimality for the first time. Our sensitivity analysis provides some useful insights about the impact of the probability of route failure on the decision variables, the expected cost and the route reliability.

Featured Image

Why is it important?

* A set-partitioning model for chance-constraint vehicle routing problems is proposed. * Some dominance rules are introduced for solving the stochastic pricing problem. * The complexity remains tractable for several types of distribution functions. * Some large standard instances are solved to optimality for the first time. * Extensive experiments including simulation and sensitivity analysis are carried.