0 概述

城市规模的迅速扩张使路网复杂性日益增加, 针对交通拥堵的演化研究由此得到广泛关注。然而对单路段拥堵状况的研究难以适应相邻路段拥堵时的传播和消散特性^[1]。将路网划分为不同拥堵程度的控制子区, 能够可视化地显示实时的拥堵场景, 这体现了路网控制子区动态划分的重要性。

目前, 对于路网控制子区的划分方法已有一些相关研究^[2-3]。研究者通常运用谱图理论^[4]或归一化分割(Normalized cut, Ncut)算法^[5]求解矩阵特征系统, 从而将异构路网划分为密度均匀的控制子区, 但此类方法的划分性能对参数值较为敏感。文献[6]运用遗传算法与降维处理方法构建一种控制子区快速划分模型。文献[7]考虑拥堵的传播特性构建一种相似性模型, 将高相似性的路段聚类成簇。文献[8]将大型路网转化为密度峰值图, 并运用图切割算法实现控制子区划分的快速寻优。文献[9]在Ncut算法的基础上构建具有最优宏观基本图的控制子区划分模型, 但其获取的子区边界存在不平滑情形。文献[10]基于λ-连通性的概念提出一种启发式划分算法, 并执行边界调整程序得到具有光滑边界的控制子区。文献[11]将路段间的拓扑特性融入K均值聚类算法中, 弥补了必须对不平滑子区再根据连接性微调的不足。

上述方法实现了路网的静态划分, 但未考虑子区在时间维度上的动态演化。文献[12]研究拥堵路段的时空关系, 根据前一时刻的划分结果, 通过目标函数最小化对后一时刻的高异质性路段进行合并或分割。文献[13]采用一种两层划分方法, 通过增量地更新控制子区来跟踪拥堵的传播, 该方法与每一刻都重新执行路网控制子区静态划分的方法相比具有更高的效率。

本文考虑路段的密度分布与交通流的时变特性, 设计一种新的控制子区动态划分算法。利用路段与其邻域内其他路段的相似度重新定义局部密度概念, 确定控制子区划分方案, 并对孤立路段进行再处理, 实现聚类与连通性的同步约束。在此基础上, 将狄利克雷问题求解模型融入算法中, 迭代更新高异质性路段的划分结果, 从而捕捉子区的演变趋势, 实现控制子区的动态划分。

1 狄利克雷问题求解模型

构建一个路网无向图G=(V, E), 其中, 节点V={v₁, v₂, …, v_i, v_j, …, v_m}表示m条路段, 边集合E={e_ij}表示所有路段间的n个交叉口。令s_i、s_j表示路段v_i、v_j的饱和度, 则路段v_i、v_j间的相似度w(i, j)定义如式(1)所示:

$ w(i,j) = \exp \left( { - \frac{{{{({s_i} - {s_j})}^2}}}{{2{\sigma ^2}}}} \right) $

(1)

本文设置参数σ=0.1, 并构建相似度矩阵W={w(i, j)}_m×m。度矩阵D的定义如式(2)和式(3)所示:

$ {\mathit{\boldsymbol{D}} = {\rm{diag}} \{ {d_i}\} } $

(2)

$ {{d_i} = \sum\limits_{j = 1}^m w (i,j)} $

(3)

人为设置控制子区数k, 以适应交通量的时空分布。定义路网中控制子区的编号为G={G¹, G², …, G^k}。路网无向图上狄利克雷问题的求解模型可看作是根据调和函数(定义如式(4)所示)求解路段对于各控制子区的概率矩阵r, 其中, r(i, k)表示v_i属于子区G^k的概率。

$ D[\mathit{\boldsymbol{r}}] = \frac{1}{2}\int_\varOmega | \nabla \mathit{\boldsymbol{r}}{|^2}{\rm{d}}\varOmega $

(4)

由于拉普拉斯方程是狄利克雷积分的拉格朗日方程^[14], 因此拉普拉斯方程满足边界条件▽²r=0。定义(n×m)阶的路段关联矩阵, 如式(5)所示:

