- A Unifying Framework for the Capacitated Vehicle Routing Problem under Risk and Ambiguity Shubhechyya Ghosal(s.ghosal16imperial.ac.uk) Chin Pang Ho(clint.hocityu.edu.hk) Wolfram Wiesemann(wwimperial.ac.uk) 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 $\phi$-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. Keywords: Capacitated Vehicle Routing Problem, Stochastic Programming, (Distributionally) Robust Optimization Category 1: Applications -- OR and Management Sciences Category 2: Robust Optimization Category 3: Stochastic Programming Citation: Download: [PDF]Entry Submitted: 10/14/2021Entry Accepted: 10/14/2021Entry Last Modified: 10/14/2021Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.