Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function

In this paper, the stochastic shortest path problem of determining a path that maximizes the expected utility is considered. The nature of the utility function used to evaluate paths is of a decreasing deadline type. The principal contribution of this paper is the development of exact algorithms that use two types of pruning techniques that are incorporated in labeling procedures. One type of pruning makes use of the concept of local preference relations while the other type makes use of relaxations. Specifically two algorithms are developed, each containing the same preference relation, but two different relaxations. Our extensive computational testing indicates that both these algorithms are able to solve even large size problems quickly. More importantly, even for large problems, both the algorithms solved them by enumerating a very small percentage of all paths.