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

The article focuses on the computational complexity of the pricing problem in two-stage stochastic vehicle routing problems with scenarios (VRPSD with scenarios), where customer demands are modeled by an empirical distribution over a finite set of scenarios. It establishes that, under mild assumptions on the recourse cost function—which generalizes various recourse policies—the pricing problem remains strongly NP-hard even when approximate second-stage costs and route relaxations (e.g., ng-routes) are allowed. The authors prove this by a novel reduction from the independent set problem, demonstrating that the hardness persists even when edge costs correspond to reduced costs from dual solutions in column generation. These results imply significant challenges for designing exact column generation–based algorithms for VRPSD with scenarios and suggest that alternative methods, such as ignoring recourse costs in pricing and using integer L-shaped cuts, may be necessary.