A sampling approach to solve the vehicle routing problem with time windows and stochastic travel times

In this paper, we discuss the vehicle routing problem with time windows (VRPTW) where stochastic travel times are assumed. In a first step, a variable neighborhood search (VNS) approach is proposed for the VRPTW where deterministic data is assumed. This approach is extended in a second step by adding a sampling approach to deal with the stochastic travel times. Problem instances are proposed that are based on the well-known Solomon instances from the literature. The resulting routes are executed in a stochastic environment to assess the performance of the proposed heuristic. Computational experiments demonstrate that it is reasonable to incorporate stochastic knowledge into VRPTW algorithms.