Two-stage linear stochastic programming formulations for the Stochastic Vehicle Routing Problem with Backhauls and Time Windows

Due to their broad existence in industrial and service companies, decision-making under uncertainty for the well-known Vehicle Routing Problem (VRP) are among today's most critical challenges. This paper focuses on the design of routes to be developed considering the variability of some parameters for the Vehicle Routing Problem with Backhauls and Time Windows (VRPBTW). Travel times have mainly been considered a stochastic component and modelled using a statistical distribution for the VRPBTW, generating a new problem called Stochastic Vehicle Routing Problem with Backhauls and Time Windows (SVRPBTW). We introduce the SVRPBTW and propose an efficient solution method for solving it, considering two-stage linear stochastic programming formulations with two (SILP2I model) and three (SILP3I model) indices and the Sample Average Approximation (SAA) as solution method. The results obtained from real data show the efficiency of the proposed methodology. The proposed stochastic models (SILP2I and SILP3I) for the SVRPBTW have been compared with their deterministic versions (MILPs) for the VRPBTW. The SILP2I model outperforms the results obtained by its deterministic version and by the SILP3I model for all the set of instances.