A Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel Times

E. Nikolova () and N. E. Stier-Moses ()
Additional contact information
E. Nikolova: Department of Electrical and Computer Engineering, University of Texas at Austin, Austin, Texas 78712; and Department of Computer Science and Engineering, Texas A&M University, College Station, Texas 77843
N. E. Stier-Moses: Graduate School of Business, Columbia University, New York, New York 10027; and School of Business, Universidad Torcuato Di Tella and CONICET, Buenos Aires C1428B1J, Argentina

Operations Research, 2014, vol. 62, issue 2, 366-382

Abstract: Heavy and uncertain traffic conditions exacerbate the commuting experience of millions of people across the globe. When planning important trips, commuters typically add an extra buffer to the expected trip duration to ensure on-time arrival. Motivated by this, we propose a new traffic assignment model that takes into account the stochastic nature of travel times. Our model extends the traditional model of Wardrop competition when uncertainty is present in the network. The focus is on strategic risk-averse users who capture the trade-off between travel times and their variability in a mean-standard deviation objective, defined as the mean travel time plus a risk-aversion factor times the standard deviation of travel time along a path. We consider both infinitesimal users, leading to a nonatomic game, and atomic users, leading to a discrete finite game. We establish conditions that characterize an equilibrium traffic assignment and find when it exists. The main challenge is posed by the users' risk aversion, since the mean-standard deviation objective is nonconvex and nonseparable, meaning that a path cannot be split as a sum of edge costs. As a result, even an individual user's subproblem---a stochastic shortest path problem---is a nonconvex optimization problem for which no polynomial time algorithms are known. In turn, the mathematical structure of the traffic assignment model with stochastic travel times is fundamentally different from the deterministic counterpart. In particular, an equilibrium characterization requires exponentially many variables, one for each path in the network, since an edge flow has multiple possible path-flow decompositions that are not equivalent. Because of this, characterizing the equilibrium and the socially optimal assignment, which minimizes the total user cost, is more challenging than in the traditional deterministic setting. Nevertheless, we prove that both can be encoded by a representation with just polynomially many paths. Finally, under the assumption that the standard deviations of travel times are independent from edge loads, we show that the worst-case ratio between the social cost of an equilibrium and that of an optimal solution is not higher than the analogous ratio in the deterministic setting. In other words, uncertainty does not further degrade the system performance in addition to strategic user behavior alone.

Keywords: congestion game; stochastic networks; mean-stdev Wardrop equilibrium; Nash equilibrium; risk aversion; nonadditive traffic assignment problem (search for similar items in EconPapers)
Date: 2014
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2013.1246 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:62:y:2014:i:2:p:366-382

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().