Tutte Colloquium - Ricardo Fukasawa

Zoom (for information email emma.watson@uwaterloo.ca) 

Title: Hardness of set-partitioning formulation for the vehicle routing problem with stochastic demands

Abstract:

The vehicle routing problem considers the cheapest way to serve a set of customers using a fixed set of vehicles. When a vehicle serves a customer, it picks up its demand which is given as an input, and the total demand picked up cannot exceed the vehicle’s capacity. This classical combinatorial optimization problem combines aspects of routing (like a traveling salesman problem) and packing (like a knapsack problem). The vehicle routing with stochastic demands (VRPSD) arises when demands are assumed to be random variables.

In this talk we will focus on integer programming formulations for the VRPSD. The most successful formulations for the deterministic problem are based on a set-partitioning formulation, thus it is natural to try and adapt these ideas to the VRPSD. However, we show that there are some natural barriers for doing so, by proving hardness results for solving the LP relaxations of such formulations.

This talk is based on joint work with Joshua Gunter.