Stochastic graph models with phase type distributed edge weights

Abstract

Most stochastic shortest path problems include an assumption of independent weights at edges. For many practical problems, however, this assumption is often violated indicating an increased number of applications with stochastic graphs where edge weights follow a distribution that has a possible correlation with weights at adjacent edges. Real-world information in conjunction with existing dependencies in networks can significantly contribute to the computation of the optimal solution to stochastic shortest path problems. For example, the knowledge of a congestion arising on the current road results in a better traveler's choice of an alternative route. Markov dependability models describing the correlation in the length of availability and unavailability intervals of technical components could support optimal decisions to avoid high maintenance costs. In this thesis, an innovative model class for stochastic graphs with correlated weights at the edges is introduced. In the developed model edge weights are modeled by PH distributions and correlations between them can be encoded using transfer matrices for PH distributions of adjacent edge weights. Stochastic graph models including correlations are important to describe many practical situations where the knowledge about system parameters like traveling times and costs is incomplete or changes over time. Based on PH-Graphs efficient solution methods for Stochastic Shortest Path Problems with correlations can be developed. Competing paths from origin to destination in a PH-Graph can be interpreted as CTMDPs. Optimal solutions to different shortest path problems can be obtained from finding an optimal policy in a CTMDP. For example, the problem of finding the reliable shortest path to maximize the probability of arriving on time under realistic assumptions can be efficiently treated. Formulations of shortest path problems with correlations as well as solution methods from the CTMDP field are presented. We address the parameterization of PH-Graphs based on measured data from simulated systems. Fitting methods for parameterization of transfer matrices are adopted from MAP fitting approaches. Also similarity transformations for order 2 acyclic PHDs in composition are considered. Our experiments and examples show that correlation has a significant impact on shortest paths in stochastic weighted networks and that our solution methods are effective and usable in online decision senarios.