Hardness of pricing routes for two-stage stochastic vehicle routing problems with scenarios

Abstract

Following state-of-the-art exact algorithms for vehicle routing problems, several recent exact algorithms for the two-stage vehicle routing problem with stochastic demands (VRPSD) are based on set partitioning formulations. To solve the corresponding LP relaxation, these algorithms rely on efficient routines for solving the associated pricing problems. In this paper, we study the complexity of solving such VRPSD pricing problems. While most of the previous algorithms for the VRPSD assume that the probability distributions of the demands are independent and have a convolution property, we instead model the probability distribution with a finite set of demand scenarios. In this case, we show that, for any choice of a generic recourse cost function that satisfies a set of mild assumptions, the VRPSD pricing problem is strongly NP-hard — even when the edge costs are determined by the reduced costs of a restricted master problem. Therefore, our results not only extend and generalize previous results in the literature, but also provide a stronger argument for the difficulty of developing efficient column-generation based algorithms for the VRPSD with a probability distribution given by scenarios.