Hardness of Pricing Routes for Two-Stage Stochastic Vehicle Routing Problems with Scenarios

The vehicle routing problem with stochastic demands (VRPSD) generalizes the classic vehicle routing problem by considering customer demands as random variables. Similar to other vehicle routing variants, state-of-the-art algorithms for the VRPSD are often based on set-partitioning formulations, which require efficient routines for the associated pricing problems. However, all of these set partitioning–based approaches have strong assumptions on the correlation between the demands of random variables (e.g., no correlation), a simplification that diverges from real-world settings where correlations frequently exist. In contrast, there is a significant effort in the stochastic programming community to solve problems where the uncertainty is modeled with a finite set of scenarios. This approach can approximate more diverse distributions via sampling and is particularly appealing in data-driven contexts where historical data are readily available. To fill this gap, we focus on the VRPSD with demands given by scenarios. We show that for any route relaxation (where repeated visits are allowed in a route) and any approximation of the recourse cost that satisfies some mild assumptions, the VRPSD pricing problem is still strongly $\mathcal{N}\mathcal{P}$-hard. This provides a very strong argument for the difficulty of developing efficient column generation–based algorithms for the VRPSD with demands following an empirical probability distribution of scenarios.

Funding: This work was supported by Natural Sciences and Engineering Research Council of Canada [Grant RGPIN-2020-04030].