基于含权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.

1. 引言

如何根据交通网络的拓扑结构和交通流的网络分布特征，将庞大且复杂的路网划分成若干独立的子区，有效实现子区上的信号控制，使得整个路网系统变得更加高效、可靠和灵活，一直备受研究者关注。自1971年Walinchus提出路网交通控制子区的概念 [1] 以后，关于交通控制子区划分的方法，多是基于交叉口关联度模型，结合各种分区算法将交通特性相近的交叉口划到同一个控制子区。也有一部分分区算法是以路段为聚类对象，依据一个特定时间内的拥挤特征，利用谱聚类中的归一化分割(Normalized cut, Ncut)方法进行路网划分，并拓展到对小区的动态划分问题上 [2] [3] 。如李刚奇 [4] 、马莹莹 [5] 等进行的交通小区划分研究都运用了谱聚类方法。谱聚类在图像分割领域应用最早、也最广泛，具有坚实的理论基础，但其存在两个主要缺点 [6] ：其一是划分结果对参数值敏感；其二是需求解矩阵特征值，对于聚类规模较大的应用，计算和存储压力大。此外，还有基于聚类的小区划分算法，如Dimitriou等对k-mans算法和METIS算法的路网划分效果进行了对比 [7] ，发现k均值算法对纯数值属性对象的聚类性能优于METIS算法，但其无法考虑交通网络的空间连接性；王晓轩 [8] 进一步结合交通流特征，提出了考虑路段空间位置的路网分区方法。但是，基于聚类的小区划分算法，如k-means算法都有一些缺点，即需要事先指定待分类数据聚类数k，然而合适的k值选择是一个比较困难的，用户往往需要选择若干k值来进行实验。并且由于有奇异值对象存在，可能会相当程度上扭曲数据的分布，k-means算法对于噪声是敏感的且不能解决任意形状的数据聚类问题。Newman快速划分算法 [9] 是Newman等在GN (Girvan-Newman)算法 [10] 基础上于2004年提出的一种社团快速聚合划分算法，是一种凝聚式层次聚类算法。社区发现算法(Newman算法)常用在社群划分问题上，其实它也是交通控制小区划分的一种有效的算法。该算法的目的是将复杂网络划分成多个“同质”社区，即同一社区内的节点之间连接很紧密，不同社区间的连接非常稀疏。

此外，当前在路段交通流密度的获取上，多是采用微观仿真，如王晓轩运用浮动车数据结合Vissim仿真得到路网各路段的交通流密度值来进行交通控制子区的划分，本文采用基于用户均衡模型进行交通分配得到的路段交通流量来求解路段拟交通密度，因为其有两个优点：一是考虑了交通流量在网络中的分布，从而比已有方法更深入地考虑了人对路径的选择；二是能更好地适应交通需求变化情况下，交通控制灵活变动的需求，屏蔽现有交通控制方案给历史交通流带来的相关性影响。

为了使控制子区交通流具有更好同质性，提高其理论最大路网容量，本文以路段为节点，以路段拟交通流密度相似性为边权，对传统Newman算法进行改进，使该方法能够运用于有权网络的“社团”(交通控制小区)发现，使划分的小区更加符合交通控制的需要，并利用 $N{S}_k$ 指标 [11] 对划分出的交通控制小区进行“同质性”验证。

2. Newman快速划分算法及其改进

社区发现算法比较经典的有基于图分割的算法、层次聚类算法和基于模块度的优化算法。图分割算法的基本思想是循环迭代将网络划分成事先设定好规模的两个社区，停止条件是这两个社区之间边的数量达到最小，该数量即为图论中的最小割。其中，Kernighan-Lin算法 [12] 事先知晓网络中两个社区的大小，无法运用于实际交通网络；层次聚类算法，如GN (Girvan-Newman)算法虽然精度高，但是不知道最终会生成多少个社区、且不能判断算法何时终止。为了解决这些问题，Newman引入了模块度 $Q$ 的概念，它用来评价划分社区的质量。

社团模块度 [13] 的概念由Girvan和Newman提出，是目前被普遍接受的关于衡量社团划分的标准。模块度是指网络中连接社团结构内部节点边所占的比例与任意连接该社团之间边的比例差的期望。该期望值越高，说明节点越有集中在某些社区内，即网络的模块化结构越明显。可用 $Q$ 函数定量描述社团划分的模块化水平。

