A Unifying Framework for the Capacitated Vehicle Routing Problem Under Risk and Ambiguity

• 成果类型: Article
• 署名作者: Ghosal, Shubhechyya; Ho, Chin Pang; Wiesemann, Wolfram
• 署名单位: Imperial College London; City University of Hong Kong
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2021.0669
• 发表日期: 2024
• 关键词: capacitated vehicle routing problem; Stochastic Programming; distributionally robust optimization; branch-and-cut

摘要

We propose a generic model for the capacitated vehicle routing problem (CVRP) under demand uncertainty. By combining risk measures, satisficing 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, and 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.