Stochastic shortest path problems with piecewise-linear concave utility functions

This paper considers a stochastic shortest path problem where the are lengt hs are independent random variables following a normal distribution. In thi s problem, the optimal path is one that maximizes the expected utility, wit h the utility function being piecewise-linear and concave. Such a utility f unction can be used to approximate nonlinear utility functions that capture risk averse behaviour for a wide class of problems. The principal contribu tion of this paper is the development of exact algorithms to solve large pr oblem instances. Two algorithms are developed and incorporated in labelling procedures. Computational testing is done to evaluate the performance of t he 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.