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 p ath that maximizes the expected utility is considered. The nature of t he 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 inc orporated 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 contai ning the same preference relation, but two different relaxations. Our extensive computational testing indicate that both these algorithms ar e able to solve even large size problems quickly. More importantly, ev en for large problems, both the algorithms solved them by enumerating a very small percentage of all paths. (C) 1997 Elsevier Science B.V.