Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/288335 
Erscheinungsjahr: 
2020
Quellenangabe: 
[Journal:] Mathematical Methods of Operations Research [ISSN:] 1432-5217 [Volume:] 93 [Issue:] 1 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2020 [Pages:] 153-178
Verlag: 
Springer, Berlin, Heidelberg
Zusammenfassung: 
Stochastic shortest path problems (SSPPs) have many applications in practice and are subject of ongoing research for many years. This paper considers a variant of SSPPs where times or costs to pass an edge in a graph are, possibly correlated, random variables. There are two general goals one can aim for, the minimization of the expected costs to reach the destination or the maximization of the probability to reach the destination within a given budget. Often one is interested in policies that build a compromise between different goals which results in multi-objective problems. In this paper, an algorithm to compute the convex hull of Pareto optimal policies that consider expected costs and probabilities of falling below given budgets is developed. The approach uses the recently published class of PH-graphs that allow one to map SSPPs, even with generally distributed and correlated costs associated to edges, on Markov decision processes (MDPs) and apply the available techniques for MDPs to compute optimal policies.
Schlagwörter: 
Stochastic shortest path problems
Markov decision processes
Phase type distributions
PH graphs
Multicriteria optimization
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.