Research on Route Planning Based on Congestion Prediction

交通流预测通过分析历史交通流中的流动趋势，对未来时刻的交通流给出预测结果，可以看做是一类序列预测问题。然而，交通流序列呈现出一种复杂和动态的时空相关性^[9]，对于路网中的每一个节点，在同一时刻，邻居节点会对它影响，这是空间相关性。此外，每一个节点也可能受到过去时刻自己的影响，这是时间相关性。

在空间相关性建模方面，目前的主流方案是ChebNet图卷积^[10]，卷积核$\Theta $和图信号$ x $在时域上的卷积结果如式(1)所示：

式中，$ {\theta }_{k} $是切比雪夫多项式系数；K是卷积核的感受野半径；$ {\boldsymbol{L}}={\boldsymbol{D}}-{\boldsymbol{A}} $是图的拉普拉斯矩阵，由邻接矩阵$ {\boldsymbol{A}} $和度矩阵$ {\boldsymbol{D}} $计算得来。$ \bar{{\boldsymbol{L}}}=2L/{\lambda }_{{\mathrm{max}}}-{I}_{n} $是归一化的拉普拉斯矩阵，$ {\lambda }_{{\mathrm{max}}} $是拉普拉斯矩阵的最大特征值。$ {T}_{k}\left(\bar{{\boldsymbol{L}}}\right) $是第$ k $阶的切比雪夫多项式，其中$ {T}_{0}\left(\bar{{\boldsymbol{L}}}\right)={I}_{n} $，$ {T}_{1}\left(\bar{{\boldsymbol{L}}}\right)=\bar{{\boldsymbol{L}}} $，之后的结果通过式(2)进行推导：

式(2)中，由于$ {T}_{0}\left(\bar{{\boldsymbol{L}}}\right)={I}_{n} $，$ {T}_{0}\left(\bar{{\boldsymbol{L}}}\right)x $使得图中每个节点都提取了自己的信息。$ {T}_{1}\left(\bar{{\boldsymbol{L}}}\right) $中的所有非零元素都是1阶邻居和当前节点本身，如果将本身作为0阶邻居节点，那么$ {T}_{1}\left(\bar{{\boldsymbol{L}}}\right)x $使得图中每个节点都提取了0阶到1阶邻居的信息。以此类推，$ {T}_{k}\left(\bar{{\boldsymbol{L}}}\right)x $使得每个节点都提取了0阶到k阶邻居的信息。最终这些信息通过切比雪夫多项式系数$ {\theta }_{k} $进行加权求和，这些系数决定哪一阶的邻居提供更多的信息。而同一阶邻居对当前节点的不同影响程度由邻接矩阵$ A $进行区分。

在时间相关性建模方面，目前主流的方案主要有循环卷积神经网络RNN^[11]和卷积神经网络CNN^[12]。CNN模型一般空间维度的卷积核大小为1，步长为1，使得其只在时间维度聚集信息。时间维度的卷积核大小为$ {K}_{t} $，步长为1，使得每一个节点都聚集了当前时刻以及$ {K}_{t}-1 $个邻近历史时刻的信息。

路阻函数表述了路段的通行时间与路段上采集到的交通流参数之间的关系，BPR路阻函数如式(3)所示^[13]：

式中，$ t $是通行时间；$ {t}^{0} $是自由行驶时的通行时间；$ C $是路段通行能力，是流量$ Q $能够达到的理论最大值，如式(4)所示：

式中，$ {K}_{j} $是阻塞时的交通密度；$ {V}_{f} $是自由行驶时的通行速度。

本文的拥堵预测模型主要包括交通流预测和拥堵状态判定两个阶段。交通流预测模型对路网中的时空相关性进行建模，然后对未来时刻的交通流参数进行预测。拥堵状态判定模块在给定交通流参数的情况下，对拥堵状态进行分级判定。

在ChebNet模型中，同一阶邻居节点对当前节点的不同影响程度由邻接矩阵区分，邻接矩阵的构建，主要有基于连接和基于距离这两种方式。基于连接的邻接矩阵只表达了连接关系，没有对同一阶的邻居节点做区分。基于距离的邻接矩阵单一使用距离作为区分标准，不够全面。