假设有 $n$ 个节点的网络，节点彼此之间共有m个连接。 $i$ 和 $j$ 表示节点，当两节点直接相连时，则 $A_{ij}$ = 1；否则 $A_{ij}=0$ 。 $$ 代表节点 $i$ 的度。 ${\delta }_{\left(C_{i,}{C}_j\right)}$ 用来判断节点 $i$ 和 $j$ 是否在同一个社区内，在同一个社区内 ${\delta }_{\left(C_{i,}{C}_j\right)}=1$ ，否则 ${\delta }_{\left(C_{i,}{C}_j\right)}=0$ 。则 $Q$ 函数可以表达为：

$Q=\underset{ij}{{\displaystyle \sum }}\left[\frac{A_{ij}}{2m}-\frac{k_i*k_j}{\left(2m\right)\left(2m\right)}\right]{\delta }_{\left(C_i,C_i\right)}$ (1)

假设网络已经被划分成 $k$ 个社团。定义 $k\times k$ 维的对称矩阵 $e=e_{ij}$ ，其中，矩阵元素表示第 $$ 个社团和第 个社团之间连接的边数与网络总边数的比例。设 $\text{Tre}=\underset{i}{{\displaystyle \sum }}{e}_{ii}$ 为矩阵中对角线上各元素之和，其表示网络中社团内部节点之间相连的边数在网络总的边数中所占的比例。设 $$ 为每行或者每列中各元素之和，其表示与第 $i$ 个社团中的节点相连的边在所有边中所占的比例，则模块度 $Q$ 也可以表达为：

$Q=\underset{i}{{\displaystyle \sum }}\left(e_{ii}-a_i{}^2\right)=\text{Tre}-\Vert e^2\Vert$ (2)

式中：

$e^2=\underset{i}{{\displaystyle \sum }}{a}_i^2=\underset{i}{{\displaystyle \sum }}{\displaystyle {\sum }_{j,k}{e}_{ij}{e}_{ik}}$ (3)

模块度 $Q$ 越大则表明社区划分效果越好。若社团内部边的比例不大于任意社团间连接边的比例的期望值，则 $Q\le 0$ 。 $Q$ 的上限为 $Q=1$ 。 $Q$ 越接近1，说明社团结构越明显，相应的社团结构划分良好。而在实际的网络中， $Q$ 值通常在0.3~0.7之间。在划分社团的过程中，计算每一种划分对应的模块度值，并找出最大 $Q$ 值所对应的一种或者几种划分，即找出最优的社团结构划分。

2.1. 基于模块度的Newman快速划分算法

该算法基于贪婪算法的思想，算法开始时，将社团中的每个节点看作一个初始社团，然后沿着使网络模块度增加最大或减少最小的方向不断地进行社区合并，在算法执行过程中会形成一个树状图，将树状图在 $Q$ 值达到最大的位置处进行断开，这样便能够得到网络中的最佳社区结构。

2.2. 算法步骤

Newman快速算法执行过程如下：

1) 首先把含有 $n$ 个的节点复杂网络视为 $n$ 个社团，那么，初始时有：

$$ (4)

$a_i=\frac{k_i}{2m}$ (5)

式中， $k_i$ 为节点 $i$ 的度； $$ 为网络中连接节点的边的总数。

2) 根据贪婪算法的原理，沿着使 $Q$ 增加或者减小速度最小的方向，依次合并两个有边连接的社团，并计算合并后的 $Q$ 值增量：

$\Delta Q=e_{ij}+e_{ji}-2a_i{a}_j=2\left(e_{ij}-a_i{a}_j\right)$ (6)

合并以后，对相应的元素更新，并将 $i$ 和 $$ 社团的行和列相加。

3) 重复上一步，直到每个节点都合并成为一个社团为止。

2.3. 算法改进

将道路网络中的路段抽象为点，相邻路段之间的连接关系抽象为边，则区域路网将被抽象为一个对偶的网络拓扑结构图。但是，道路交通网络拓扑结构图中各个元素之间的关系并不是简单的布尔关系。考虑到引言中各种划分方法虽然考虑的因素不太相同，但最终目的都是为了使得划分后的小区具有交通流的同质性且路网划分的目的是将路网划分为多个具有同等关联水平的小区，为了使Newman算法更加适用于有权网络划分，对经典的Newman社团快速划分算法进行改进，即以各路段拟交通流密度为参数，建立路段拟交通流密度相似度模型 $$ 作为道路网络节点 $i$ 和 $j$ 之间的边权参数， $D_{ij}$ 的计算如公式1所示：

