Regret-Bounded Vehicle Routing
Professor Zachary Friggstad, Canada Research Chair Tier-II in Combinatorial Optimization, Department of Computing Science, University of Alberta.
Room: C674, University Hall
A typical vehicle routing problem involves deploying a fleet of vehicles to serve some clients. Many well-studied models are concerned mostly with the distance travelled by the vehicles. However, this objective does not differentiate between clients that are located at different distances from the depot. For example, a client closer to the depot may incur a larger delay than a client that is further away in a minimum-length TSP tour. This can be a source of client dissatisfaction.
This leads us to consider the notion of regret of a client: the time a client waits to be served in excess of its shortest-path distance from the depot. I will discuss old and new approximation algorithms for client-centric vehicle routing models and their applications to more classical models. In particular, I will present the first constant-factor approximation for the problem of deploying the fewest vehicles to ensure each client is served with regret at most some given bound B.
Students are encouraged to attend.
Professor Friggstad’s main research interests lie in designing approximation algorithms and, more specifically, in investigating the effectiveness of mathematical programming based techniques in the design of such algorithms. His research has been applied to problems in vehicle routing, facility location, resource allocation, network design, and lift-and-project techniques. Professor Friggstad is a University of Lethbridge alumnis (2005) and, as a student, he has competed twice in the ACM Programming Contest World Finals obtaining one Bronze Medal in 2006.