针对上述问题，本文采用三维权重矩阵$ {\boldsymbol{W}}\in {{\boldsymbol{R}}}^{K\times N\times N} $进行优化，其中第一个维度是切比雪夫多项式的阶数，后面两个维度为路网节点数量，并按照式(5)进行初始化：

使用权重矩阵后的图卷积式如(6)所示：

通过可训练参数$ {w}^{k} $，可以自适应调整同一阶邻居的影响程度。

时间相关性提取方面，本文改进了传统的CNN模型，如图1所示。其中横轴代表空间信息，表示当前路网中所有节点在同一时刻采集到的交通参数。纵轴代表时间信息，从上往下是路网中每个节点严格按照时间顺序采集到的交通参数序列。在空间维度，卷积核的长度为1，相当于在卷积的过程中只聚集时间维度的信息，并且空间维度的卷积步长也为1，从而对路网中的所有节点都提取时间相关性。在时间维度，使用不同大小的卷积核进行卷积。使用多个卷积核进行卷积后，时间轴上越靠后的时刻能聚集到更多的信息，从而尽可能地提高信息利用率，增加卷积的感受野，提高时间相关性的提取能力。

本文采取的交通流预测模型如图2所示，使用时空图卷积层提取时空相关性。时空图卷积层由上述的一个空间维度图卷积和两个时间维度卷积堆叠而成。模型最后的输出通过时间维度卷积和全连接层转为未来时刻的交通流参数。

拥堵状态评估主要分为单参数评估和多参数评估。单参数评估只使用到了一种交通流参数，根据输入参数的取值得到所在的区间，即为最终的拥堵状态判定结果。由于路网的复杂性，单参数不能够完全反映路网的通行状况，所以本文选取了多参数判定方案，通过熵权法为影响因子更高的参数赋予更高的权重，最后利用模糊综合法判定，综合考虑多参数后确定最终分级。具体步骤如下：

1）假设样本长度为$ k $，每个样本有$ n $种交通流参数，$ {d}_{il} $代表第$ i $个样本的第$ l $种交通流参数。

2）将样本归一化并计算第$ i $个样本的第$ l $种参数占该种参数的比重$ {p}_{il} $,通过比重$ {p}_{il} $计算出第$ l $种参数的熵值$ {e}_{l} $和差异系数$ {g}_{l}=1-{e}_{l} $,如式(7)所示：

3）通过差异系数确定第$ l $种参数的权值，某种交通流参数的差异系数越大，说明参数对拥堵状态的影响越大，如式(8)所示：

确定好权重后，通过模糊综合判定进行拥堵分级。模糊综合判定的核心思想是不绝对地肯定与否定，而是利用隶属度来描述一个元素的归属问题，隶属度越接近1，那认为该元素归属度更高。具体步骤如下。

1）确定每一种交通参数分级区间以及拥堵状态分级。假设有$ m $种拥堵分级，$ {{\boldsymbol H}}=\{{\mu }_{1},{\mu }_{2},\cdots,{\mu }_{2m-2}\} $是对应的临界值。

2）计算参数$ {d}_{il} $对应每一种拥堵分级的隶属度$ {r}_{il}^{m} $，采用梯形隶属度函数下的计算方式如图3所示。

3）综合考虑每一种参数，得到第$ i $个样本的评价矩阵$ {{\boldsymbol{P}}}_{i} $，如式(9)所示：

最终的拥堵分级为$ \mathrm{m}\mathrm{a}\mathrm{x}({p}_{1},{p}_{2},\cdots ,{p}_{m}) $所在的下标。

在路径规划中，计算路段的通行时间是非常重要的环节，是影响车辆在路网中行驶的重要因素。在基于拥堵预测的场景下，拥堵预测模型能够提供未来时刻的交通流参数以及拥堵状态，通过路阻函数可以将路段上采集到的交通流量转化为路段的通行时间。路段通行时间如图4所示。

图中，$ d $是预测的时间间隔；$ L $是该路段的长度；$ t $是进入路段的时刻。通过拥堵预测模型和分段路阻函数能够得到未来每个时刻的瞬时通行时间$ {T}_{ij}^{k} $和平均通行速度$ L/{T}_{ij}^{k} $，之后利用拟合补全拥堵预测未提供的细节，采用积分的方式将离散的信息组合成连续的形式。再从$ t $时刻开始积分，则路段在未来时刻的通过时间为积分面积$ L $的多边形在时间轴上的投影。