$ \mathit{\boldsymbol{A}}({e_{ij}},k) = \left\{ {\begin{array}{*{20}{l}} {1,i = k}\\ { - 1,j = k}\\ {0,{\rm{ 其他 }}} \end{array}} \right. $

(5)

定义(n×n)阶的0-1对角矩阵C, 则拉式矩阵可计算为L=A^TCA, 调和函数可分解为式(6):

$ D[\mathit{\boldsymbol{r}}] = \frac{1}{2}{(\mathit{\boldsymbol{Ar}})^{\rm{T}}}\mathit{\boldsymbol{C}}(\mathit{\boldsymbol{Ar}}) = \frac{1}{2}{\mathit{\boldsymbol{r}}^{\rm{T}}}\mathit{\boldsymbol{Lr}} $

(6)

由于L是半正定的, 因此D[r]具有唯一的极小临界点。将路网内的路段分为2个部分, 即划分到控制子区的稳定块V_S与未分配路段V_U, V_S∪V_U=V, V_S∩V_U=Ø。求解调和函数的临界值, 即在确定稳定块的情况下求解未分配路段属于不同子区的概率。假设L和r中控制子区的稳定块为第一部分, 未分配路段依次排序在后, 则调和函数可分解为式(7):

$ \begin{array}{*{20}{l}} {D[{\mathit{\boldsymbol{r}}_{\rm{U}}}] = \frac{1}{2}\left[ {\begin{array}{*{20}{l}} {\mathit{\boldsymbol{r}}_{\rm{S}}^{\rm{T}}}&{\mathit{\boldsymbol{r}}_{\rm{U}}^{\rm{T}}} \end{array}} \right]\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{L}}_{\rm{S}}}}&\mathit{\boldsymbol{B}}\\ {{\mathit{\boldsymbol{B}}^{\rm{T}}}}&{{\mathit{\boldsymbol{L}}_{\rm{U}}}} \end{array}} \right]\left[ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{r}}_{\rm{S}}}}\\ {{\mathit{\boldsymbol{r}}_{\rm{U}}}} \end{array}} \right] = }\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \frac{1}{2}(\mathit{\boldsymbol{r}}_{\rm{S}}^{\rm{T}}{\mathit{\boldsymbol{L}}_{\rm{S}}}{\mathit{\boldsymbol{r}}_{\rm{S}}} + 2\mathit{\boldsymbol{r}}_{\rm{U}}^{\rm{T}}{\mathit{\boldsymbol{B}}^{\rm{T}}}{\mathit{\boldsymbol{r}}_{\rm{S}}} + \mathit{\boldsymbol{r}}_{\rm{U}}^{\rm{T}}{\mathit{\boldsymbol{L}}_{\rm{U}}}{\mathit{\boldsymbol{r}}_{\rm{U}}})} \end{array} $

(7)

求D[r_U]关于r_U的倒数, 并找到临界点:

$ \begin{array}{*{20}{l}} {\frac{{D[{\mathit{\boldsymbol{r}}_{\rm{U}}}]}}{{\partial {\mathit{\boldsymbol{r}}_{\rm{U}}}}} = {\mathit{\boldsymbol{B}}^{\rm{T}}}{\mathit{\boldsymbol{r}}_{\rm{S}}} + \frac{1}{2}\left( {{\mathit{\boldsymbol{r}}_{\rm{U}}} \cdot \frac{{\mathit{\boldsymbol{r}}_{\rm{U}}^{\rm{T}}{\mathit{\boldsymbol{L}}_{\rm{U}}}}}{{\partial {\mathit{\boldsymbol{r}}_{\rm{U}}}}} + \mathit{\boldsymbol{r}}_{\rm{U}}^{\rm{T}}{\mathit{\boldsymbol{L}}_{\rm{U}}} \cdot } \frac{{{\mathit{\boldsymbol{r}}_{\rm{U}}}}}{{\partial {\mathit{\boldsymbol{r}}_{\rm{U}}}}}\right) = }\\ {{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\mathit{\boldsymbol{B}}^{\rm{T}}}{\mathit{\boldsymbol{r}}_{\rm{S}}} + {\mathit{\boldsymbol{L}}_{\rm{U}}}{\mathit{\boldsymbol{r}}_{\rm{U}}}} \end{array} $

(8)

令$\frac{D\left[\boldsymbol{r}_{\mathrm{U}}\right]}{\partial \boldsymbol{r}_{\mathrm{U}}}=0$, 得到L_Ur_U=－B^Tr_S。概率矩阵r对应的子矩阵r_S定义如式(9)所示:

