Pseudo-Compact Formulations and Branch-and-Cut Approaches for the Capacitated Vehicle Routing Problem with Stochastic Demands

In this paper, we address the Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD), in which routes are planned a priori and recourse actions are performed to ensure demand fulfillment. These recourse actions are defined through policies and may include replenishment trips or demand backlogging subject to penalties. We develop the first family of pseudo-compact MIP formulations for different recourse policies, which explicitly determine the expected recourse cost of routes. These formulations allow us to write closed models for the CVRPSD and use them straightforwardly within general-purpose MIP solvers. To the best of our knowledge, this is the first exact approach for the CVRPSD that does not rely on tailored cutting-plane or branch-and-price algorithms, making it accessible to a broader range of practitioners and researchers. Extensive computational experiments show that the proposed formulations can be used to solve small to medium-sized instances to optimality using standalone MIP solvers. We also develop simple yet effective branch-and-cut methods upon these formulations, with performance comparable to state-of-the-art methods over different benchmarks, finding proven optimal solutions for previously unsolved asymmetric instances.

Article

Download

View PDF