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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI