Distributionally Robust Chance Constrained Vehicle Routing

Wolfram Wiesemann is Associate Professor of Management Science and Operations as well as Fellow of the KPMG Centre for Advanced Business Analytics at Imperial College Business School, London. Before joining the faculty of Imperial College Business School in 2013, he was a post-doctoral researcher at Imperial College London (2010-2011) and an Imperial College Research Fellow (2011-2012). He was a visiting researcher at the Institute of Statistics and Mathematics at Vienna University of Economics and Business, Austria, in 2010, the Computer-Aided Systems Laboratory at Princeton University, USA, in 2011, and the Industrial Engineering and Operations Research Department at Columbia University, USA, in 2012. Wolfram’s research interests revolve around the methodological aspects of decision-making under uncertainty, as well as applications in operations management, energy and finance.

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. Moreover, we 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 modern branch-and-cut algorithms if and only if 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.

Registration to Krzysztof Postek, postek@ese.eur.nl  is required for availability of lunch.