$D_{ij}=1-\frac{\left|d_i-d_j\right|}{{{\displaystyle \sum }}^{\text{}}{d}_i}$ (7)

式中： $$ 表示路段 $i$ 的拟交通流密度， $D_{ij}$ 即表示两路段 和 的拟交通流密度相似度水平，密度越接近， $D_{ij}$ 的值就越接近1。

由于引入了路段接近水平边权参数 $D_{ij}$ ，改进后的元素 $e_{ij}$ 表示为：

$e_{ij}=\{\begin{array}{l}\frac{D_{ij}}{{{\displaystyle \sum }}_{i,j}{D}_{ij}};节点i与节点j之间有边相连\\ 0;其他\end{array}$ (8)

$a_i$ 可以表示为：

$a_i=\frac{{{\displaystyle \sum }}_j{e}_{ij}}{{{\displaystyle \sum }}_{i,j}{D}_{ij}}$ (9)

改进的Newman快速划分算法的合并原则与传统Newman快速划分算法一致，都是沿着 $$ 值增大最多或者是减少最小的方向，直至所有节点合并为一个社团。

3. 实例分析

为了验证本文方法在交通路网控制子区划分的有效性，选取常德市中心城区交通路网，进行划分实验。图1为研究片区的交通路网图，该路网中共有48个信号控制路口和103条路段。划分算法通过Matlab程序语言实现，其中使用用户均衡交通分配得到的路段交通流数据，然后除以路段长度计算得出各条路段的“拟交通密度”。

Figure 1. Changde downtown urban road network map

图1. 常德市中心城区道路网络图

3.1. 子区划分结果

为了验证方法的有效性，将传统Newman社团快速划分算法、本文提出的方法和传统K均值聚类方法得到的子区划分结果进行对比。

首先，将路网视为无权网络，只考虑路段间的拓扑关系，运用传统Newman快速划分算法对图1所示的交通路网进行控制子区划分，划分结果如图2所示。然后，引入路段拟交通流密度相关性参数，采用本文的改进的Newman快速划分算法对路网进行子区划分，划分结果如图3所示。子区合并过程中两种方法模块度 $Q$ 值变化情况如图4所示。由图4可知，采用传统Newman快速划分算法进行子区划分时，当子区划分至第98次时，模块度 $Q$ 达到最大值0.6021，此时子区划分结果最优，路网被划分为5个控制子区，如图5所示，对应图2的子区划分树状图。采用本文改进的Newman快速划分算法进行子区划分时，当子区划分至第98次时，模块度 $Q$ 达到最大值0.6278，此时子区划分结果最优，此时路网被划分为6个控制子区，如图6所示，对应图3的子区划分树状图。

Figure 2. Controls sub-area partitioning tree diagram based on Traditional Newman algorithm

图2. 传统Newman算法控制子区划分树状图

Figure 3. Controls sub-area partitioning tree diagram based on Improved Newman algorithm

图3. 改进Newman算法控制子区划分树状图

Figure 4. Modular values of subdivision results

图4. 子区划分模块度值

Figure 5. Control sub-area division result based on Traditional Newman algorithm

图5. 传统Newman算法控制子区划分结果

Figure 6. Control sub-area division result based on Improved Newman algorithm

图6. 改进Newman算法控制子区划分结果

接着，运用传统 $k$ 均值聚类方法进行两次子区划分实验，每次划分的初始聚类中心都是随机选取且不相同，划分结果分别如图7、图8所示：

Figure 7. First sub-division based on K-means clustering

图7. K均值聚类第一次子区划分

Figure 8. Second sub-division based on K-means clustering

图8. K均值聚类第二次子区划分

图7、图8显示了两次随机 $k$ 均值聚类算法划分出的控制子区在空间上的分布情况，同一种线型的路段被划分到同一控制子区，可以看出，各个控制子区的路段在空间上都比较分散，下一节将结合 $N{S}_k$ 指标对划分出的子区“同质性”进行评价。

3.2. 划分结果指标分析

为了评价划分出的控制子区同质性水平，这里引入文献中 [11] 定义的 $N{S}_k$ (NcutSilhouette)指标来衡量不同子区之间的密度差， $N{S}_k$ 指标通过各子区的路段交通流密度来计算子区之间的平均密度距离：

$N{S}_k\left(A,B\right)=\frac{{{\displaystyle \sum }}_{i\in A}{{\displaystyle \sum }}_{j\in B}{\left(d_i-d_j\right)}^2}{N_A{N}_B}$ (10)

$d_i$ 表示路段 $i$ 的密度， $N_A,N_B$ 分别为子区域A和子区域B路段的数目。由于 $N{S}_k\left(A,B\right)$ 仅表征了子区域A和子区域B之间的平均密度距离，并不能体现子区之间的空间关系。为了补充这一点，进而采用公式(11)对其进行评价：

$N{S}_k\left(A\right)=\frac{N{S}_k\left(A,A\right)}{N{S}_k\left(A,B\right)}$ (11)

$N{S}_k\left(A,B\right)=\min \left\{N{S}_k\left(A,K\right)|K\in Neighbor\left(A\right)\right\}$ (12)

式中， $k$ 表示为与子区A相邻接的子区(这里我们只比较相邻子区之间的密度相近性，因为对于两个空间上不相邻的控制子区，即使它们内部的路段密度水平接近，也并不影响分区结果的好坏)。

整个路网的划分结果将由公式(13)进行评价，其表示所有划分子区平均密度距离的平均值：

$AN{S}_k=\frac{{{\displaystyle \sum }}_{A\in C}N{S}_k\left(A\right)}{k}$ (13)

式中， $k$ 为划分出的子区数，C为划分的子区集合。

$NS$ 评价标准也可以以路段拟交通流密度的方差和均值来表达：

$N{S}_k\left(A,B\right)=Var\left(A\right)+Var\left(B\right)+{\left(u_A-u_B\right)}^2$ (14)

式中 $u_A,Var\left(A\right)$ 分别为子区A中路段拟交通流密度的均值和方差，同样的可以得到：

$N{S}_k\left(A\right)=\frac{N{S}_k\left(A,A\right)}{N{S}_k\left(A,B\right)}=\frac{2Var\left(A\right)}{Var\left(A\right)+Var\left(B\right)+{\left(u_A-u_B\right)}^2}$ (15)

由公式(15)可知，当均值差很大、方差很小时，说明子区A划分结果很好。一般情况下如果子区A的方差很小，可知子区A的划分结果很好，此时由 $Var\left(A\right)<Var\left(B\right)$ 可知， $N{S}_k\left(A\right)<1$ 。如果大部分子区都有较小的方差和 $NS$ 值，但是有个别的子区有较大的方差和 $NS$ 值时，这种划分结果仍是有效的。

参照图5~8由各方法的划分结果，计算的各子区和整个路网的 $N{S}_k$ 值如表1所示。

通过划分后的路网分区图(图5~8)和相关指标(表1)对比，可以发现传统K均值聚类算法得到的各子区 $N{S}_k$ 指标和路网 $N{S}_k$ 指标都相对最小，但同一个子区内的路段在空间位置上不相连，没有实际运用价值，且通过第一次和第二次划分试验结果(图7~8)对比可以发现，划分结果的质量过于依赖初始聚类中心的选取，造成划分结果的不稳定。与传统Newman快速划分算法控制子区划分结果对比，可以发现本文方法得到的 $N{S}_k$ 值更小，表明划分结果更好，且引入了路段拟交通密度作为边权，使得划分出来的结果更加符合交通网络的特性、更合理。由于路段密度随着时间的变化而不断改变，可以获取不同时段的路段密度对交通路网进行动态划分。本文提出的方法，在评价指标上不及传统的K均值算法，但其很好地保证了子区路网的连接性和控制子区的“同质性”，实现了其在路网划分中的有效应用。

Table 1. Evaluation index of various zoning methods

表1. 各种分区方法评价指标

4. 小结

为使交通网络控制子区内的交通流具有更好的同质性，本文以路段为对象，通过对传统的Newman快速划分算法进行改进，引入路段拟交通流密度相关性参数作为边权，使得划分出的控制子区既能达到空间上的紧凑性，又能结合路网交通流相关性，使得划分出的子区内部路段拟交通密度相近，可以近似认为子区内部为同质的交通流，便于交通子区内的交通协调控制。本文从宏观层面探讨城市控制子区的划分，实现了子区划分自动化；下一步将在本文基础上研究如何实现子区间的协调控制 [14] 。