基于NCut算法的城市路网动态分区研究

Research on Dynamic Partitioning of Urban Road Networks Based on NCut Algorithm

摘要: 为改善城市道路交通路网区域拥堵的管控措施，本文提出一种路网动态划分算法。考虑到空间相邻路段的相似性，引入速度时间序列的相关系数去度量变化趋势并构建交通运行特性指标。通过归一化割方法(Normalized Cut, NCut)构建初步路网分区算法，结合自适应调节算法路网进行逐时段的动态分区。利用贵阳市数据验证算法的有效性并评估早晚高峰的分区演变效果。结果表明，所提出的分区算法能揭示不同时期交通演变规律，早晚高峰较平峰有更优的表现，所提出算法能达到有效并理想的分区结果。

Abstract: In order to improve the control measures of regional congestion of urban road traffic network, this paper proposes a road network dynamic classification algorithm. Considering the similarity of adjacent road sections in space, the correlation coefficient of speed time series is introduced to measure the change trend and construct the traffic operation characteristics index. A preliminary road network partitioning algorithm is constructed by the Normalized Cut (NCut) method, which is combined with an adaptive adjustment algorithm for dynamic partitioning of the road network on a time-by-time basis. The effectiveness of the algorithm is verified using data from the city of Guiyang and the effect of the partitioning evolution in the morning and evening peaks is evaluated. The results show that the proposed partitioning algorithm can reveal the traffic evolution pattern in different periods, and the morning and evening peaks have better performance than the flat peaks, and the proposed algorithm can achieve effective and ideal partitioning results.

1. 引言

随着国民经济的飞速发展，我国私家车保有量呈急剧上升趋势，道路交通拥挤逐渐成为社会问题。而城市交通拥堵不再局限于路口或路段的拥堵，逐渐演变成了区域性拥堵，传统的面向节点或局部路段的管控措施已经很难发挥成效。因此需要探究城市路网内部特征，从子区视角进行交通流规律分析。交通子区划分能够将复杂的路网结构分成相对同质的若干个子区域，便于根据每个子区交通特性实施灵活的管理措施，提高交通协调控制策略的效率与性能。

交通控制子区的概念最早是1971年由Walinchus [1] 提出的，将一个大规模复杂交通路网根据给定的指标划分为多个子区域，根据各个子区的不同特点实施不同的控制策略。基于此，国内外学者针对路网交通特性制定相应的标准和算法去研究在面对复杂网络时道路交叉口和路段间的相互影响。随后Ji等 [2] 利用路网的宏观基本图属性，将归一化割算法(Normalized Cut, NCut)应用在路网分区领域，并通过实际数据验证了算法的有效性。Dantsuji等 [3] 利用东京数据对比NCut算法与社区算法在路网上的运用，并结合MFD进行验证，结果表明社区算法生成的子区更小而NCut算法的效果更优。除了对算法模型的探究，不少学者将路网分区算法应用到实际交通场景中，Wang等 [4] 利用改进的C均值算法评价交叉口在交通路网中的重要性，选择关键路口将路网划分，最终达到对路网的合理分区及控制。Saedi等 [5] 改进了对路网旅行时间的估计，Leclercq等 [6] 实施边界控制策略并利用仿真结果验证算法的有效性。Zhang等 [7] 将异质性路网划分多个子区域后实施边界控制的研究，在分区的基础上进行交通流预测 [8] 。Yang等 [9] 提出了基于张量分解的聚类方法，对比了高峰期和非高峰期交通模式的异质性，为交通控制需求提供了一定的方向。

由于交通拥堵具有时变性，在每一时刻执行完整的静态划分是一项计算量较大的工程。此后，部分学者将静态路网划分扩展到了交通路网的动态划分研究。Saeedmanesh等 [10] [11] 提出了一种相似性度量模型，基于局部优化的分区方法运用对称非负矩阵分解理论，将深圳市路网划分为低方差的内部簇。Guo等 [12] 利用社区检测的理论，提出能动态识别路网交通拥堵区域的方法。Luo等 [13] 提出了一种静态分区与动态分区相结合的分区划分方法。当交通流处于非拥堵状态时进行静态分区，而针对交通流拥堵时的路网，在静态划分的基础上进行动态划分。Yan等 [14] 基于莫兰指数分析了链路间的空间自相关特征，实现交通网络的空间划分。然而上述研究对分区算法都是以瞬时的交通数据为基础，区域演变规律不明显。

