A relaxation-based purning technique for a class of stochastic shortest path problems

A relaxation-based purning technique for a class of stochastic shortest path problems

0.00 Avg rating0 Votes
Article ID: iaor1997908
Country: United States
Volume: 30
Issue: 3
Start Page Number: 220
End Page Number: 236
Publication Date: Aug 1996
Journal: Transportation Science
Authors: ,
Keywords: networks: path
Abstract:

In this paper a form of the stochastic shortest path problem is considered where the optimal path is one that maximizes the expected utility which is concave and quadratic. The principal contribution of this paper is the development of a relaxation based pruning technique which is incorporated into a label setting procedure. The basic label setting procedure solves the problem by generating all Pareto-optimal paths. However, the number of such paths can grow exponentially with the size of the problem. The relaxation based pruning technique developed here is able to recognize and discard most of the Pareto-optimal paths that do not contribute to the optimal path. The present computational results show that the label setting procedure that incorporates the pruning technique consistently outperforms the basic label setting procedure, and is able to solve large problems very quickly.

Reviews

Required fields are marked *. Your email address will not be published.