上述路段通行时间的计算方法可以量化拥堵时长带来的影响，从而发现更有潜力的路段。并且能够及时规避拥堵，比如某些路段在进入时刻还是畅通状态，但在驶离阶段发生拥堵，那么这些影响会表现在路段的通行时间上，使得最短路径算法不再选择该路段，达到避开拥堵的目的。

计算完路段的通行时间后，路网中的每条路段都有了权重，之后可以通过路径规划算法搜索路径。

算法1　拥堵预测下的路径规划算法

输入起点$ {n}_{s} $, 终点$ {n}_{g} $, 开始时刻$ t $

通行时间矩阵$ {\boldsymbol{T}}={\mathrm{cal}}\_{\mathrm{travelT}}\left(t\right) $

初始化$ Q=\varnothing $, $ {\mathrm{rhs}}\left({n}_{s}\right)=0 $

　for $ n\in N:g\left(n\right)=\infty ,{\mathrm{rhs}}\left(n\right)=\infty $

　$ Q.{\mathrm{add}}({n}_{s},{\mathrm{key}}({n}_{s}\left)\right) $

　while $ Q.{\mathrm{minKey}} < {\mathrm{key}}\left({n}_{g}\right)\left|\right|{\mathrm{rhs}}\left({n}_{g}\right)\ne g\left({n}_{g}\right) $

　　$ n=Q.{\mathrm{minNode}}\left(\right) $

　　　if $ g\left(n\right) > {\mathrm{rhs}}\left(n\right): $

　　　　$ g\left(n\right)={\mathrm{rhs}}\left(\right) $

　　　　for $ q\in {\mathrm{Out}}\left(n\right):{\mathrm{updateNode}}(q,g\left(q\right),{\boldsymbol{T}}) $

　　else:

　　　$ g\left(n\right)=\infty $

　　　for $ q \in {\mathrm{Out}}\left(n\right) \cup \left\{n\right\} : {\mathrm{updateNode}}(q,g\left(q\right),{\boldsymbol{T}}) $

　　function $ {\mathrm{updateNode}}(n,g\left(n\right),{\boldsymbol{T}}) $

　　if $ n\ne {n}_{g}: $