$ {r_{\rm{S}}}(i,k) = \left\{ {\begin{array}{*{20}{l}} {1,{v_i} \in {G^k}}\\ {0,{v_i} \notin {G^k}} \end{array}} \right. $

(9)

对未分配路段对应的子矩阵r_U进行求解, 任意v_i属于各子区的概率之和满足式(10)。获取第(i－S)行(i∈{S+1, S+2, …, m})最大值的所在列l∈{1, 2, …, k}, 即将v_i划分到子区G^l内。

$ \sum\limits_l {{r_{\rm{U}}}} (i,l) = 1,\forall l \in \{ 1,2, \cdots ,k\} $

(10)

2 控制子区静态划分

本节基于密度峰值理论, 重新定义了局部密度概念, 用于自动识别控制子区的稳定块, 同时运用狄利克雷问题的求解模型实现控制子区的划分。子区划分流程如图 1所示。

2.1 局部密度定义

由于交通路网属于稀疏网络, 因此本文对传统局部密度概念中节点的度进行加权, 运用路段与其邻域内其他路段的相似度来求解局部密度, 使之适用于实际路网。

基于密度峰值理论^[15], 将任意路段v_i到每一个更高局部密度路段v_j的最短路径记为p_ij, 并将其中的最小值记为p_i。局部密度ρ_i的定义如式(11)和式(12)所示:

$ {{\rho _i} = \sum\limits_j {{a_{ij}}} \cdot w(i,j),w(i,j) > \theta } $

(11)

$ {{a_{ij}} = \left\{ {\begin{array}{*{20}{l}} {1,{p_{ij}} = 1}\\ {0,{p_{ij}} > 1} \end{array}} \right.} $

(12)

其中, θ是一个截断阈值, ρ_i表示在v_i的邻域内其他点与该点大于θ值的相似度之和。上述局部密度只对θ的相对大小敏感, 说明基于局部密度的划分算法具有很好的鲁棒性。θ的敏感度分析详见本文第4节。

2.2 控制子区稳定块识别

控制子区稳定块识别算法步骤如下:

输入  路段集合V, 局部密度集合{ρ₁, ρ₂, …, ρ_m}

输出 控制子区稳定块集合{S_tab¹, S_tab², …, S_tab^k}

步骤1 初始化任意子区G^k的稳定块集合S_tab^k=Ø。将路段局部密度按降序排列, 并搜索前k条路段{v₁, v₂, …, v_k}分别作为k个控制子区的质心。更新每个稳定块S_tab^k=v_k。

步骤2 若任意多个质心在空间上相邻, 则只保留局部密度最大的质心, 依次选择高局部密度的路段作为新的质心。循环该过程, 直到所有质心互不相邻。此时, 保证质心周围是低密度路段, 以避免质心选取到异常点。若获得的质心数小于k, 则返回步骤1, 重新赋k值。

步骤3 计算剩余的任意路段v_i到各质心的最短路径。若p_i=p_ij=1, 则将v_i归属于质心v_j所在的稳定块; 若v_i与多个质心的最短路径均为1, 则将其归属于与之具有最大相似性的质心所在的稳定块; 否则跳过该路段, 重复此步骤, 直到遍历完所有路段, 稳定块集合的更新结束。

通过改进的局部密度概念, 算法能够自动获取具有最大密度峰值的k个质心并识别控制子区的稳定块, 然后将稳定块作为输入参数进行静态划分模型的求解。

2.3 基于狄利克雷问题的控制子区静态划分

狄利克雷问题的求解模型能够解决子区内的最大关联性辨识问题^[16]。本节将改进的局部密度概念运用于求解模型中, 达到将高相似性路段聚类成簇的目的。

控制子区静态划分算法步骤如下:

输入 控制子区稳定块集合{S_tab¹, S_tab², …, S_tab^k}

输出 子区划分结果G={G¹, G², …, G^k}

步骤1 将路网内路段分为V_S(划分到子区的稳定块)与V_U(未分配路段), 通过求解狄利克雷问题, 对V_U内的元素进行划分。

步骤2 针对存在的不连通控制子区, 保留最大的连通区域, 将剩余的孤立路段或小的连通区域作为二次划分的目标。计算任意目标路段v_i相对于各子区G^k的紧密度c_kⁱ, 定义如式(13)所示:

$ c_k^i = \sum\limits_{{v_j} \in {G^k}} w (i,j),{G^k} \subset G $

(13)

步骤3 将具有最大紧密度的路段划分到对应子区内。若路段与多个子区具有相同的最大紧密度, 则任选其一, 并重复此步骤, 直到所有的子区内部连通时, 静态划分结束。

步骤2和步骤3是针对算法在执行控制子区划分时缺乏考虑路网拓扑结构及子区平滑性的不足, 进行子区平滑性优化的过程。

2.4 评价指标

将子区内部匀质性的均值NS_k^[17]与归一化总方差TV_n^[7]作为评价指标, 对比不同分区下的路网划分性能, 定义如式(14)~式(17)所示。两者的取值越小, 表明划分效果越好。

$ {\rm{NS}}({G^l},{G^k}) = \frac{{\sum\limits_{i \in {G^l}j \in {G^k}} {{{({s_i} - {s_j})}^2}} }}{{{N_{{G^l}}} \cdot {N_{{G^k}}}}} $

(14)

$ {\rm{N}}{{\rm{S}}_k}({G^l}) = \frac{{{\rm{NS}}({G^l},{G^l})}}{{\min \{ {\rm{NS}}({G^l},{G^k})|{\rm{ab}}({G^l},{G^k}) = 1\} }} $

(15)

$ {\rm{N}}{{\rm{S}}_k} = \frac{{\sum\limits_{{G^l} \subset G} {\rm{N}} {{\rm{S}}_k}({G^l})}}{k} $

(16)

$ {\rm{T}}{{\rm{V}}_{\rm{n}}} = \frac{{\sum\limits_{l = 1}^k {{N_{{G^l}}}} \cdot {\rm{var}} ({G^l})}}{{m \cdot {\rm{var}} (G)}} $

(17)

其中, ab(G^l, G^k)=1表示控制子区G^l、G^k相邻, N_G^l表示子区G^l内的路段数。

3 控制子区动态划分

由于交通量动态分布, 若对每一时刻的路网都执行静态划分, 计算复杂性较高, 因此本文提出一种动态划分算法存储前一时刻稳定路段的划分结果, 同时对异质性高的路段进行微调, 从而得到后一时刻较好的划分结果, 准确捕捉控制子区的演化趋势。

本文提出的动态划分算法采用迭代的聚类过程。在初始时刻t控制子区静态划分结果的基础上, 计算各子区(t+1)时刻的饱和度均值, 并更新相似度矩阵, 取饱和度与所在子区饱和度均值差异最小的路段作为新的质心, 以识别(t+1)时刻控制子区的交通状态。在此基础上, 将质心作为初始的稳定块, 迭代地捕捉与稳定块具有最大相似度w_max的路段, 并将其添加到稳定块集合中。需要注意的是, 稳定块必须包含在该子区内。但随着迭代次数的增多, 该块的异质性呈非线性增长趋势。因此, 此处设置限制条件w_max>δ, 使得稳定块达到一定覆盖率时截止扩展并缩短运行时间。本文设置δ=0.3。最后利用控制子区静态划分算法对剩余路段进行划分。动态划分算法仅将异质性高的路段作为研究对象, 降低了计算复杂性, 具体描述如下:

算法 动态划分算法

输入 控制子区数k, 终止时刻t′, 局部密度{ρ₁, ρ₂, …, ρ_m}, ρ₁>ρ₂>…>ρ_m

输出 路网划分结果G={G¹, G², …, G^k}

1.For i∈[1, k] do//t时刻稳定块识别

2.S_tabⁱ=v_i;

3.End For

4.For i∈[k+1, m] do

5.If (p_i=p_il=1) then

6.S_tab^l={S_tab^l, v_i}, l∈{1, 2, …, k};

7.Elseif (p_i=p_il=…=p_ik=1) then

8.w(i, l)=max{w(i, l), w(i, l+1), …, w(i, k)};

9.S_tab^l←{S_tab^l, v_i};

10.Else (p_i>1) then

11.++i;

12.End If

13.End For

14.While (t < t′)//狄利克雷问题求解

15.r_U=－L_U^－1B^Tr_S//概率矩阵求解

16.If (控制子区内部连通) then

17.G_t←{G_t¹, G_t², …, G_t^k}//t时刻的结果

18.Else (存在孤立路段集) then

19.搜索二次划分的目标{v_i, v_i+1, …, v_j};

20.c_kⁱ=max{c₁ⁱ, c₂ⁱ, …, c_kⁱ, …, c₁^j, …, c_k^j};

21.G_t^k←{G_t^k, v_i};

22.End If

23.t←t+1//时段更新

24.For i∈[1, k] do

25.w(S_tab^k, i)=max(w(S_tab^k, :));

26.w(S_tab^k, i)>δ, S_tab^k=S_tab^k∪v_i;

27.End For

28.End While//动态划分稳定块识别

4 案例分析 4.1 数据集与θ值的敏感度分析

考虑数据与问题来源的真实性, 本文以美国法默布兰奇市^[18]某区域的真实数据集为例进行分析。该路网包含211条路段, 道路拓扑图如图 2所示。数据集包含所有路段在2014年10月所有工作日的饱和度均值。本文将全天00:00—23:15的时段取15 min为间隔, 得到93个时段, 以饱和度为特性进行研究。

截断阈值θ是控制子区划分中一个关键参数, 其取值直接决定了分区效果。本文选取晚高峰期(t=69)时的路网进行划分。当分区数k=2~4时, θ值对NS_k与TV_n的影响如图 3所示。

由图 3可见, 在不同分区数下, NS_k与TV_n指标值随着θ的增大逐渐变小, 表明算法的划分性能逐渐增强。控制子区数k分别为2、3、4时, 路网的最优θ值为0.95、0.95、0.25, 此时NS_k与TV_n最小, 即算法的划分效果最佳。最优θ值下的路网评价指标如表 1所示。

4.2 不同分区下静态划分效果分析

t=69时刻的控制子区静态划分结果如图 4所示。结合图 5中各控制子区内饱和度的频率分布可知:当t=69时, 2分区时的子区2内部通畅, 多数路段的饱和度集中在0.2~0.5, 子区1为饱和区域; 4分区下的3、4子区内饱和度相似, 但连接两者的公共路段较少, 因此, 将其划分为两部分。由于执行了子区边界平滑处理, 因此各控制子区内部完全连通, 为交通信号控制策略提供了准确的依据。

将谱聚类算法、Newman算法^[19]、密度峰值聚类算法^[20]以及本文算法分别从NS_k与TV_n两个方面对比算法性能, 如表 2所示, 表中数据均以NS_k/TV_n的形式列出。

由表 2可见, 在3种分区模式下, 本文算法相较其他算法的NS_k与TV_n值均最小, 即控制子区的匀质性最高。其中, 2分区时本文算法相较密度峰值算法的NS_k、TV_n分别降低22%和11%, 体现了算法的有效性。

4.3 连续时段内动态划分效果分析

此处分析2分区下t=69~75时段内本文算法与两层动态划分算法的动态划分效果。不同时刻路网的饱和度分布如图 6所示, 控制子区的划分结果如图 7所示。

由图 7(a)可见, 本文算法与两层动态划分算法^[13]在大部分时刻的划分结果相较随着时间的步进一直保持原划分结果的静态划分具有更好的效果。其中, 本文算法在除t=71时的其他划分结果相较两层动态划分算法性能更好, 体现了本文算法的有效性。由图 7(b)可见, t=69~75时段内2个控制子区的饱和度逐渐减小, 说明路网处于拥堵消散阶段。同时由图 8可见, 拥堵子区1(虚线区域)呈现先扩大后缩小的变化趋势。

5 结束语

本文结合密度峰值理论和狄利克雷问题求解模型, 提出一种路网控制子区的动态划分算法, 用以实现控制子区的快速寻优, 同时提高子区边界的平滑性并捕捉控制子区的动态演化趋势。以美国法默布兰奇市的真实路网数据集作为案例进行分析, 结果表明, 该算法能够有效提升子区内部匀质性均值与归一化总方差, 增强控制子区动态划分的时效性。下一步拟将该动态划分算法应用于边界控制中, 并结合具体需求加以优化。