Flexible Milk-Runs for Stochastic Vehicle Routing

We study a vehicle routing problem with stochastic demands in which the goal is to find an optimal set of vehicle routes, such that the capacity of each vehicle is not exceeded with a given probability. We introduce ‘flexible milk-runs’, or flex-runs, to model this problem as a set covering problem to find (near-)optimal solutions. We apply our methodology to design new freight routes for the North-American division of the Bosch/Siemens Home Appliances Corporation. Our computational experiments indicate an expected transportation cost reduction of up to 25%, while at the same time the new routes realize overall increase in robustness with respect to demand fluctuations.