Recourse Actions for Capacitated Vehicle Routing Problems with Stochastic Demand

In this thesis we will focus on the capacitated vehicle routing problem with stochastic demands. When demand is subject to uncertainty, routes must be defined (at least partially) before the real demand values of the customers become known. Companies might for example have access to some statistical information about the demands in order to define these routes. In some situations, a vehicle may not have sufficient stock available to meet a customer’s demand upon arrival, in which case a route failure is said to have occurred. Recourse actions can be applied in order to amend these failures. The action to take when a failure takes place has strong implications on the satisfaction of customers, as well as on the profitability of suppliers. In this thesis the effect of choosing different recourse actions is studied.

Our numerical experiments show that it is possible to improve on the simplest recourse action (detour to depot) by introducing more sophisticated recourse actions. In particular, re-optimizing the routes when failures occur provides significantly better results compared to using routes that are completely planned a priori.