Optimization Online


The Distributionally Robust Chance Constrained Vehicle Routing Problem

Shubhechyya Ghosal (s.ghosal16***at***imperial.ac.uk)
Wolfram Wiesemann (ww***at***imperial.ac.uk)

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

Category 1: Robust Optimization

Category 2: Stochastic Programming

Category 3: Applications -- OR and Management Sciences (Transportation )


Download: [PDF]

Entry Submitted: 08/03/2018
Entry Accepted: 08/03/2018
Entry Last Modified: 04/12/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society