On vehicle routing problems with stochastic demands -- Generic disaggregated integer L-shaped formulations

We study the vehicle routing problem with stochastic demands (VRPSD), an important variant of the classical capacitated vehicle routing problem in which customer demands are modeled as random variables. We develop the first algorithm for the VRPSD in the case where the demands are given by an empirical probability distribution of scenarios -- a data-driven variant that tackles a significant challenge identified in the literature: dealing with correlations. Indeed, most previous exact algorithms for this problem relied on independence of the random variables. To address the VRPSD with scenarios, we introduce a unifying framework that generalizes existing integer L-shaped (ILS) formulations developed for other variants of the problem. This framework and subsequent analysis allow us to generalize previous ILS cuts and pinpoint which assumptions are needed to apply those generalizations. In particular, our results enable, for the first time, the combination of two previous types of inequalities: partial route and set cuts, which leads to significant computational improvements.