Markov Chain Models for Stochastic Shortest Path Problem.

      Аннотация: The Markov stochastic process is used to model lots of optimization problems, especially in the network optimization problems. In the routing optimization problems there could be either continuous or discrete parameters in the networks. Suppose the length of an arc is defined as the time that takes to transmit flow between the pair linked nodes of the arc; then, in this situation the cost parameters of the network are continuous variables and it may be modeled by a continuous time Markov chain (CTMC) stochastic process. In other situation consider the topology of the network that shows the location of the nodes and their related linked arcs; so, a connecting path from a given source node to a given destination node may be modeled by a discrete time Markov chain (DTMC) stochastic process. Then, some stochastic routing models in the networks with an established Markov stochastic process are discussed. So, a new criterion will be presented for the probabilistic evaluation of the message transmission between two given nodes by time T, which is applicable for large size networks. Then, a genetic algorithm is performed to find the best established connection.

Ключевые слова: genetic algorithm, shortest path problem, stochastic network, Markov chain stochastic process