𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Iterative methods for dynamic stochastic shortest path problems

✍ Scribed by Raymond K. Cheung

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
147 KB
Volume
45
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

State space partitioning methods for sto
State space partitioning methods for stochastic shortest path problems
✍ Alexopoulos, Christos πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 150 KB πŸ‘ 2 views

This paper describes methods for computing measures related to shortest paths in networks with discrete random arc lengths. These measures include the probability that there exists a path with length not exceeding a specified value and the probability that a given path is shortest. The proposed meth

Dual algorithms for the shortest path tr
Dual algorithms for the shortest path tree problem
✍ Pallottino, Stefano; ScutellοΏ½, Maria Grazia πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 117 KB πŸ‘ 2 views

We consider dual approaches for the Shortest Path Tree problem. After a brief introduction to the problem, we review the most important dual algorithms which have been described in the literature for its solution and propose a new family of dual ascent algorithms. In these algorithms, ''local'' and

A dynamic programming algorithm for the
A dynamic programming algorithm for the shortest path problem with time windows and linear node costs
✍ Ioachim, Irina; GοΏ½linas, Sylvie; Soumis, FranοΏ½ois; Desrosiers, Jacques πŸ“‚ Article πŸ“… 1998 πŸ› John Wiley and Sons 🌐 English βš– 154 KB πŸ‘ 2 views

This paper presents an optimal dynamic programming algorithm, the first such algorithm in the literature to solve the shortest path problem with time windows and additional linear costs on the node service start times. To optimally solve this problem, we propose a new dynamic programming algorithm w

An improved iterative method for large s
An improved iterative method for large strain viscoplastic problems
✍ H.-L. Cao; M. Potier-Ferry πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 167 KB πŸ‘ 1 views

In this work, some techniques are proposed to improve the usual Newton-Raphson Method (NRM) used in the numerical analysis of large strain viscoplastic problems. These techniques, based on the ΓΏrst-order perturbation technique, allow to deΓΏne an adaptive step strategy and to improve the trial soluti

Dynamic analysis methods for the year 20
Dynamic analysis methods for the year 2000 problem
✍ Wilde, Norman; Justice, Randy; Blackwell, Kristin; Wong, W. Eric πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 175 KB πŸ‘ 1 views

Programmers working on the year 2000 problem need to locate and understand date sensitive code, that is, code whose execution depends on date inputs. This paper presents several dynamic analysis methods for addressing this problem. Date sensitive code can be located by running many test cases that a