Congested Network Flow Models and Algorithms

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

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.