Nicolás Stier-Moses

A Mean-Risk Model for the Stochastic Traffic Assignment Problem

Coauthor(s): Evdokia Nikolova.


Adobe Acrobat PDF

We embark on an agenda to investigate how stochastic travel times and risk aversion transform the traditional traffic assignment problem and its corresponding equilibrium concepts. Moving from deterministic to stochastic travel times with risk-averse users introduces non-convexities that make the problem more difficult to analyze. For example, even computing a best response of a user to the environment is still of unknown complexity [50, 48]. This paper focuses on equilibrium existence and characterization in the different settings of infinitesimal (non-atomic) vs. atomic users and fixed (exogenous) vs. congestion-dependent (endogenous) variability of travel times. We show that equilibria always exist in three out of the four possible combinations. The exception is the case of atomic users and endogenous variability. Because cost functions are non-additive (i.e., the cost along a path is not a sum of costs over edges of the path as it is assumed in the vast majority of network routing problems), solutions need to be represented as path flows since not all decompositions from edge to path-flows are equivalent. Nevertheless, we show that succinct representations of equilibria and optimal solutions always exist. Finally, we investigate the inefficiencies resulting from the stochastic nature of travel times. We obtain that under exogenous variability of travel times, the worst-case inefficiency of equilibria is exactly the same as when travel time functions are deterministic, meaning that in this case risk-aversion under stochastic travel times does not further degrade a system in the worst-case in relation to users' self-mindedness.

Source: Decision, Risk & Operations Working Papers Series
Exact Citation:
Nikolova, Evdokia, and Nicolás Stier-Moses. "A Mean-Risk Model for the Stochastic Traffic Assignment Problem." Decision, Risk & Operations Working Papers Series, Columbia Business School, 2011.
Date: 12 2011