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

探索性研究早期概念资助 (EAGER) 动态流量均衡问题：分布式算法和误差分析

• 批准号: 0948905
• 负责人: Angelia Nedich
• 金额: $ 20万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2012-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0948905&HistoricalAwards=false
• 关键词: Early; Concept; Grant; Exploratory; Research

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.

该奖项由2009年美国复苏和再投资法案资助。城市交通网络中日益严重的拥堵对经济和环境产生了重大影响。在传感和通信能力大幅提高的支持下，人们重新强调开发智能交通系统。该基金主要用于开发动态交通分配问题的精确和近似算法，用于在线部署和离线设计。我们的目标是研究相应的变分不等式问题及其随机推广通过分解方法和分布式计划。我们建议开发两类计划，即基于投影的计划和分裂的计划，重点发展收敛理论和提供误差估计。我们还建议考虑设计的机制，最大限度地减少无政府状态的代价，通过解决大规模的数学规划与平衡约束，重点是（1）通过非凸对偶获得边界和（2）可扩展的分解schemes.The智力价值这项工作的建设有限的协调低复杂性分布式解决动态交通平衡问题。所提出的计划预计是可证明收敛或有明确的误差界。更一般地说，这项工作将添加到领域的近似计划开发的凸优化问题，并将有适用性获得近似平衡在主机的设置。从应用的角度来看，这项工作的动机是需要创造更有效的运输系统。具体而言，这些计划可以部署在在线环境中，并能够在有限的信息和协调要求下发挥作用。我们希望我们的可扩展离线设计算法将有助于这种系统的设计。