现有的大多数文献中多数以仿真数据进行研究并且对划分的验证和原则缺少明确定义，在动态划分算法上都是以瞬时交通数据来研究。在此基础上本文结合交通运行特性，引入速度时间序列，构建交通运行特性衡量指标。在保证区域连通性的前提下，将改进的归一化割算法应用于目标路网的分区研究。利用贵阳市观山湖区路网采集的交通流数据进行案例分析，考虑到交通流在时间上的动态变化特点，对交通早高峰、晚高峰时期的道路演变规律进行探究，验证了算法的有效性和实用性。

2. 基于NCut的路网分区算法

2.1. 交通运行特性综合衡量指标

以往的分区算法，多数利用空间上的相似性作为理论基础，而交通流是一个演变的过程，对不同时段交通变化趋势的研究可以更好理解交通拥堵的形成和消散。为了结合空间相邻路段的相似性，利用相关系数去度量速度时间序列的变化趋势。本文综合考虑衡量交通状态特性的交通密度、衡量空间距离的欧式距离以及衡量变化趋势的相关系数构建交通运行特性综合衡量指标。

假设n维密度观测值为 $\theta =\left\{{\theta }_1,{\theta }_2,\cdots ,{\theta }_n\right\}$ ，坐标点为 $\eta =\left\{\left(x_1,y_1\right),\left(x_2,y_2\right),\cdots ,\left(x_n,y_n\right)\right\}$ 构建密度矩阵和距离相似矩阵为：

$K={\left(k_{ij}\right)}_{n\times n}{k}_{ij}=\exp \left[-{\left({\theta }_i-{\theta }_j\right)}^2\right]$ (1)

$E={\left(e_{ij}\right)}_{n\times n}{e}_{ij}=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$ (2)

其中 $K$ 为密度矩阵， $E$ 为距离矩阵，度量观测点的空间属性，而在时间维度上，路段当前时刻的交通状态与相邻时间段存在相关关系，引入Pearson相关系数度量分析交通流速度之间的相似程度。假设k维的时间序列 ${\alpha }_i=\left\{{\alpha }_{i1},{\alpha }_{i2},\cdots ,{\alpha }_{ik}\right\}$ 和 ${\alpha }_j=\left\{{\alpha }_{j1},{\alpha }_{j2},\cdots ,{\alpha }_{jk}\right\}$ ，相关系数矩阵 $P$ 则用来衡量速度间变化的相关性，定义为：

$P={\left(p_{ij}\right)}_{n\times n}{p}_{ij}=\frac{\mathrm{cov}\left({\alpha }_i,{\alpha }_j\right)}{{\sigma }_{{\alpha }_i}{\sigma }_{{\alpha }_j}}=\frac{{\displaystyle \underset{i=1}{\overset{k}{\sum }}\left({\alpha }_{ik}-{\bar{\alpha }}_i\right)\left({\alpha }_{jk}-{\bar{\alpha }}_j\right)}}{\sqrt{{\displaystyle \underset{i=1}{\overset{k}{\sum }}{\left({\alpha }_{ik}-{\bar{\alpha }}_i\right)}^2}}\sqrt{{\displaystyle \underset{i=1}{\overset{k}{\sum }}{\left({\alpha }_{jk}-{\bar{\alpha }}_j\right)}^2}}}$ (3)

由式(1)~(3)分别得到不同交通特性矩阵，但由于三者的量纲不同，在构造交通特性的综合性指标时，需要消除量纲的影响。本文对三种度量指标分别进行归一化处理，分别得到 $K^{*}$ 、 $E^{*}$ 、 $P^{*}$ 。相似程度越高，得到的密度矩阵和距离矩阵越小，而相关系数矩阵越大，因此还需要对相似矩阵进行翻转，最终得到交通运行特征综合性指标 $Q$ 为：

$Q=w_k{K}^{*}+w_e{E}^{*}+w_p\left(I-P^{*}\right)$ (4)

