Congested Network Flow Models and Algorithms

拥塞网络流量模型和算法

• 批准号: 9634849
• 负责人: Donald Hearn
• 金额: --
• 依托单位: University of Florida
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-10-01 至 1999-09-15
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9634849&HistoricalAwards=false
• 关键词: Congested; Network; Flow; Models; Algorithms

9634849 Hearn This project involves modeling and analysis of congested networks. Congested networks are encountered in a variety of scenarios, including vehicular traffic flow, routing of calls in telecommunications systems, natural gas distribution, water distribution. The research is concerned with two distinct problems: (1) optimal toll pricing in congested networks, and (2) determination of flows in bounded congested network flow models. The investigators will develop algorithms to efficiently solve these problems and will carry out a large-scale numerical implementation of the approaches developed in the research. In the case of congestion toll pricing, these algorithms will be based on an existing two-stage approach for determining tolls known as MINSYS. New research will focus on efficient specialized methods to exploit the network structure of the problem, and extensions to the case where the system objective function is convex but each of the components of the cost map is concave. In the case of bounded networks, these algorithms will represent enhancements to the principal investigator's non-linear, multicommodity congestion network code, which uses the affine scaling with centering bundle method (ASCBM). In particular, the method will be extended to handle non-differentiable objective functions and ill-conditioned problems. Pricing of tolls on congested networks to guarantee that the "user" equilibrium is close to the "system" equilibrium is a problem faced by organizations as diverse as city traffic planners and telecommunications engineers. The theory and algorithms developed in this research have great promise to improve planning and decision-making functions in these networks. Moreover, the research should open up new avenues for the analysis of network flows in general.

9634849 Hearn这个项目涉及拥塞网络的建模和分析。拥挤的网络在各种情况下都会遇到，包括车辆交通流、电信系统中的呼叫路由、天然气分配、水分配。本文研究了两个不同的问题：(1)拥塞网络中最优收费，(2)有界拥塞网络流模型中流量的确定。研究人员将开发算法来有效地解决这些问题，并将对研究中开发的方法进行大规模的数值实施。在拥堵收费的情况下，这些算法将基于现有的两阶段方法来确定收费，即MINSYS。新的研究将集中于有效的专门方法来利用问题的网络结构，并扩展到系统目标函数是凸的，但成本图的每个组成部分都是凹的情况。在有界网络的情况下，这些算法将代表对主要研究者的非线性，多商品拥塞网络代码的增强，该代码使用仿射缩放与中心束方法（ASCBM）。特别地，将该方法推广到处理不可微目标函数和病态问题。在拥挤的网络上对通行费进行定价，以保证“用户”平衡接近“系统”平衡，这是城市交通规划者和电信工程师等各种组织面临的一个问题。本研究提出的理论和算法对改善这些网络的规划和决策功能有很大的希望。此外，该研究将为一般的网络流分析开辟新的途径。