Pseudo-Compact Formulation for the Problem of Routing Vehicles with Stochastic Demands

This paper addresses the Capacitated Vehicle Routing Problem with Stochastic Demands, in which routes are planned a priori and out-and-back replenishment trips to the depot, called as recourse actions, are performed whenever the vehicle becomes empty. We propose a pseudo-compact mixed-integer linear programming formulation, which computes the expected cost of recourse within the model through the so-called expected recourse cost explicit constraints, introduced in this paper. Building upon this formulation, three solution approaches of increasing level of sophistication are proposed: direct solution with a general-purpose MIP solver; a branch-and-cut method with expected capacity inequalities; and a branch-and-cut method with a tailored separation algorithm for the proposed inequalities. Computational experiments show that the proposed approaches solve small- and medium-sized instances to optimality and obtain high-quality solutions for instances with up to 60 customers.