Stochastic shortest path problems with piecewise-linear concave utility functions

This paper considers a stochastic shortest path problem where the arc lengths are independent random variables following a normal distribution. In this problem, the optimal path is one that maximizes the expected utility, with the utility function being piecewise-linear and concave. Such a utility function can be used to approximate nonlinear utility functions that capture risk averse behaviour for a wide class of problems. The principal contribution of this paper is the development of exact algorithms to solve large problem instances. Two algorithms are developed and incorporated in labelling procedures. Computational testing is done to evaluate the performance of the algorithms. Overall, both algorithms are very effective in solving large problems quickly. The relative performance of the two algorithms is found to depend on the ‘curvature’ of the piecewise linear utility function.