The Distributionally Robust Chance-Constrained Vehicle Routing Problem

Shubhechyya Ghosal () and Wolfram Wiesemann ()
Additional contact information
Shubhechyya Ghosal: Imperial College Business School, Imperial College London, SW7 2AZ London, United Kingdom
Wolfram Wiesemann: Imperial College Business School, Imperial College London, SW7 2AZ London, United Kingdom

Operations Research, 2020, vol. 68, issue 3, 716-732

Abstract: 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 − ε, where ε 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.

Keywords: vehicle routing; distributionally robust optimization; chance constraints (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
https://doi.org/10.1287/opre.2019.1924 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:68:y:2020:i:3:p:716-732

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().