A unifying framework for the capacitated vehicle routing problem under risk and ambiguity

Abstract

We propose a generic model for the capacitated vehicle routing problem (CVRP) under demand uncertainty. By combining risk measures or disutility functions with complete or partial characterizations of the probability distribution governing the demands, our formulation bridges the popular but often independently studied paradigms of stochastic programming and distributionally robust optimization. We characterize when an uncertainty-affected CVRP is (not) amenable to a solution via a popular branch-and-cut scheme, and we elucidate how this solvability relates to the interplay between the employed decision criterion and the available description of the uncertainty. Our framework offers a unified treatment of several CVRP variants from the recent literature, such as formulations that optimize the requirements violation or the essential riskiness indices, while it at the same time allows us to study new problem variants, such as formulations that optimize the worst-case expected disutility over Wasserstein or φ-divergence ambiguity sets. All of our formulations can be solved by the same branch-and-cut algorithm with only minimal adaptations, which makes them attractive for practical implementations.