A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems

Ishwar Murthy and Sumit Sarkar
Additional contact information
Ishwar Murthy: Department of Information Systems and Decision Sciences, Louisiana State University, Baton Rouge, Louisiana 70803
Sumit Sarkar: Department of Information Systems and Decision Sciences, Louisiana State University, Baton Rouge, Louisiana 70803

Transportation Science, 1996, vol. 30, issue 3, 220-236

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. Our 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.

Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (15)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.30.3.220 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:30:y:1996:i:3:p:220-236

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().