Random variables as arc parameters when solving shortest path problems

2020 
Abstract Random graph theory was initially proposed by Paul Erdős and Alfred Renyi in the 1950s. A book of Bela Bollobas presented the first systematic and extensive group of results of random graphs. Associating to each edge of a random graph a real random variable, we obtain a probabilistic network. The determination of an optimal path between two nodes in a probabilistic network has first been studied by H. Frank in 1969. Since then few theoretical results have been found, even though there is a recognizable applicability of this type of networks to real problems, namely, social and telecommunication networks. The mathematical model proposed in this chapter maximizes the expected value of a utility function over a directed random network, where the costs related to the arcs are real random variables following Gaussian distributions. We consider the linear, quadratic, and exponential utility functions, presenting a theoretical formulation based on multicriterion models, as well as the resulting algorithms that may be applied to real-life problems. In the last section an application to a real problem that was developed to solve a criminality problem in the city of Lisbon is discussed. Due to its complexity these types of applications are suggested to use as project-based learning and not as an easy applied exercise to solve within a limited time.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    0
    References
    0
    Citations
    NaN
    KQI
    []