Early Concept Grant for Exploratory Research ( EAGER ) Dynamic Traffic Equilibrium Problems: Distributed Algorithms and Error Analysis

点击翻译按钮获取中文摘要

This award is funded under the American Recovery and Reinvestment Act of 2009. Increasing levels of congestion in urban traffic networks have significant economic and environmental impact. Supported by dramatic increases in sensing and communication ability, there is a renewed emphasis on developing intelligent transportation systems. This grant concentrates on developing exact and approximate algorithms for the dynamic traffic assignment problems, for purposes of online deployment and offline design. Our objective is to study the corresponding variational inequality problems and their stochastic generalizations via decomposition methods and distributed schemes. We propose to develop two classes of schemes, namely, projection-based schemes and splitting-based schemes, with an emphasis on developing convergence theory and providing error estimates. We also propose to consider the design of mechanisms that minimize the price of anarchy via the solution of large-scale mathematical programs with equilibrium constraints, with an emphasis on (1) obtaining bounds via nonconvex duality and (2) the development of scalable decomposition schemes.The intellectual merit of this work lies in the construction of limited coordination low-complexity distributed for solving the dynamic traffic equilibrium problem. The proposed schemes are expected to be either provably convergent or have well-defined error bounds. More generally, the work will add to the realm of approximate schemes developed for convex optimization problems and will have applicability for obtaining approximate equilibria in a host of settings. From an application standpoint, the work is motivated by the need to create more efficient transportation systems. Specifically, these schemes can be deployed in online settings, and are capable of functioning under limited information and coordination requirements. We expect that our scalable offline design algorithms will aid in the very design of such systems.