其中w为权重系数， $w_k+w_e+w_p=1$ ， $I$ 为元素全为1的矩阵。对于各个矩阵的权重的确定采用变异系数法赋权，数据指标间的差异越大更能够反映各个节点间的不同。在建立衡量性指标前，计算速度、密度、距离三个指标的权重，根据下式计算得到各项指标的变异系数以及各项指标权重，其中 $c_i$ 表示第i项指标的变异系数； ${\delta }_i$ 表示第i项指标的标准差； $x_i$ 表示第i项指标的均值。

$c_i={\delta }_i/x_{i}i=1,2,\cdots ,n$ $w=c_i/{\displaystyle \underset{i=1}{\overset{n}{\sum }}{c}_i}$ (5)

2.2. NCut算法理论基础

NCut算法是在图论的基础上将定义的无向图以同个子图内节点间的相似度高，不同子图间节点相似度低为目的进行切割。利用NCut算法划分路网子区，首先需要构建无向带权图 $G\left(V,E\right)$ ，其中V表示所有数据节点的集合，E为边的集合。假设将图G分割为A、B两个点集合，则 $A,B\subset V$ ， $A\cap B=\varnothing$ ，定义为：

$W\left(A,B\right)={\displaystyle \underset{i\in A,j\in B}{\sum }{w}_{ij}}$ (6)

其中 $w_i{}_j$ 为权重值，定义为：

