基于含权Newman算法的交通控制子区划分

Traffic Control Subarea Partition Based on Weighted Newman Algorithms

摘要: 为使交通网络控制子区内的交通流具有更好的同质性，本文将道路网络中的路段抽象为点，相邻路段之间的连接关系抽象为边，形成一个对偶的网络拓扑结构图。以用户均衡交通分配得到的路段交通流数据除以路段长度计算得到路段的“拟交通密度”；通过引入路段拟交通密度，扩展了Newman子区划分算法。最后，选取实际路网、以NS_K (Normalized cut Silhouette)指标验证K均值聚类算法、传统Newman算法和扩展的Newman子区划分算法的优劣。研究发现：传统K均值聚类算法得到的各子区NS_K指标和路网NS_K指标都相对最小，但同一个子区内的路段在空间位置上不相连，没有实际运用价值；扩展的Newman子区划分算法的NS_K值优于传统Newman快速划分算法，证实引入了路段拟交通密度作为边权，使得划分出来的结果更加符合交通网络的特性。

Abstract: A dual network is structured firstly by setting link of road network as dual node and incidence relationship between links of road network as dual links in the dual network in order to keep homogeneity of traffic flow in each road sub-network partitioned. Link traffic flow, which is the result of traffic demand assignment based on user equilibrium principle, is divided by link length and then the definition of quasi traffic density of each link is proposed secondly. Newman network partition algorithm is extended by introducing the definition of quasi traffic density. Thirdly, the superiority of K-means cluster algorithm, Newman network partition algorithm and extended Newman network partition algorithm are identified by measurement of Normalized cut Silhouette (NS_K) on a real road network. This study has identified that: indexes value NS_K  and NS_K  on networks of traditional K-means cluster algorithm are relatively small, but the sub-network partitioned is not connected in the space so that it lacks practical value. Index  NS_K of extended Newman network partition algorithm is prior to that of Newman network partition algorithm. The sub-network which is partitioned by extended Newman network partition algorithm introduced the definition of quasi traffic density is favorable for purpose of traffic flow control.