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; 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年的《美国复苏与再投资法》资助的。城市交通网络中的拥堵水平不断增加，具有重大的经济和环境影响。在感应和沟通能力的急剧增强的支持下，人们对发展智能运输系统有了新的重视。该赠款集中于为在线部署和离线设计的目的开发精确和近似算法。我们的目标是通过分解方法和分布式方案研究相应的变异不平等问题及其随机概括。我们建议开发两类方案，即基于投影的方案和基于分裂的方案，重点是开发收敛理论并提供误差估计。 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 问题。预计所提出的方案将被证明是收敛的或具有明确定义的误差范围。更一般而言，这项工作将增加用于凸优化问题的近似方案的领域，并具有适用于在许多设置中获得近似平衡的适用性。从应用程序的角度来看，这项工作是由于需要创建更有效的运输系统而激发的。具体而言，这些方案可以部署在在线设置中，并且能够在有限的信息和协调要求下运行。我们希望我们的可扩展离线设计算法将有助于此类系统的设计。