A priori optimization with recourse for the vehicle routing problem with hard time windows and stochastic service times
The vehicle routing problem with hard time windows and stochastic service times (VRPTW ST) introduced by Errico et al. (2013) in the form of a chance constrained model mainly differs from other vehicle routing problems with stochastic service or travel times considered in the literature by the presence of hard time windows. This makes the problem extremely challenging. In this paper, we model the VRPTW ST as a two stage stochastic program and define two recourse policies to recover operations feasibility when the first stage plan turns out to be infeasible. We formulate the VRPTW ST as a set partitioning problem and solve it by exact branch cut and price algorithms. Specifically, we developed efficient labeling algorithms by suitably choosing label components, determining extension functions, and developing lower and upper bounds on partial route reduced cost to be used in the column generation step. Results on benchmark data show that our methods are able to solve instances with up to 50 customers for both recourse policies.
Eur. J. Oper. Res.