Path Preferences and Optimal Paths in Probabilistic Networks

Abstract

The classical shortest route problem in networks assumes deterministic link weights, and route evaluation by a utility (or cost) function that is linear over path weights. When the environment is stochastic and the “traveler’s” utility function for travel attributes is nonlinear, we define “optimal paths” that maximize the expected utility. In this setting, the concept of temporary and permanent preferences for route choices is introduced. It is shown that when the utility function is linear or exponential (constant risk averseness), permanent preferences prevail and an efficient Dijkstra-type algorithm can be used.