基于宏观交通理论的交通控制子区划分方法.doc

基于宏观交通理论的交通控制子区划分方法基金项目：国家高技术研究发展计划（863计划），2011AA110305李刚奇 赵娅丽（同济大学交通运输工程学院，上海 201804）摘 要：目前国内的基于控制的子区划分方法主要依据交叉口的关联度，将交叉口集聚进行统一控制，本文提出了一种基于路段交通流密度的城市子区划分方法，以路网路段为对象，从宏观层面探讨城市控制子区的划分，将图像划分的方法应用于城市路网划分，并提出了划分标准对子区划分进行控制。本文从路网整体角度出发，对城市路网拓扑结构及路段相似性进行了建模，采用VISSIM仿真数据进行了方法实验并得出了结论。关键词：子区划分；宏观基本曲线图；Normalized Cuts；自动划分Urban Traffic Signal Control Network Partitioning Based on Macro-Traffic Flow TheoryGangqi Li Yali Zhao（School of TransportationEngineering, Tonji University,Shanghai 201804）Abstract: The correlation of each intersection is usually used to partitioning the network in the field of network partitioning, The density of each link is adopted to partitioning the network into subdivision from a macro point of view in this paper. A image division method is applied to the division of the urban network partitioning, a metric is proposed to estimate the optimal number of subdivisions and evaluate a given partitioning. From a point of the whole network, the topology of the network and the similarity of each link has been modeled, at last, the data from VISSIM simulation is used to partitioning the network.Keywords: Network Partitioning, Macroscopic Fundamental Diagram(MFD), Normalized Cuts, Auto Subdivision1 引言目前国内关于控制子区划分的方法基本上都是基于交叉口关联度，并考虑网路空间特性，从把单个交叉口集合的角度来划分控制子区，最后的划分结果会打断路段，造成路段的不连续性，一定程度上其应用带来不方便，基于此本文提出了一种基于路段的城市子区划分方法，从整条路段的交通流参数出发，对城市路网进行划分。Nikolas Geroliminis和Carlos F. Daganzo1通过对日本横滨城市道路（10km2）的交通数据（其数据来源为研究区的500个线圈数据和140辆配有GPS的出租车）研究首先在实际中揭示了对于城市规模的路网，其平均流量、密度和速度存在着类似单个路段流密速关系图的宏观曲线图，称为macroscopic fundamental diagram (MFD)。文献2显示了一定区域内的车辆数(accumulation)与该区域流出量(trip completion)有很强的线性关系，文中将这样的区域称为“neighborhood”，这就使在宏观层面对进出“neighborhood”的流量控制有了依据，使得缓解交通拥堵，甚至快速疏散拥堵成为可能。Nikolas Geroliminis在文献3的研究表明密度是影响MFD离散程度及曲线形状的一个很重要的因素，考虑到MFD的可能的应用性，本文提出了一种简单易行的一种宏观层面的子区划分方法。2 Normalized CutsNormalized Cuts是一种图像划分方法，此方法是种宏观层次的方法，着眼点不在于细节，从图像的整体感觉出发，可以将其比喻为：一个画家作画时，总是先勾勒出画的轮廓，然后才会填充细节，具有一定的感知性。城市路网亦有这样的特性且有自己的空间特性，并考虑到路网上交通流的密度，本文将会把城市路网划分为密度相近的区域，使其尽可能的具有良好的MFD特性。一个带权重的无向图G=(V,E)中，V为节点，E为节点间连线，代表节点u，v之间的相似性，我们的划分目标为把V划分为不同的V1，V2Vm，其中Vi中的相似度较高，Vi，Vj间的相似度较低。假定集合V可以划分为两部分A和B，A和B之间的相似度可以定义为。最优的划分结果为最小的Cut(A,B)值，此时表明同一子区内的路段的相似度最高，然而由于本方法在进行划分时，容易划分出孤立的单独的节点，如图1中的n1和n2，最好的划分结果应沿着图1中间的虚线进行划分4。图1 产生的偏差划分和正确划分为了避免此结果，将子区划分的目标表示为：（1）将相似度高的节点放在同一个子区内（2）不同子区内的节点的相似度应该尽量小为此本文引入了子区间的相异度和子区内的相似度，将分别其定义为： （1） （2）通过以上的两个划分标准，可以避免划分出孤立的单独路段，容易证明：本文提出的两个划分目标是一致的。 （3）基于此本文提出的划分目标的数学模型可以表示为： s.t. （4）求解此Ncut的最小值是一个NP难题，尤其是在处理路网较大的情况下，然而一些近似的解法可以求得满足精度的结果，谱方法是一种应用较广的方法，通过求解特征值及特征值向量，可以近似解决NP问题。3 谱方法的应用无向图G=(V,E)的邻接矩阵为H，H中的元素aij为1，当V中i与j相连时，即i与j有同一个边；aij为0，当i与j不相连时，即i与j没有同一边连接。顶点间的相似性可以表示为： （5）式中di代表路段i的交通密度5，在应用模型时，本文采用路段作为无向图G中的节点V，令。则minNcut可以通过以下公式求得：s.t. （6）其中，D为对角阵，对角线元素，图的Laplace矩阵即为D-W，由于Laplace矩阵中所有的行和列和都为0，因此该矩阵总有一个特征值为0，如果图G是连通的，那么第二小特征值为正数，且对应的特征向量称为Fiedler向量，包含图的重要信息，也就是说Fiedler向量中各元素的数值大小反应了其对应顶点的相互关系。具体的方法的实现步骤可以概括为：（1）建立路网的拓扑结构图，并标定节点间的权重（2）建立对应图的Laplace矩阵，求解获得Fiedler向量（3）依据Fiedler向量对图进行划分（4）返回步骤（1）直至满足划分要求依据Fiedler向量进行路网划分时，可以依据不同的临界值S将Fiedler向量对应的顶点进行划分，在选择S值时常有以下方法6：（1）平分法：将Fieder向量中的值从小到大排列，取位于中间的的元素进行划分（2）0分法：由于Fieder向量中的元素和为0，可以依据正负数进行划分（3）元素间隔分法：将Fiedler向量排序，并计算相邻元素的间隔，选取间隔最大的两个元素进行划分（4）搜索法：搜索Fiedler中的向量，确定划分点，使划分结果拥有最小的Ncut值各个划分方法中，平分法和元素间隔法不能保证每次划分的自取是连通的，0分法简单实用，搜索法计算量较大，需要遍历点。4 划分标准为了确定划分的子区数及评价划分出的子区，本文引入了一个评价指标，为： （7）式中，NA表示为子区A中所有的路段由于公式（7）中只包含了交通流数据，并不包括路网的空间结构信息，为了评价子区A是否为很好的划分结果，采用公式（8）对其进行评价 （8）式中，K表示为与子区A相邻接的子区。最后的划分结果将由公式（9）进行评价，其表示为所有划分的子区的平均值 （9）式中，k为划分出的子区数，C为划分的子区集合。NS评价标准也可以以路段密度的方差和均值来表达： （10）式中Var(A)，uA分别为子区A中路段的方差和均值，同样的可以得到： （11）由公式（11）知道，当均值差很大，方差很小时，说明子区A划分结果很好，一般情况下如果子区A的方差很小，可知子区A的划分结果很好，此时由可知，NS(A)1。如果A的方差很大，表明子区A需要继续划分，除非邻接子区B和A的均值差非常大，此时应有。如果大部分子区都有较小的方差和NS值，但是有个别的子区有较大的方差和NS值时，本文认为这种划分结果仍是有效的。5 案例分析为了验证方法的有效性，本文采用北京奥林匹克公园周边的路网进行了子区划分实验。其路网拓扑图如图所示，该路网包含36个交叉口，连接路段数为58条，数据由VISSIM仿真获得，路段密度采集间隔为5min，其VISSIM仿真路网如图2所示，考虑道路性质将其抽象为图3所示的拓扑结构图。 图2 VSSIM仿真路网 图3 路网拓扑结构图表1表明了不同划分子区数的NS值，本文对路网进行了5次划分，其划分结果如图4所示，由NS可知最好的划分结果为四子区数，可以最为最后的划分推荐方案。表1 不同子区数NS值子区数k23456NSk0.92291.12040.87210.92281.1409图4 划分结果6 结语本文从宏观路网的角度出发对城市路网进行了控制子区的划分，划分方法以路段为对象，将图像划分的方法应用于交通控制子区的划分，并考虑城市路网的空间结构，以路网对应的Laplace矩阵的特性向量Fiedler向量作为划分依据，实现了子区的自动划分，与传统的以交叉口为对象不同的是，划分结果并未打断路段，划分的结果在空间上连通集聚，便于施行交通控制，划分出的子区内部交通密度相近，可以近似认为子区内部为同质的交通流，考虑到MFD曲线的特性，本文的划分结果一定程度上可以为拥堵疏散提供控制策略。参考文献1Nikolas Geroliminis and Carlos F. Daganzo. Existence of urban-scale macroscopic fundamental diagrams: Some experimental findings. Transportation Research Part B 42 (2008) 759-770.2Nikolas Geroliminis and Jie Sun. Properties of a well-defined macroscopic fundamental diagram or urban traffic. Transportation Research Part B 45 (2011) 605-617.3Christine Buisson and Cyril Ladier. Exploring the Impact of the Homogeneity of Traffic Measurementson the Existence of Macroscopic Fundamental Diagrams. 88th Annual Meeting Transportation Research Board Washington, D.C. January 2009.4Shi, J. and J. Malik. Normalized cuts and image segmentation. Transactions on Pattern Analysis and Machine Intelligence, 22(8), 2000, 888-905.5Y