$w_{ij}=\{\begin{array}{l}w\left(i,j\right),r\left(i,j\right)=1\\ 0,r\left(i,j\right)>1\end{array}$ (7)

进一步对于集合A、集合B，定义cut为划分A、B时连接的边的和：

$cut\left(A,B\right)={\displaystyle \underset{i\in A,j\in B}{\sum }w\left(i,j\right)}$ (8)

式(8)中 $w\left(i,j\right)$ 为节点 $i,j$ 的边的权重，该算法利用归一化割(NCut)和子图内部归一化关联度(Nassoc)来衡量划分的优劣，表示为：

$NCut\left(A,B\right)=\frac{cut\left(A,B\right)}{assoc\left(A,V\right)}+\frac{cut\left(A,B\right)}{assoc\left(B,V\right)}$ (9)

$Nassoc\left(A,B\right)=\frac{assoc\left(A,A\right)}{assoc\left(A,V\right)}+\frac{assoc\left(B,B\right)}{assoc\left(B,V\right)}$ (10)

其中 $assoc\left(A,V\right)={\displaystyle \underset{i\in A,j\in B}{\sum }w\left(i,j\right)}$ ，表示A与整体之间的关联度， $assoc\left(B,V\right)$ 表示B与整体之间的关联度；

$assoc\left(A,A\right)$ 和 $assoc\left(B,B\right)$ 分别为子图A和B内部的关联度。由于 $NCut\left(A,B\right)$ 与 $Nassoc\left(A,B\right)$ 能相互转换，见式(11)。

$\begin{array}{c}NCut\left(A,B\right)=\frac{cut\left(A,B\right)}{assoc\left(A,V\right)}+\frac{cut\left(A,B\right)}{assoc\left(B,V\right)}\\ =\frac{assoc\left(A,V\right)-assoc\left(A,A\right)}{assoc\left(A,V\right)}+\frac{assoc\left(B,V\right)-assoc\left(B,B\right)}{assoc\left(B,V\right)}\\ =2-Nassoc\left(A,B\right)\end{array}$ (11)

由式(11)得到最后该算法需要求解 $\min NCut$ 。但准确地最小化NCut值是NP难的问题，随着图规模的增加，计算复杂度将变得很高。因此，一般在实际求解中采用求解实值域中的特征系统近似逼近离散解。上述2-way归一化割算法，它只会用到第二小特征向量的信息，进一步的将2-way归一化割推广到K-way归一化割算法。K-way归一化割算法可以一次性将图像分为k个部分，再将前k个特征值对应的特征向量的信息将图G分割成k个子图。具体表达式如下，假设将图 $G\left(V,E\right)$ 被分为K个子图 $G_1,G_2,\cdots ,G_k$ ，对应的顶点集为 $V_1,V_2,\cdots ,V_k$ 有：

$Kncut\left(V_1\cdots V_k\right)=\frac{cut\left(V_1,V-V_1\right)}{assoc\left(V_1,V\right)}+\frac{cut\left(V_2,V-V_2\right)}{assoc\left(V_2,V\right)}+\cdots +\frac{cut\left(V_k,V-V_k\right)}{assoc\left(V_k,V\right)}$ (12)

$Knassoc\left(V_1\cdots V_k\right)=\frac{cut\left(V_1,V_k\right)}{assoc\left(V_1,V_1+V_k\right)}+\frac{cut\left(V_2,V_k\right)}{assoc\left(V_2,V_2+V_k\right)}+\cdots +\frac{cut\left(V_k,V_k\right)}{assoc\left(V_k,V_k\right)}$ (13)

2.3. 交通特性指标下路网动态分区算法

为了能使分区后各子区域间的交叉口和路段在空间上相互紧密连通，将交通运行综合矩阵定义为相似矩阵可能会使分区结果不理想，连通的紧密性也会让交通调控更加便利。考虑到节点在空间上的约束，建立节点 $i,j$ 的相似矩阵为：

$Q={\left(q_{ij}\right)}_{n\times n}{s}_{ij}=\{\begin{array}{l}exp\left(-\frac{q_{ij}}{2{\sigma }^2}\right),节点i,j相邻\\ 0,其他\end{array}$ (14)

式中通过矩阵 $Q$ 和高斯核函数定义相似度矩阵，由此得到整个路网区域的空间邻接权重矩阵。进一步，对于图G的任一个节点，定义度矩阵：

$d_i={\displaystyle \underset{j=1}{\overset{n}{\sum }}{s}_{ij}}$ $D=diag\left\{d_1,d_2,\cdots ,d_n\right\}$ (15)

度矩阵的对角元素为相似矩阵对应行的元素之和。随后需要计算拉普拉斯矩阵，它是度矩阵与邻接矩阵的差，即 $L=D-S$ ，将矩阵标准化后得到 $D^{-1/2}L{D}^{-1/2}$ 。通过计算拉普拉斯矩阵对应特征值和特征向量得到路网初步分区结果。

Figure 1. Flow chart of the adaptive adjustment algorithm

图1. 自适应调节算法流程图

然而路网初步的子区划分结果具有一定的偏离目标误差，在子区边界上个别节点在划分结果里并非最优，因此需要进一步进行边界调整。在不同子区间权重最小化、子区内部同质性最大化的基础上，提出一种自适应边界调整方法优化算法。通过迭代调整子区边界节点，保证子区边界的稳定性，使得划分趋于最优。算法流程如图1所示，首先需要确保内部加权值高于外部加权值，其次在子区边界的节点遍历子区的总关联度，使边界节点能调整到总关联度较大的子区，相关定义如下所示：

$d_a^i={\displaystyle \underset{j\in G_a}{\sum }w\left(i,j\right)}$ $d_b^i={\displaystyle \underset{j\in G_b}{\sum }w\left(i,j\right)}$ (16)

$cor\left(G\right)={\displaystyle \underset{i}{\overset{N}{\sum }}assoc}\left(A_i,A_i\right)$ (17)

其中 $d_a$ 为内部加权值， $d_b$ 为外部加权值； $cor\left(G\right)$ 为路网G的总关联度，N为子区总数。

对异质性的路网逐时段的动态分区能够有效呈现交通拥堵区域随时间演变的规律。具体而言，动态分区的过程中，路网分区的子区数量和交通状态的会随着时间的改变发生变化。以t时刻的静态划分结果为k个稳定块，在原有结果的基础上分别计算 $t+1$ 时刻对应的子区数为 $k-1$ ，k， $k+1$ 时的子区异质性的均值。对比指标选取下一时刻最小k值作为子区数，进一步完成子区间更新合并的过程。因此，本文针对不同时期道路交通情况对路网进行动态分区。算法具体流程如表1所示：

Table 1. Dynamic partitioning algorithm for NCut road networks based on traffic characteristic indicators

表1. 基于交通特性指标的NCut路网动态分区算法

2.4. 分区评价指标

为了能使分区后各子区域间的交叉口和路段在空间上相互紧密连通，将交通运行综合矩阵定义为相似矩为了确定划分的子区数合理性并评价不同划分数量下的小区划分结果，本文引入了归一化总体方差 $T{V}_n$ 以及各子区间匀质度的均值 $N{S}_k$ [2] 作为评价指标。归一化总体方差 $T{V}_n$ 可以用来对区域内部的总体方差进行把握，对于k个子区域的分区结果， $T{V}_n$ 的计算表达式如下：

$T{V}_n=\frac{1}{T}{\displaystyle \underset{t=1}{\overset{T}{\sum }}\frac{{\displaystyle \underset{i=1}{\overset{k}{\sum }}{N}_{R_i}Va{r}^t\left(R_i\right)}}{NVa{r}^t\left(R\right)}}$ (18)

式中R为整个路网的路段集合， $N_{R_i}$ 为子区 $R_i$ 的路段数，N为整个路网的总路段。 $Var\left(R_i\right)$ 表示为子区域 $R_i$ 在t时刻的速度方差，T为时间序列长度。在本文中 $T{V}_n$ 可以用来衡量区域划分后各子区节点的相似性。评价指标越小则路段间的相似度越高。另一方面，为了衡量相邻子区域见的差异性，引入 $N{S}_k$ 指标，计算如下：

$N{S}_k\left(R_i,R_j\right)=\frac{{\displaystyle \underset{i\in R_i}{\sum }{\displaystyle \underset{j\in R_j}{\sum }{\left({\theta }_i-{\theta }_j\right)}^2}}}{N_{R_i}{N}_{R_j}}$ (19)

其中 $N_{R_i},N_{R_j}$ 为子区 $R_i$ 和 $R_j$ 的路段数， ${\theta }_i,{\theta }_j$ 为不同子区的平均密度观测值。除了不同子区间的密度差异，子区内部的差异也需要量化， $N{S}_k\left(R_i\right)$ 为相邻子区间的密度差异，最后计算各区域的平均值 $N{S}_k$ 得出整体路网划分结果的判断标准。

$N{S}_k\left(R_i\right)=\frac{N{S}_k\left(R_i,R_i\right)}{\min \left\{N{S}_k\left(R_i,R_j\right)|ad\left(R_i,R_j\right)=1\right\}}$ $N{S}_k=\frac{{\displaystyle \underset{R_i\in C}{\sum }N{S}_k\left(R_i\right)}}{k}$ (20)

其中 $ad\left(A,B\right)=1$ 表示子区 $R_i$ 、 $R_j$ 在空间上相邻， $N{S}_k\left(R_i,R_i\right)$ 在度量子区间的相似性， $N{S}_k\left(R_i\right)$ 旨在度量子区内的相似性。 $N{S}_k<1$ 说明分区效果合理， $N{S}_k$ 越小表明子区的分区效果越理想。

3. 实例分析

3.1. 数据说明

本文选取贵阳市观山湖区域作为实例研究分析。路网如图2所示，一共包含47个路口或路段的数据，包括中心城区以及高速路段。数据集以秒为单位收集到各路口交通流量和速度，后续以5分钟为周期汇总处理，即一天共有288个观测值。

Figure 2. Guiyang Guanshanhu district road network

图2. 贵阳市观山湖区路网

3.2. 路网动态分区结果

在动态分区算法中，需要确定不同时期间隔时间段。本节将2.3节提出的动态分区算法应用于实例路网。在高峰期(8:00~10:00；17:00~19:00)以10分钟为时间间隔，平峰期(10:00~17:00)以30分钟为时间间隔进行动态分区。定义早高峰时段为 $t_1~t_{12}$ (08:00~10:00)；平峰时段为 $t_{13}~t_{26}$ (10:00~17:00)；晚高峰时段为 $t_{27}~t_{38}$ (17:00~19:00)。

表2为早高峰时期动态分区算法的评价结果，图3为其对应时间段的分区演变。从表2中可看出，综合两个指标，我们得到在 $t_1~t_5$ 时间段(08:00~08:50)最优分割子区数为3； $t_6~t_8$ 时间段(08:50~09:20)最优分割子区数为4，最后演变为 $k=5$ 的情形。而 $t_4~t_9$ 时间段(08:30~09:30)指标相对较小，所表现的分区情形更为合理和有效。图3中展示了具有重大变化时刻的节点，子区从 $k=3$ 开始持续增加分区数，出现更多不同质的拥堵区域，主要表现在部分区域1和区域2合并为区域4；在 $t_6$ 的状态持续了30分钟后再次发生变化，区域3分裂为两个部分，包括区域5和区域3。具体体现在这段时间内，区域5的平均速度均值略高于区域3，形成较为明显的分割特征。

Table 2. Evaluation of the evolution of the dynamics of the early peak period

表2. 早高峰时期动态演变评价

(a) t₁ (k = 3) (b) t₆ (k = 4) (c) t₉ (k = 5)

Figure 3. Evolution of the dynamics of the early peak period

图3. 早高峰时期动态演变

同样的，表3为平峰时期动态分区算法的评价结果，图4为其对应时间段的分区演变。本文在平峰期设置时间间隔为30分钟， $t_{13}~t_{16}$ 时间段(10:00-12:00)延续上一早高峰期的分区结果，在 $t_{17}$ 时间段(12:30)转变为3个子区域，这表明此时的交通拥堵得到了较大的缓解，一直持续到 $t_{22}$ 时段(15:00)；随着拥堵范围的进一步扩散，在之后两小时持续形成四个子区域的划分情形。而从图4中的空间上的演变图可观察出，由三区域转变为四区域主要是区域2分割成区域2和区域4，其余区域的边界有较小的变化。

Table 3. Evaluation of the dynamic evolution of the peaking period

表3. 平峰时期动态演变评价

(a) t₁₇ (k = 3) (b) t₂₃ (k = 4)

Figure 4. Evolution of peaking period dynamics

图4. 平峰时期动态演变

第三部分的动态演变是由17:00开始，时间间隔为10分钟，由表4可看出， $t_{27}$ (17:10)时刻延续上一平峰时期结果，之后拥堵情况的进一步扩散，路网的控制子区数一直持续在5这一稳定值。值得注意的是晚高峰时期的评价指标值相对更小，nsk最小达到0.658。说明其区域划分更为合理且具有更高的区域特征。图5展示了晚高峰时期 $t_{28}$ 和 $t_{33}$ 的分区演变，区域数量没有发生改变，表现在区域2进一步扩大延伸到区域1，区域3扩大区域面积扩大。

Table 4. Evaluation of the evolution of the dynamics of the evening peak period

表4. 晚高峰时期动态演变评价

(a) t₂₈ (k = 3) (b) t₃₃ (k = 4)

Figure 5. Evolution of the dynamics of the evening peak period

图5. 晚高峰时期动态演变

基于以上的分区演变，图6为动态分区下子区域的更新、分裂和合并的过程，图中不同颜色块代表不同区域的速度均值。从 $t_1$ 到 $t_6$ 再到 $t_9$ 表示子区的更新和分裂过程，在早高峰时段持续增长的交通拥堵，使得子区数逐渐扩大，交通速度也有所减小。在平峰期，区域出现合并情形，从评价指标结果来看其区域内部也具有较好的均质性。随着高峰期拥堵趋势的加强，子区间逐渐出现更新和分裂，各区域的平均速度也出现一定程度的下降。从以上的动态分区结果和演变上充分体现了算法的可行性和有效性，也能够在一定程度上反映贵阳市相应路网的交通出行和演变规律。

Figure 6. Dynamic partitioning with sub-regions updating, splitting and merging processes

图6. 动态分区下子区域更新、分裂和合并过程

4. 结论

通过考虑交通流时空特性，本文综合衡量空间距离以及交通流时间序列的相似性构建交通运行特性指标，在此基础上对NCut路网分区算法做出了改进，并对路网动态分区算法进行探究，引入 $N{S}_k$ 、 $T{V}_n$ 指标确定其最优的划分子区数。结合实际数据验证算法的有效性，最后结果表明所提出的算法能对异质性的区域进行有效划分，所提出的算法达到有效并理想的分区结果。

参考文献