基于深度优先搜索算法的交通流向供需失衡路径辨识

2021-07-29 02:09李衬衬李大龙宋子文

科学技术与工程 2021年14期

李衬衬，孙锋，孙猛，李大龙，宋子文

(山东理工大学交通与车辆工程学院，淄博 255000)

城市交通系统是维持经济发展与日常生活的基础，交通形态和交通环境的复杂性以及交通供给的时滞性、有限性对城市路网中的交通出行者形成干扰，产生了不平衡的交通流分布，由此引发的交通拥堵严重制约了高峰时段的路网运行效率。中外学者针对此问题开展了一系列研究，柳波[1]建立了基于用户均衡的交通流演化模型，研究了从一种非均衡交通流状态到另外一种非均衡交通流状态的过程；He等[2]通过预测-修正模型描述了交通流中断后逐渐趋于均衡状态的过程；Kumar等[3]认为路网静态不均衡会导致驾驶员改变出行路径，并建立了出行者动态路径选择模型；Naguney等[4]建立了由非稳定向稳定状态转化的模拟方法；Lida等[5]对出行者动态路径的选择行为进行了研究，认为道路交通流的理想均衡状态难以达到；马海波等[6]对交通流网格自适应负载平衡预测进行了研究。上述成果都集中在非均衡交通流向均衡交通流的演化规律及过程研究，而关于交通流向失衡特征及快速识别的研究却涉及较少。分别针对交叉口、路段的流向失衡特征进行分析，并基于图论和深度优化搜索算法(deep first search,DFS)算法构建了交通流失衡路径识别模型，以期为流向供需失衡状态下交通流管控奠定一定的理论基础。

1 交通拥堵及供需失衡特征

流向供需失衡是指路段或交叉口不同方向流量比在不同时段表现出显著差异性，导致空间资源供需错位的运行状态。该状态在交叉口表现为进口不同转向之间的非均衡性，在路段上表现为双向车流之间的非对称性。

1.1 交叉口流向供需失衡特征

交叉口流向供需失衡的表现特征是进口道不同转向车流的时段性变化显著，导致固有的车道功能划分在部分时段无法适用，造成某一流向车道浪费而其他流向拥堵的现象。交通流转向不平衡最明显的特征是进口道各转向交通流之比在不同时段有明显差异性。

(1)交通流量变化。流向供需失衡进口道在流量变化方面呈现方向性转向不平衡及波动明显的现象。基于交叉口地磁检测数据，对淄博市华光路—西五路交叉口15:30—19:30的车流量进行统计，统计结果如图1所示。由图1可知，平峰与晚高峰的直行与左转车流量的比值变化浮动较大，呈现明显的非均衡性。

(2)排队长度变化。根据实地观测，不同时段的平均排队车辆数如图2所示,晚高峰时段，直行排队较长，达到了左转排队的3倍，影响绿灯期间的车流释放效率。

图2 交叉口不同时段的平均排队车辆数Fig.2 Average number of queuing vehicles in different periods of intersection

由此可见，交叉口进口流向供需失衡特征可通过式(1)来描述：

(1)

式(1)中：Ai为路网节点失衡的阈值，可作为开启可变车道条件的评价指标；d为转向不均衡系数；x为饱和度。

(2)

式(2)中：Ql为左转车车辆数；Qs为直行车车辆数；Qr为右转车车辆数；b为左转车车辆在总车数中所占的比例；d为标准转向不均衡系数；n为左转直行车道数总和；bgl,max、bpl,max分别为高峰期与平峰期左转车辆的比例最大值；bgl,min、bpl,min分别为高峰期与平峰期左转车辆的比例最小值；x为饱和度[7-8]。

当交叉口具有显著转向不平衡特征时，d≥1；当0.5≤d＜1时，交叉口具有轻微的不平衡特征；当d＜0.5时,交叉口不具有不均衡特征[9-10]。

1.2 路段流向供需失衡特征

路段流向供需失衡主要是由于两个原因造成：①居民的通勤出行造成的潮汐交通流，其显著特点是在时间上呈现规律性与周期性；②突发性事件造成的偶发性流向供需失衡[11-12]。

现基于路段微波检测数据，对淄博市城区主干路世纪大道的潮汐交通特征进行调查，调查结果如表1所示。

表1 早晚高峰交通流量及方向分布系数对比表Table 1 Comparison of traffic flow and direction distribution coefficient in morning and evening peak

