基于含权Newman算法的交通控制子区划分
Traffic Control Subarea Partition Based on Weighted Newman Algorithms

DOI: 10.12677/OJTT.2019.82018, PP. 145-154

Keywords: 交通控制，控制子区，聚类算法，Newman网络划分算法，交通密度
Traffic Flow Control, Sub-Network for Flow Control, Cluster Algorithm, Newman Network Partition Algorithm, Traffic Density

Full-Text   Cite this paper   Add to My Lib

Abstract:

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

References

[1]	Walinchus, R.J. (1971) Real-Time Network Decomposition and Sub Network Interfacing. Highway Research Record, 7, 20-28.
[2]	Ji, Y. and Geroliminis, N. (2012) On the Spatial Partitioning of Urban Transportation Networks. Transportation Research Part B: Methodological, 16, 1639-1656. https://doi.org/10.1016/j.trb.2012.08.005
[3]	Ji, Y. and Geroliminis, N. (2011) Spatial and Temporal Analysis of Congestion in Urban Transportation Networks. Trans-portation Research Board Annual Meeting, 1791-1808.
[4]	李刚奇, 赵娅丽. 基于宏观交通理论的交通控制子区划分方法[C]//第七届中国智能交通年会. 第七届中国智能交通年会优秀论文集——智能交通技术. 北京: 中国智能交通协会, 2012: 31-38.
[5]	马莹莹, 杨晓光, 曾澄. 基于谱方法的城市交通信号控制网络小区划分方法[J]. 系统工程理论与实践, 2010, 30(12): 2290-2296.
[6]	卢守峰, 陶黎明, 江勇东. 考虑连接性的路网划分算法[J]. 交通运输系统工程与信息, 2018, 18(5): 95-102.
[7]	Dimitriou, L. and Nikolaou, P. (2017) Dynamic Partitioning of Urban Road Networks Haled on Their Topological Andoperational Characteristics. IEEE International Conference on MODELS and Technologies for Intelligent Transportation Systems, Naples, Italy, 26-28 June 2017, 457-462.
[8]	王晓轩. 基于聚类的城市交通路网分区和交通状态判别[D]: [硕士学位论文]. 北京: 北京交通大学, 2017.
[9]	Newman, M.E.J. and Girvan, M. (2004) Finding and Evaluating Community Structure in Networks. Physical Review E, 69, Article ID: 026113. https://doi.org/10.1103/PhysRevE.69.026113
[10]	Girvan, M. and Newman, M.E.J. (2002) Community Structure in Social and Biological Networks. Proceedings of the National Academy of Sciences of the United States of America, 99, 7821-7826. https://doi.org/10.1073/pnas.122653799
[11]	Ji, Y.X. and Geroliminis N. (2012) On the Spatial Partitioning of Urban Transportation Networks. Transportation Research Part B, 46, 1639-1656. https://doi.org/10.1016/j.trb.2012.08.005
[12]	Kernighan, B.W. and Lin, S. (1970) An Efficient Heuristic Procedure for Partitioning Graphs. The Bell System Technical Journal, 49, 291-307. https://doi.org/10.1002/j.1538-7305.1970.tb01770.x
[13]	Newman, M.E.J. (2004) Detecting Community Structure in Networks. European Physical Journal B, 38, 321-330. https://doi.org/10.1140/epjb/e2004-00124-y
[14]	刘澜, 卢维科, 胡国静, 等. 面向边界控制地路网小区划分[J]. 中国公路学报, 2018, 31(11): 187-196.

Full-Text