李伟沙志仁戴秀斌谢海莹地质学报
（广东方纬科技有限公司，广东广州， 510006）
摘 要：本文提出基于宏观基本图的路网评价子区划分方法，把交通运行具有相似性的路段划分为同一个子区，便于掌握评价子区的交通运行特征。首先根据路段基本图获得每个路段的交通运行最大交通量，对相邻连通路段之间的交通运行相似性进行定义与计算，构建基于交通运行相似性的路网带权图；然后利用图论中的归一化割方法，对路网图进行子图划分，得到子区划分方案。最后在微观交通仿真平台上，通过对现实路网的交通运行历史数据进行模拟，对路网评价子区划分进行实证分析，应用于交通运行评价决策。
关键词：宏观基本图、子区划分、归一化割、交通运行评价、交通相似性
Method of Sub-region Division based on Macroscopic
Fundamental Diagram
LiWei Sha Zhiren Dai Xiubin Xie Haiying
(Guangdong Fundway Science and Techonology CO., Ltd., Guangzhou, Guangdong, China 510006)皮尔斯电子
Abstract: The MFD-based method of evaluation sub-area division is proposed. The network transforming is executed to let the weights of links be achieved. The similarity of connecting links is defined by the difference of each link’s maximum flow. The weights of the network diagram are determined by the links’ similarity. According to the Graph Theory, the sub-area division is achieved by the method of Normalized Cut. Spectral clustering algorithm is used to solve the optimization problem of Normalized Cut according to the Laplace matrix and the Fielder eigenvector. Then the evaluation method of the sub-area division is put forward. At last, the application is put forward in the downtown of Haizhu District, Guangzhou.
1 引言
城市路网交通运行评价的关键内容是评价子区的合理划分。路网中各条道路的静态基本属性与动态交通运行情况不尽相同，如车道数、通行能力、交通组织等均存在一定差异。若把整个路网不分区域进行评价，则不能突显及掌握部分区域的交通运行特征，如中心商业区、拥堵常发区等特征，更无法了解与认识城市不同区域或相邻区域间交通运行的异同点，从而将未能执行有效的区域交通协调联控。因此，需要根据每条道路的交通运行特性，对整个路网中的道路进行聚类，把交通运行特征相近的道路聚为一类，继而把路网划分为多个具有交通运行同质性（即交通运行特征相近）的评价子区，
分别对每一子区进行交通运行评价。根据交通运行评价结果，可在子区内外进行有针对性的交通管控，使得子区内部的交通运行保持在一个稳定的状态，子区之间的交通流顺畅稳定过渡，在一定程度上能缓解或减少交通拥堵的发生。
近几年，为了研究区域路网中交通需求与交通供给的关系，以便执行有效的交通管理与控制措施，Daganzo 等学者在宏观交通流理论的基础上，提出了宏观基本图（MFD ，Microscopic Fundamental Diagram ）理论[1-12]。Daganzo 等学者对日本横滨中心城区以及美国三藩市中央商务区（CBD ）进行了MFD 存在性的分析，对路网加权平均交通量、加权平均密度、加权平均速度的计算结果表明，在两个区域中均可到MFD 关系。Bussion C 等学者对交通测量同质性对宏观基本图存在性影响进行分析，并提出路网需要满足同质性要求，并指出具有交通运行同质性的路网，存在稳定的MFD 00。Geroliminis 等学者通过考察不同时刻内路网交通密度的分布，利用相邻路段的密度相似性对区域路网进行子区划分，并通过子区内及子区间各个路段交通密度的均值与方差定义了评价指标，评价不同子区数量下的划分效果，从而得出区域最佳子区数量[14-18]，并把划分结果应用作为控制子区的划分结果。
为把路网划分为若干个具有稳定MFD 的交通运行评价子区，本文将基于Geroliminis 等学者提出的子区划分方法进行改进与完善。以图论为基础，首先对相邻连通路段之间的交通运行相似度进行定义，计算相邻连通路段之间的交通运行相似度，使相邻连通路段之间的交通运行相似度能表达为路网图中
弧段的权重，建立路网带权图；然后，应用图论中子图划分方法中的归一化割方法，对路网进行评价子区划分。
2 基于交通运行相似度的路网带权图构建
生物陶粒2.1 交通运行相似度的定义
由MFD 的基本理论可得，具有交通运行同质性的路网，存在稳定的MFD 00。路网中各个路段的特征对MFD 曲线的影响较大即每个路段的交通特征对路网同质性的影响较大。交通特征主要包括：车道数、交通量、车流密度、拥堵分布等。
MFD 理论的出发点是研究路网中交通需求与交通供给的关系，最大交通量能直接反映每个路段及整体路网的交通供给量，而且交通量数据容易通过交通流检测而得到，因此本文主要以交通量作为路段的交通基本特征，利用路段的交通运行最大交通量来定义相邻连通路段之间的交通运行相似度。
令路网G 中相邻连通路段i 与j 之间的交通运行相似度为：
2(,)exp[()]m m i j w i j q q =-- （1） 其中，m i q 为路网G 中路段i 的交通运行最大交通量，m j q 为路网G 中路段j 的交通运行最大交通量。 利用自然常数变换，使相邻连通路段之间的交通运行最大交通量的差值平方映射到0-1的区间内，相似度为0则路段之间的交通运行最不相似，相似度为1则路段
之间的交通运行最相似。
路网带权图的构建
应用生态学报以图论为基础，首先对路网进行“结点-弧段变换”，使相邻路段之间的交通运行相似度表达为图中弧段的权重；然后基于交通运行相似度构建图的拉普拉斯矩阵，该矩阵为图论中进行子图分割的基础。具体如下。贵州财经学院学报
当路网G 中路段i 与路段j 有向连通时，H 中的元素1ij a =；当路段i 与路段j 不连通时，0ij a =；当i j =时，0ij a =。路网'G 的带权邻接矩阵为W ，W 中的元素为
'(,),10,0ij ij ij w i j a w a =⎧⎪=⎨=⎪⎩ （2）
矩阵D 为对角阵 {}i D diag d =
（3） '(,)i j
d w i j =∑ 式2-4
D W -即为路网'G 的拉普拉斯矩阵，矩阵中所有行和列之和均为零。通过上述变换与计算，便可得到以相邻连通路段之间的交通运行相似度为权重的路网带权图。
基于归一化割的路网子区划分方法
归一化割
城市路网亦有自己的宏观交通特性，其评价子区划分问题可转换为图的子图划分问题。采用归一化割方法对路网进行评价子区划分，则不会划分出于孤立路段，该划分从路网区域的整体运行状态出发，把路网划分为基本同质的子区，使其具有较为稳定的MFD 。
归一化割（NCut ，Normalized Cut ）[19-20]是图论中子图划分的方法之一，此方法是种宏观层面的子图划分方法，着眼点不在于图中的细节，从图的整体特征出发进行子图划分。图的最优归一化割问题可表述为：
min ()x Ncut x （4）
..s t
11i i i i v V
x if v A x if v B ∈=∈=-∈
其中，x 为由1与-1组成的列向量。若图中包含n 个结点，则x 中包含n 个元素。当第i 个i v 结点被划分在子区A 时，1i x =；当被划分在子区B 时，1i x =-。
求解归一化割的最小值是一个NP （Non-deterministic Polynomial ，非确定多项式）难题。然而一些近似的解法可以求得满足精度的结果，谱聚类方法是一种应用较广的方法，通过求解特征值及特征值向量，可以近似解决NP 问题0。
基于谱聚类的评价子区划分算法
谱聚类算法建立在图论中的谱图理论基础上，其本质是将聚类问题转化为图的最优划分问题。与传统的聚类算法相比，它具有能在任意形状的样本空间上聚类且收敛于全局最优解的优点。该算法首先根据给定的样本数据集定义一个描述相邻数据点相似度的邻接矩阵，并且计算矩阵的特征值和特征向量，然后选择合适的特征向量聚类不同的数据点0。
在上文中已通过计算相邻连通路段之间的交通运行相似度ij w ，构建了路网带权图的拉普拉斯矩阵 D W -。在本节将采用Fiedler 方法计算矩阵的特征值与特征向量，对路网评价子区进行划分。Fiedler 方法的主要思想是到图的拉普拉斯矩阵的第二小特征值，并把该特征值所对应的特征向量（称为Fiedler 向量）用于图的分割问题0。
根据Shi 与Malik 等人的研究，把图G 的点集合V 划分为两个子集A 与B 的最优化归一化割问题可通过变换得到其矩阵表达0： ()min ()min T T x y y D W y Ncut x y Dy
-= （5）
..s t
11{1,}
10i i i i i i T v V
x if v A
x if v B y b y D ∈=∈=-∈∈-=
其中，(1)(1)y x b x =+--，00i i i x i x d b d ><=∑∑
，i ij j d w =∑，其他定义同前。 当y 取实值时，可通过求解以下特征值方程得到T D W U U -=∧式34的最优解： ()D W y Dy λ-= （6）
对拉普拉斯矩阵D W -进行SVD 分解（Singular Value Decomposition ，奇异值分解）
，得到： T D W U U -=Λ （7） 其中，{}i diag λΛ=，i λ是矩阵D W -的奇异值（此处D W -为方阵，即i λ为D W -的特征值），()i U u =是正交矩阵，i u 是U 的列向量。设j λ为矩阵D W -的次小特征值，则j λ所对应的特征向量j u 即为Feidler 向量。Fiedler 向量中各元素的数值大小反映了其对应顶点的相互关系，可根据Fiedler 向量使用“0分法”对路网进行划分。
4 实例分析
为验证基于MFD 的路网评价子区划分方法，本文选取广州市海珠区江南片区作为实测数据验证分析区域，区域路网双向总长度约为25km 。试验所用的数据是根据现实路网的交通运行历史数据在Paramics 仿真平台上模拟获得，通过Paramics 的Modeller 模块对路网进行建模，获得仿真路网如图1所示，包括：弧段39条，结点36个，OD 小区12个，信号控制点20处，线圈检测器51组。其中编号为OD 小区编号。
12
3
4
5678
9
1011
12
图 2 Paramics 仿真路网建模效果图
为获得路网在各种运行状态下的运行参数特征，通过在仿真路网中设置不同的交通需求OD 矩阵，进行“平峰—高峰”等不同交通需求转换下的交通仿真，共输入不同的OD 矩阵共计80个，共进行仿真50次，每次仿真时长为4小时。
根据Ncut方法，可依次把全路网划分成1到5个评价子区，划分结果如图2（a）-（e）所示。
（a）N=1
地震与海啸的关系
（b）N=2（c）N=3
（d）N=4（e）N=5
图 3 评价子区划分实例（N为子区数）
