Iterative methods for dynamic stochastic shortest path problems

Raymond K. Cheung

Naval Research Logistics (NRL), 1998, vol. 45, issue 8, 769-789

Abstract: We consider a routing policy that forms a dynamic shortest path in a network with independent, positive and discrete random arc costs. When visiting a node in the network, the costs for the arcs going out of this node are realized, and then the policy will determine which node to visit next with the objective of minimizing the expected cost from the current node to the destination node. This paper proposes an approach, which mimics the classical label‐correcting approach, to compute the expected path cost. First, we develop a sequential implementation of this approach and establish some properties about the implementation. Next, we develop stochastic versions of some well‐known label‐correcting methods, including the first‐in‐first‐out method, the two‐queue method, the threshold algorithms, and the small‐label‐first principle. We perform numerical experiments to evaluate these methods and observe that fast methods for deterministic networks can become very slow for stochastic networks. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 769–789, 1998

Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1002/(SICI)1520-6750(199812)45:83.0.CO;2-#

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:wly:navres:v:45:y:1998:i:8:p:769-789

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().