Iterative methods for dynamic stochastic shortest path problems

Iterative methods for dynamic stochastic shortest path problems

0.00 Avg rating0 Votes
Article ID: iaor19992552
Country: United States
Volume: 45
Issue: 8
Start Page Number: 769
End Page Number: 789
Publication Date: Dec 1998
Journal: Naval Research Logistics
Authors:
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.

Reviews

Required fields are marked *. Your email address will not be published.