Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Visit our COVID-19 information website to learn how Warriors protect Warriors.
Please note: The University of Waterloo is closed for all events until further notice.
Zoom (for information email emma.watson@uwaterloo.ca)
Title: Hardness of set-partitioning formulation for the vehicle routing problem with stochastic demands
Speaker: | Ricardo Fukasawa |
Affiliation: | University of Waterloo |
Location: | Online (Zoom) |
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.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Indigenous Initiatives Office.