　　　$ {\mathrm{rhs}}\left(n\right) = {\mathrm{m}\mathrm{i}\mathrm{n}}_{n{\text{`}}\in {\mathrm{In}}\left(n\right)}(g\left(n{\text{`}}\right) + {\mathrm{cost}}(n{\text{`}},n,g\left(n\right)\left)\right) $

　　if $ n\in Q:Q.{\mathrm{remove}}\left(n\right) $

　　if $ g\left(n\right)\ne {\mathrm{rhs}}\left(n\right):Q.{\mathrm{add}}(n,{\mathrm{key}}(n\left)\right) $

　end function

如算法1所示，$ {\mathrm{out}}\left(n\right) $表示经过节点$ n $一跳能到达的节点，$ {\mathrm{in}}\left(n\right) $表示一跳能到达$ n $的节点，$ g\left(n\right) $表示上一轮迭代中到达节点$ n $的最短时间。$ {\mathrm{rhs}}\left(n\right) $表示当前迭代中到达节点$ n $的最短时间，其中$ {\mathrm{cost}}(n{\text{`}}, n,g(n\left)\right) $是路段$ (n{\text{`}},n) $通行时间。如果$ g\left(n\right)\ne {\mathrm{rhs}}\left(n\right) $表示当前迭代中$ g\left(n\right) $未同步到最优；如果$ g\left(n\right)={\mathrm{rhs}}\left(n\right) $，节点$ n $已经同步到最优。除此之外，启发因子$ {\mathrm{key}} $如式(10)所示：

式中，$ h\left(n,{n}_{g}\right) $是当前节点到终点的预估代价。

在算法的初始化阶段，通过拥堵预测模型和分段路阻函数计算路网的瞬时通行时间矩阵，并设置起点的$ {\mathrm{rhs}}\left({n}_{s}\right) $为0，其余节点的$ g\left(n\right) $和$ {\mathrm{rhs}}\left(n\right) $都为$\infty $，并将起点加入优先队列。

之后从起点开始搜索迭代。每次迭代从优先队列取出$ {\mathrm{key}} $值最小的节点，如果$ g\left(n\right) > {\mathrm{rhs}}\left(n\right) $，说明上游节点找到了更优的路径，此时需要同步节点$ n $，并采用广度优先搜索策略，并将影响向下游节点传播。如果$ g\left(n\right) < {\mathrm{rhs}}\left(n\right) $，则当前节点信息有误，更新当前节点和其下游节点。

搜索迭代过程一直持续到发现终点完成同步并且其$ {\mathrm{key}} $是优先队列中的最小值。当迭代结束后，通过判断$ g\left({n}_{g}\right) $是否为$\infty $可得是否找到路径，并且从终点不断回溯上游节点$ n{\text{`}} $中$ g\left(n{\text{`}}\right)+{\mathrm{cost}}(n{\text{`}},n) $最小的节点即可得到最优路径。

本文使用的地图数据来源于开放街道图OpenStreetMap，下载江苏省无锡市巡塘镇的部分地图，对原始地图进行清洗。之后使用交通仿真软件SUMO产生交通流并添加检测点，获取仿真期间路网上的交通流量、通行速度、交通密度等交通流参数。在交通流预测阶段，使用平均绝对误差MAE、平均绝对百分比误差MAPE和均方根误差RMSE作为准确度指标。在拥堵预测阶段，将拥堵状态划分为畅通、基本畅通、轻度拥堵、重度拥堵4个分级。仿真参数设置如表1所示，其中地图面积为在OSM官网中选取地图所对应的真实地图面积，选取路网中的主干路及其支路作为检查点。每轮实验进行10轮迭代，每次迭代投入20辆测试车辆，在所有的测试车辆到达终点后，统计各项指标的平均值。

表2～4给出了不同预测模型下交通流量、交通密度和平均通行速度的预测结果。可以看出，LSTM模型预测效果好于传统SVR模型，而本模型和STGCN模型则优于LSTM和SVR模型。这是因为LSTM和SVR只提取时间相关性，而本模型和STGCN还考虑了路网拓扑方面的空间相关性。

图5给出了本文模型在高峰时期的拥堵预测细节图。可以看到拥堵预测的结果和实际状况较为吻合，包括9点～10点半期间畅通到重度拥堵的转变，以及1点～1点半期间重度拥堵到畅通的过渡，都能被本模型大致捕捉到。在8点～2点15的75个采样点中，畅通状态的预测错误次数为5次，基本畅通状态的预测错误次数为5次，轻度拥堵状态的预测错误次数为4次，总计高峰时期的预测准确度为81.33%。

图6给出了不同数量车辆情况下不同算法的行驶时间对比。可以发现，随着投入车辆的增加，Dijkstra算法的劣势逐渐显现，因为在当前时刻的最优路径并不一定是未来时刻的合理路径，导致后续的行驶过程中遇上拥堵从而影响了行驶时间。D*算法在每个交叉路口重新规划路径，从而避开了拥堵，提高了行驶效率。而本文算法因为结合了当前时刻和未来时刻的路况，其长期收益更大。在投入900辆车时，本文算法相对于Dijkstra算法在行驶时间上减少了22.13%，相对于D*算法减少了5.35%。

表5给出了预期行驶时间与实际行驶时间对比。可以看到Dijkstra算法采用当前时刻路况计算路段通行时间，因此预期行驶时间与实际行驶时间的差值会随着路况的复杂变化而急剧增大。D*算法会不断重规划进行修正，所以差值相对Dijkstra算法较小但波动性强。本文算法考虑了未来时刻路况并且完整地利用了路况的变化趋势，因此差值能稳定地维持在一个较小的范围。

图7给出了不同算法的行驶距离对比图。可以看到，D*算法行驶距离最长，这是因为频繁地重新规划带来了绕行。Dijkstra算法的行驶距离最短，但是最容易遇上拥堵。本文算法能在行驶时间比D*算法少的情况下也有更短的行驶距离，在投入数量为9000辆车时，行驶距离比D*算法减少了11.72%。

本文利用权重矩阵和多卷积核提高交通流预测的准确度，并采用熵权法和模糊综合判定进行拥堵分级输出，在此基础上计算未来时刻路段的通行时间并进行路径规划。仿真表明该方式能更准确地计算路段通行时间，从而降低路径规划算法的实际行驶时间和行驶距离，为智慧交通提供了一种可行的路径规划方案。