Shortest paths subject to time-varying stochastic transit times

We consider a stochastic, time-varying shortest path problem, where the transit time on an arc is a random variable taking discrete values, and the transit cost on an arc is a known function of the amount of the transit time. Waiting at a vertex is allowed, at a waiting cost. By utilizing the discrete nature of the transit times and their probabilistic distributions, we develop an efficient dynamic programming algorithm to determine the shortest (cheapest) path from a source vertex to a sink vertex.