Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function |
| |
Institution: | 1. Department of Industrial and Management Systems Engineering, College of Engineering and Petroleum, Kuwait University, P.O. Box 5969, Safat, Kuwait;2. Department of Mathematics and Natural Sciences, Gulf University for Science and Technology, P.O. Box 7207, Hawally 32093, Kuwait;3. Department of Economics and Finance, Gulf University for Science and Technology, P.O. Box 7207, Hawally 32093, Kuwait |
| |
Abstract: | 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 indicate 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|