Dynamic shortest path in stochastic dynamic networks: Ship routing problem

Dynamic shortest path in stochastic dynamic networks: Ship routing problem

Authors: Azaron, A.; Kianfar, F.

European Journal of Operational Research - 2003 Volume 144, Pages 138-156

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, 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. © 2002 Elsevier Science B.V. All rights reserved.

https://doi.org/10.1016/S0377-2217(01)00385-X

Cite as:

@article{Azaron_2003,
	doi = {10.1016/s0377-2217(01)00385-x},
	url = {https://doi.org/10.1016%2Fs0377-2217%2801%2900385-x},
	year = 2003,
	month = {jan},
	publisher = {Elsevier {BV}},
	volume = {144},
	number = {1},
	pages = {138--156},
	author = {Amir Azaron and Farhad Kianfar},
	title = {Dynamic shortest path in stochastic dynamic networks: Ship routing problem},
	journal = {European Journal of Operational Research}
}



    Leave a Reply

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

    x
    This site uses cookies to make navigation simple and efficient. By continuing you declare that you want to automatically accept the privacy policy. More. Close