Arc Reduction and Path Preference in Stochastic Acyclic Networks

Jonathan F. Bard and James E. Bennett
Additional contact information
Jonathan F. Bard: Department of Mechanical Engineering, Operations Research Group, University of Texas, Austin, Texas 78712
James E. Bennett: Department of Mechanical Engineering, Operations Research Group, University of Texas, Austin, Texas 78712

Management Science, 1991, vol. 37, issue 2, 198-215

Abstract: The paper presents a heuristic for determining the path that maximizes the expected utility of a stochastic acyclic network. The focus is on shortest route problems where a general, nonlinear utility function is used to measure outcomes. For such problems, enumerating all feasible paths is the only way to guarantee that the global optimum has been found. Alternatively, we develop a reduction algorithm based on stochastic dominance to speed up the computations. Monte Carlo simulation is used to evaluate the approach. In all, 70 test problems comprising 20 to 60 nodes are randomly generated and analyzed. The results indicate that the heuristic produces significant computational saving as the size of the network grows, and that the quality of the reduced network solutions are better than those obtained from the original formulation.

Keywords: stochastic networks; shortest path problems; Monte Carlo simulation; utility theory (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.37.2.198 (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:37:y:1991:i:2:p:198-215

Access Statistics for this article

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