Routing problems and Markovian decision processes (Q761359): Difference between revisions

The problem of finding a routing problem through a network has been solved by dynamic programming [see \textit{R. Bellman}, ''Introduction to the mathematical theory of control processes, Vol. II'' (1971; Zbl 0214.145) and \textit{R. Bellman} and \textit{S. E. Dreyfus}, ''Applied dynamic programming'' (1962; Zbl 0106.349)]. A stochastic view of the routing problem for finding the maximum reliability has been studied by \textit{M. Roosta} [J. Math. Anal. Appl. 88, 341-347 (1982; Zbl 0491.90087)]. A different version of the problem is now introduced, where at each city there is a transition probability \(p_{ij}\) of going from city i to city j. The expected time of going from city i to N (end of destination) is then calculated. If, however, at each city there is a choice of policies (one might decide to travel from city i to city j by a different method of transport) then a new Markovian decision process is formulated. The method is easily extended for finding the maximum reliability from city i to city N using an optimal policy.