Extending the sample average approximation method to the traveling salesman problem with random travel times and soft time windows

In this thesis, we apply the sample average approximation method to stochastic routing problems. We replicate the results by Verweij et al. (2003) with respect to the shortest path problem with random travel times and the traveling salesman problem with random travel times. In addition, we propose a branch-and-cut framework to apply the sample average approximation method to the traveling salesman problem with random travel times and soft time windows. Different approaches for eliminating subtours are evaluated. We find that we can solve the problems using less memory by adding subtour elimination constraints in fractional branch-and-bound nodes.