通过表1可以看出，在早高峰由西向东的方向分布系数为66.81%，已经超过临界方向分布不均衡系数，达到了设置潮汐车道的交通条件。但是设置以后必须确保轻交通流方向上的路段饱和度不能低于重交通流方向上的路段饱和度，其通行能力能够满足该方向的交通需求。

由此可见，路段的失衡特征可以通过方向分布系数来描述：

(3)

式(3)中:Qq为轻交通流方向交通量；Qz为重交通流方向交通量;α为交通流影响因子。

根据方向分布系数和车流密度共同来确定路段可变车道的方向特征和管控策略，如式(4)所示：

(4)

式(4)中：Cl为路网路段供需失衡的阈值，可作为潮汐车道是否开启的相关参照；k为方向分布系数；Iij为路段密度。

(5)

式(5)中:Iij为交叉口i与交叉口j之间的路段密度；k为车道数；L为路段长度。

1.3 网络路径流向供需失衡特征

目前，城市的网络路径流向供需失衡主要是由于城市规划的功能分区布局不合理造成的。城市新建区域功能单一，多为居民住宅小区。商业、医疗、教育等资源仍然分布于城市中心，由此带来的便是城市结构向组团式方向发展，如图3所示。潮汐交通主要是由于人们白天进入中心城区办公，下班后离开中心城区所导致的，此现象呈现出一定的规律性和周期性[13-14]。

流向供需失衡初期表现为节点、路段的流向供需失衡，随着供需矛盾激化，逐步演化为区域路径的流向供需失衡。区域性供需失衡问题需更加综合和智能的管控手段去解决。而快速识别区域失衡路径和组合可变导向车道、潮汐车道进行管控，是制定区域流向供需失衡管控对策的关键。网络交通流向供需失衡特征演变如图4所示。

图3 网络流向不均衡交通空间形成Fig.3 Diagram of tidal traffic spatial characteristics

图4 网络交通流向供需失衡特征Fig.4 Characteristics of imbalance between supply and demand of network traffic flow

为了解决上述问题，提出将可变车道与潮汐车道综合使用的思路。首先潮汐车道默认为开启状态，可变车道设置原理为通过改变各流向的车道数来改变流量比，流量比反映了交通供给与交通需求的匹配情况，以左转与直行方向的交通流量比为阈值，作为可变车道功能属性转换的依据。

假设可变导向车道初始状态为左转，则由左转切换为直行需满足的条件如式(6)所示：

(6)

可变导向车道功能由直行切换为左转需满足的条件如式(7)所示：

(7)

式中：Yl、Ys分别为左转、直行方向流量比;Ql、Qs分别为左转、直行方向交通量；Nl、Ns分别为左转、直行方向车道数；Sl、Ss分别为左转、直行方向单车道饱和流量；α、β为修正系数，可取0.8～0.9。

2 交通流向供需失衡路径辨识模型

2.1 路网模型

网络流向失衡特征可通过检测路段及交叉口的流向供需失衡来确定，路口可转化为路网上的节点，节点之间的路段可转化为双向线，并在节点和连线上赋予权重信息，整体路网就可以抽象为1个加权有向图。可用式(8)表示：

G=(N,L,W)

(8)

路网的拓扑结构反应路段和交叉口之间的相互关系如图5所示。

图5 区域路网网络图例Fig.5 Legend of regional road network

路网权重可使用有向图邻接矩阵的逻辑结构来表示，一维数组可存储路网中所有节点信息，若节点共有N个，则其对应的邻接矩阵A={aij}在规则路网下是一个N×N的二维矩阵。二维数组中元素为1时，说明对应的两个节点之间有着路段相连，反之则为0，如式(9)所示。

(9)

2.2 深度优先搜索算法

深度优化算法是一种搜索算法，其目的是达到被搜索结构的叶结点。其搜索原理[15]是当与节点v相邻的边全被搜索过，将回溯到发现节点v所在边的起始节点，直到源节点可达到的所有节点，若还存在未被发现的节点，选择其中未被发现的一个节点作为源节点，重复上述过程直到所有节点全部被访问，搜索过程如图6所示。

2.3 失衡路径辨识模型

基于图论的基础理论和DFS算法，构建了一个路网失衡路径的搜索模型。首先，分析路网的拓扑结构，利用有向加权图的数据结构来定义节点和路段的关系，构建路网的基本结构模型；然后，对相关数据进行处理，利用上述供需失衡理论得出相应指标的阈值矩阵TM，与路网结构进行结合得到路网矩阵RM；最后，对重新构建的路网矩阵进行条件标记处理和DFS查找操作，计算和存储查找得到的路径，并将其输出为路网路径图。其流程如图7所示。