Random variables as arc parameters when solving shortest path problems

Random graph theory was initially proposed by Paul Erdős and Alfred Rényi in the 1950s. A book of Béla Bollobás 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.