Premium
Iterative methods for dynamic stochastic shortest path problems
Author(s) -
Cheung Raymond K.
Publication year - 1998
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/(sici)1520-6750(199812)45:8<769::aid-nav2>3.0.co;2-#
Subject(s) - shortest path problem , k shortest path routing , mathematical optimization , constrained shortest path first , computer science , path (computing) , dynamic programming , mathematics , graph , theoretical computer science , programming language
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