Finding the most reliable path in a stochastic network

This thesis studies the problem of finding the most reliable path between two nodes on a graph, when the exact travel times are unknown. It is desirable that a path is quick on average, while at the same time the arrival time should be easy to predict. Therefore the objective is to minimize a weighted sum of mean and standard deviation. Since this objective function is non-linear and non-convex, standard methods cannot be used. We analyze and implement the algorithm proposed by Xing and Zhou (2011) to find close-to-optimal paths. The algorithm is based on a Lagrangian substitution approach, which results in a sequence of shortest path problems. The Lagrangian multipliers are updated using subgradient optimization. The analysis of Xing and Zhou (2011) is extended in two ways. First, instead of minimizing a weighted sum of mean and standard deviation, we analyze the objective of maximizing on-time arrival probability, in case of a normal distribution. Second, the algorithm is extended to allow for rerouting decisions along the way. For both extensions, examples are presented that illustrate the theory and the algorithms. All methods are tested on a number of randomly generated graphs.