Stochastic Shortest Path Problems with Piecewise-Linear Concave Utility Functions

Ishwar Murthy and Sumit Sarkar
Additional contact information
Ishwar Murthy: Department of Information Systems and Decision Sciences, Louisiana State University, Baton Rouge, Lousiana 70803
Sumit Sarkar: School of Management, University of Texas at Dallas, Richardson, Texas 75080

Management Science, 1998, vol. 44, issue 11-Part-2, S125-S136

Abstract: This paper considers a stochastic shortest path problem where the arc lengths are independent random variables following a normal distribution. In this problem, the optimal path is one that maximizes the expected utility, with the utility function being piecewise-linear and concave. Such a utility function can be used to approximate nonlinear utility functions that capture risk averse behaviour for a wide class of problems. The principal contribution of this paper is the development of exact algorithms to solve large problem instances. Two algorithms are developed and incorporated in labelling procedures. Computational testing is done to evaluate the performance of the algorithms. Overall, both algorithms are very effective in solving large problems quickly. The relative performance of the two algorithms is found to depend on the "curvature" of the piecewise linear utility function.

Keywords: Stochastic; Shortest Path; Networks (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.44.11.S125 (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:ormnsc:v:44:y:1998:i:11-part-2:p:s125-s136

Access Statistics for this article

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