Seminar by Prof. Wolfram Wiesemann, Imperial College London
Event details
| Date | 14.12.2018 |
| Hour | 16:00 › 17:30 |
| Speaker | Prof. Wolfram Wiesemann, Imperial College London |
| Location | |
| Category | Conferences - Seminars |
"Distributionally Robust Chance Constrained Vehicle Routing"
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. 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.
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. 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.
Practical information
- General public
- Free