The Sample Average Approximation Method applied to Stochastic Routing Problems

In this thesis most parts of the computational study of Verweij et al. (2003) on the Sample Average Approximation (SAA) method have been replicated. The SAA method uses Monte Carlo simulation to solve stochastic optimization problems. Verweij et al. (2003) investigated the Shortest Path Problem with Random Travel Times (SPRT), the Shortest Path Problem with Random Arc Failures (SPAF) and the Traveling Salesman Problem with Random Travel Times (TSPRT). We have replicated both the SPRT and TSPRT. Additionally, we extended the TSPRT to a Vehicle Routing Problem with Random Travel Times (VRPRT). Some differences in results are expected as different versions of the same commercial MIP solver CPLEX have been used. Besides, the SAA method makes use of random generated samples, so different samples are expected. Precise instances are also not available, so reconstructing them as close as possible was the only option, but the dimensions turned out to be different. The results for the SPRT are close to those found by Verweij et al. (2003). However, for the TSPRT the found values are much larger. When comparing the TSPRT and VRPRT results, we see that the difference is quite small. Taking customer satisfaction into account, it might be beneficial to use multiple vehicles. Further research on the VRPRT using different deadlines and different amounts of vehicles could therefore be interesting.