The Distributionally Robust Chance-Constrained Vehicle Routing Problem

• 成果类型: Article
• 署名作者: Ghosal, Shubhechyya; Wiesemann, Wolfram
• 署名单位: Imperial College London
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2019.1924
• 发表日期: 2020
• 页码: 716-732
• 关键词: cut-and-price; optimization; uncertainty; algorithm; capacity; RISK

摘要

We study a variant of the capacitated vehicle routing problem (CVRP), which asks for the cost-optimal delivery of a single product to geographically dispersed customers through a fleet of capacity-constrained vehicles. Contrary to the classical CVRP, which assumes that the customer demands are deterministic, we model the demands as a random vector whose distribution is only known to belong to an ambiguity set. We then require the delivery schedule to be feasible with a probability of at least 1 - e, where e characterizes the risk tolerance of the decision maker. We argue that the emerging distributionally robust CVRP can be solved efficiently with standard branch-and-cut algorithms whenever the ambiguity set satisfies a subadditivity condition. We then show that this subadditivity condition holds for a large class of moment ambiguity sets. We derive efficient cut generation schemes for ambiguity sets that specify the support as well as (bounds on) the first and second moments of the customer demands. Our numerical results indicate that the distributionally robust CVRP has favorable scaling properties and can often be solved in runtimes comparable to those of the deterministic CVRP.