Dynamic shortest path in stochastic dynamic networks: ship routing problem

Dynamic shortest path in stochastic dynamic networks: ship routing problem

0.00 Avg rating0 Votes
Article ID: iaor20042265
Country: Netherlands
Volume: 144
Issue: 1
Start Page Number: 138
End Page Number: 156
Publication Date: Jan 2003
Journal: European Journal of Operational Research
Authors: ,
Keywords: markov processes, programming: probabilistic
Abstract:

In this paper, we apply the stochastic dynamic programming to find the dynamic shortest path from the source node to the sink node in stochastic dynamic networks, in which the arc lengths are independent random variables with exponential distributions. In each node there is an environmental variable, which evolves in accordance with a continuous time Markov process. The parameter of the exponential distribution of the transition time of each arc is also a function of the state of the environmental variable of its initiative node. Upon arriving at each node, we can move toward the sink node through the best outgoing arc or wait. At the beginning, it is assumed that upon arriving at each node, we know the state of its environmental variable and also the states of the environmental variables of its adjacent nodes. Then we extend this assumption such that upon arriving at each node, we know the states of the environmental variables of all nodes. In the ship routing problem, on which we focus in this paper, the environmental variables of all nodes are known, but it is shown that the complexity of the algorithm becomes exponential in this case.

Reviews

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