Routing problems and Markovian decision processes

DOI10.1016/0022-247X(85)90097-6MaRDI QIDQ761359zbMATH OpenFDO

Authors N. G. F. Sancho

Publication date 1985

Published in Journal of Mathematical Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-247X(85)90097-6

zbMATH Keywords

maximum reliabilitynetworkoptimal policystochastic direction choicestochastic routing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Markov and semi-Markov decision processes (90C40)

Review text

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.

Recommendations

• Optimal dynamic routing in Markov queueing networks
• Optimal routing for maximizing the travel time reliability
• Dynamic Shortest Paths in Acyclic Networks with Markovian Arc Costs
• Markovian assignment decision process
• Problem of optimal choice of a route under conditions of time discounting

Cites work

• scientific article; zbMATH DE number 3148886 (Why is no real title available?)
• scientific article; zbMATH DE number 3174053 (Why is no real title available?)
• scientific article; zbMATH DE number 3289006 (Why is no real title available?)
• Introduction to the mathematical theory of control processes. Vol. II:Nonlinear processes
• Routing through a network with maximum reliability

Cited in

(5)

• Multiple objective (fuzzy) dynamic programming problems: a survey and some applications
• Stochastic shortest path problems with associative accumulative criteria
• A MDP approach to fault-tolerant routing
• A Markov Decision Model and Decomposition Heuristic for Dynamic Vehicle Dispatching
• Optimal routing for maximizing the travel time reliability

This page was built for publication: Routing problems and Markovian decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q761359)