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

该奖项是根据2009年美国复苏和再投资法案资助的。城市交通网络日益拥堵的程度对经济和环境产生了重大影响。在传感和通讯能力急剧提高的支持下，人们重新强调发展智能运输系统。这项拨款的重点是为动态交通分配问题开发精确和近似的算法，用于在线部署和离线设计。我们的目的是研究相应的变分不等式问题及其随机推广，通过分解方法和分布方案。我们建议发展两类方案，即基于投影的方案和基于分裂的方案，重点是发展收敛理论和提供误差估计。我们还建议考虑通过具有平衡约束的大规模数学规划的解来最小化无政府状态代价的机制设计，重点是(1)通过非凸对偶获得边界和(2)可扩展分解方案的发展。本文的智力优势在于构建了求解动态交通均衡问题的有限协调低复杂度分布式算法。所提出的方案要么是可证明收敛的，要么是具有良好定义的误差范围的。更一般地说，这项工作将增加为凸优化问题开发的近似方案的领域，并将适用于在许多设置中获得近似平衡点。从应用的角度来看，这项工作的动机是需要创造更有效的运输系统。具体来说，这些计划可以在联机环境中部署，并且能够在有限的信息和协调要求下发挥作用。我们期望我们的可扩展离线设计算法将有助于这种系统的设计。

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.