Title: The vehicle routing problem with hard time windows and stochastic service times

Speaker: Fausto Errico, ETS, Canada

Abstract:

In this talk I will consider a variant of the vehicle routing problem with time windows, where service times are affected by uncertainty. This problem appears in various practical applications where drivers (e.g., repairmen) perform specific services at customers, without knowing service durations beforehand.  Previous literature mostly focused on situations where customer time windows might be violated (soft time windows). I will instead address the case where such violations are not allowed (hard time windows), as required in many practical settings. In the first part of the talk, I will model the problem as a chance constraint stochastic program. In the second, I will adopt a two-stage stochastic model and compare alternative recourse strategies. For each model setting, I will show how to develop efficient branch-cut-and-price algorithms. These methods solved problem instances derived from the Solomon database with up to 50 customers.

This is a joint work with G. Desaulniers, M. Gendreau, W. Rei and L.-M. Rousseau.