SWUTC Research Project Description
Game-Theoretic Analysis of Dynamic Traffic Equilibria
University: University of Texas at Austin
Principal Investigator:
Stephen Boyles
Department of Civil and Environmental Engineering
(512) 471-3548
Project Monitor:
Avinash Unnikrishnan
Department of Civil and Environmental Engineering
West Virginia University
Funding Source: USDOT and State of Texas General Revenue Funds
Total Study Cost: $75,900
Project Number: 600451-00079
Date Started: 1/1/13
Estimated Completion Date: 12/31/13
Project Summary
Project Abstract:
The concept of equilibrium underlies all traffic assignment, and is intended to reflect drivers’ route choice behavior. In static assignment, there is always a unique equilibrium in link volumes. In dynamic traffic assignment (DTA), however, there may be more than one equilibrium (or, in some formulations of DTA, none at all). This raises important questions about how results from DTA software should be interpreted in the planning process. While addressing these questions may seem challenging from the standpoint of transportation engineering, economists have faced the same questions for decades, and the field of game theory has developed a rich set of tools to address situations exactly like this one. This project aims to use this knowledge to inform transportation planning as appropriate.
Project Objectives:
The research has three primary objectives, in response to the research needs raised in Sections A and B. The work plan in Section D explains the specific steps which will be taken to accomplish these objectives.
- Determine the extent to which these problems occur in realistic transportation networks.
- Apply game-theoretic analysis to the dynamic equilibrium problem.
- Provide guidance to planners on how the results from DTA software should be used in light of our discoveries.
Task Descriptions:
Task 1: Literature review on dynamic traffic assignment and game theory
A thorough survey of the dynamic traffic assignment and game theory research literature will be undertaken, looking for opportunities for applying results or techniques from the latter area to the former. In particular, this review will identify and explore opportunities for extending techniques applied to the static traffic assignment problem to dynamic traffic assignment as well.
Task 2: Assemble testbed suite including networks of varying sizes and topologies
To perform the remainder of the analysis, the research team will identify a set of networks in which equilibrium properties can be explored in detail. To the extent possible, these networks will be based on real cities and demand patterns, keeping in mind the computational power required to perform detailed equilibrium analysis.
Task 3: Explore prevalence and implications of equilibrium nonexistence and nonuniqueness
While problematic issues have been identified in small networks, it remains to be seen whether these effects also manifest in realistic networks, and if so, the extent to which they affect the practical interpretation of dynamic traffic assignment solutions. This task thus addresses the first study objective, and will involve comprehensive analysis of the solutions to dynamic traffic assignment models on the testbed networks at varying levels of precision.
Task 4: Apply game theoretic techniques to dynamic traffic equilibria
This task builds directly on current SWUTC research performed by Dr. Boyles applying game-theoretic techniques to static traffic equilibrium, extending this analysis to dynamic traffic assignment in the context established by the previous three tasks. The researchers will explore tractable game-theoretic formulations of dynamic traffic equilibrium, apply concepts of equilibrium refinements to address multiple equilibria, and explore the value of computational game theory in finding solutions.
Task 5: Develop practical strategies for addressing nonuniqueness
The analysis from the previous four tasks will culminate in the development of a variety of remedies for the issue of multiple equilibria, including strategies such as equilibrium refinements, planning for multiple scenarios, or modifications to flow models which avoid or minimize the prevalence of multiple equilibrium solutions.
Task 6: Author final report
A comprehensive final report will be written, describing all research work performed.
Implementation of Research Outcomes:
Dynamic Traffic Assignment models are used to estimate how many travelers use a roadway link at different times of the day. They are based on an equilibrium principle according to which no traveler between an origin-destination pair can do better by switching to an alternate route. This research focuses on issues related to multiple equilibria in such models. Researchers first point out the existence of multiple equilibria in dynamic networks and discuss its implications on project selection. Then they discuss how some of the simplified traffic flow models that are used in various DTA software packages can lead to counter-intuitive phenomena in which all feasible flow patterns are at equilibrium, while in practice only one of them is likely to be observed. Modifications to the traffic flow models are proposed to mitigate this phenomenon.
Products developed by this research:
New Models Developed: This research resulted in new models that can be integrated into existing software for Dynamic Traffic Assignment.
New Technique: A new technique to address the problem of multiple equilibrium solutions that may arise in current DTA software packages has been proposed.
Curriculum Developed: Research findings have been incorporated into a graduate course on Dynamic Traffic Assignment (CE392D) at the University of Texas at Austin.
Presentation: Diverge Models and Dynamic Traffic Equilibria. Boyles, S. D., J. Duthie, T. Rambha, and C. Melson, presented at the Annual Meeting of the Institute for Operations Research and Management Sciences, Minneapolis, MN, October 6-9, 2013.
Presentation: Game-Theoretic Learning Models in Traffic Assignment, Rambha, T., S. D. Boyles, and K. Yin, presented at the Annual Meeting of the Institute for Operations Research and Management Sciences, Minneapolis, MN, October 6-9, 2013.
Journal Article in Preparation: Diverge Models and Dynamic Traffic Equilibria, Boyles, S. D., J. Duthie, T. Rambha, and C. Melson, in preparation for submission to Networks and Spatial Economics (2014).
Impacts/Benefits of Implementation:
This research has direct implications on policy making in transportation as all planning models use traffic assignment to evaluate the impacts of improvement strategies on congestion. However, when multiple equilibria exist, it becomes difficult to make policy decisions as different results could favor the selection of different projects. While current modeling practices have been oblivious to the problem of multiple equilibria, we point out its occurrence and importance and propose ways to model it.
The research team had conversations with modelers at the Capital Area Metropolitan Planning Organization discussing the research results. While the research results have not yet been implemented these conversations have laid the ground for future research.
This research will also impact other disciplines in that the problem is similar in many ways to routing in telecommunication networks and equilibrium in queuing systems, and hence may be applied in these areas too.
Web Links:
Final Report