首页 理论教育城市道路交通事件疏导策略及影响分析

城市道路交通事件疏导策略及影响分析

【摘要】:基于上述考虑,本书提出了结合蚁群算法及正交试验设计的动态交通网络配流模型,快速生成交通事件疏导配流方案,达到及时疏导、抑制拥堵的目的。因此,为了有效弥补上述两个主要缺陷,本书将通过采用正交试验设计的方法生成初始解,并改进信息素的更新方式及状态转移概率的确定方法,以实现对蚁群算法的优化。

交通事件影响范围的控制区内,实施疏导措施的主要手段为交通管制与交通信号控制,以尽快达到抑制交通流拥堵的目的。然而,实际交通网络中的交通流并非是恒定不变的,而是具有时变的动态性,尤其是在交通事件发生后,这种动态特性尤为突出。因此,为了准确反映交通流的动态特性,制定科学的疏导方案,应以动态交通网络配流为基础,继而依据配流所得的最优解实时调整控制区内的交通管制方案及信号配时方案,最终达到快速缓解交通拥堵的目的。

动态交通网络配流是指在给定交通网络、路段特性函数以及随时间变化的OD 交通率的基础上,获取路网上随时间变化的交通流形态以及走行时间等,将预测所得的短期交通需求进行交通量分配。由于需要考虑时变特性的缘故,传统的动态交通配流模型相对于静态配流模型而言是极其复杂的,无论是求解所需的计算时间还是计算容量都非常巨大,这也大大地削弱了其在工程应用上的可操作性和实用性。而对于道路交通事件的疏导过程而言,疏导措施的时效性尤为重要,它直接决定了措施的有效性。因此,传统的动态交通配流模型无法满足道路交通事件疏导方案生成的要求。

基于上述考虑,本书提出了结合蚁群算法及正交试验设计的动态交通网络配流模型,快速生成交通事件疏导配流方案,达到及时疏导、抑制拥堵的目的。

1.问题描述

将问题可以简单描述为:给定一个多起点多讫点的城市路网,并已知时变起讫点(OD)需求,现有多名出行者进入此路网并需分别从对应的起点到达讫点,要求找出总行程时间最短的路径选择方案。

出行者从起点出发至讫点的路径并非是在起点处一次性决定的,而是每到达一个节点后,再重新选择此节点到终点的路径,直至到达终点。在此出行过程中,出行者的路径选择行为主要由两个因素决定:出行者出行前的路径预测信息及出行中实时路况信息的反馈。当交通流处于自由流状态时,出行者的出行选择行为应主要以出行前的路径预测信息为依据,选择自由流状态下的最短路径;当交通流处于拥挤流状态时,出行者的出行选择行为则应主要以出行中实时路况信息的反馈为依据,选择此时交通量较小、出行距离较短且出行时间较少的路径。

2.相关符号及定义

设城市路网有向图 G = (V  ,E ),其中V 为节点集合,l 为节点,r 为起点,s为终点,且 ∀l  , s ,r ∈ V;E 为路段集合,a 为相邻两节点间的路段,且 ∀a ∈ E;Al 为进入节点l 的路段集合,Bl 为离开节点l 的路段集合。此时,给定研究时段为[0, T],且对于 t [0, T],引入如下变量

(t)表示t 时刻路段a 上要去往终点s 的流量

xa (t)表示t 时刻路段a 上的流量;

(t)表示t 时刻进入路段a 要去往终点s 的流入率;

(t)表示t 时刻离开路段a 要去往终点s 的流出率;

(t)表示t 时刻节点l 产生的要去往终点s 的流率;

ca (t)表示t 时刻路段a 上的瞬时阻抗。

3. 目标函数及约束条件

(1)目标函数

本书以系统最优为动态交通配流原则,即在研究时段内,将动态交通需求分配到路网中,使总行程时间最小。依据此原则,可将目标函数表示如下:

其中,Z 表示路网的总行程时间,路段阻抗函数的确定是动态交通配流的关键所在。以往有不少学者对此进行了深入研究。其中有些学者将静态BPR(The Bureau of Public Roads)函数进行一定的改造推广,用于动态交通网络配流中;但这种方式不仅需要大量真实数据用以标定调节参数,并且很难描绘交通流的真实状况。[30] [31]还有一些学者认为,路段阻抗只与路段流量相关,与路段流入率、流出率均无关,基于此给出了相对应的路段阻抗函数;但这种类型函数的精度及适用性被许多学者所质疑。[32]另外,为使路段阻抗函数能真实地反映道路交通流状况,一些学者采用LWR、元胞自动机、运动波等交通流模型模拟得出阻抗估计值;但这种方式的计算效率较低,实用性不强。[33]由于第三章中所提出的普通城市道路交通事件影响范围预测模型较前面所述的交通流模型,计算更为简易,并能有效地对交通流传播进行模拟,因此,本书将通过采用此模型仿真计算得出路段阻抗值,这样既能有效地提高函数的计算效率,同时又能保证其真实性及计算精度。

依据前文有关章节的描述,可将路段阻抗函数表示如下:

式中,Na 表示t 时刻路段a 上的出行者数,即表示t 时刻第h 位出行者经过路段a 所需要的时间;ca (0)表示初始时刻出行者以自由流速度通过路段a 所需的时间,即ca(0) =,其中da 为路段a 的长度,v 为自由流速度。

(2)约束条件

结合上述问题,给出以下几个约束条件:

①设定初始时刻给定路网的流量为零,即那么在t 时刻路段a 上的流量则可更新为:

②上文引入所有变量均为非负值,即∀a , s ,t ;

③任意节点均满足流量守恒约束,进入该节点的流入量与该节点产生的流量之和等于该节点的流出量,即:

4. 基于正交设计的蚁群算法

蚁群算法作为近年来新兴的一种仿生优化算法,固然具有其他算法不可替代的一些优点,但是与其他算法类似,它同样也具有不可避免的缺点,其中尤以搜索时间长、易陷于局部最优解这两点最为突出。在算法的初始化阶段,由于各路径的信息素量均相等,蚂蚁将在可行解空间内随机选择路径,需通过长时间的搜索进行信息素的更新和累积,得出此时的较优路径,即使有分布式并行计算机制的作用仍无法避免其运行效率低下的问题。另外,蚂蚁是通过信息素的反馈进行路径搜索的,在此过程中,当出现所有蚂蚁搜索的解趋于一致时,搜索即会面临停滞,此时极可能出现陷入局部最优解、错过全局最优解的情况。因此,为了有效弥补上述两个主要缺陷,本书将通过采用正交试验设计的方法生成初始解,并改进信息素的更新方式及状态转移概率的确定方法,以实现对蚁群算法的优化。

(1)算法描述

由于正交设计法均匀分散、齐整可比的特性,一个正交数组即指定了一个均匀散布在所有解组合空间中的最小数量的组合。若将正交设计用于优化蚁群算法的初始化过程,则能使初始解均匀分布于可行解空间中,实现在可行解空间内的均匀搜索,确保全局最优解的生成,有效地避免其在获取局部最优解后停滞不前的情况发生。另外,由于通过正交设计法可以获取极少数量、具有代表性的初始解的组合,这便大大提高了搜索初始解群的效率,有效地缩减了搜索时间。因此,正交设计法可以使蚁群算法在收敛速度及搜索最优路径方面均得到明显改善。

具体算法描述如下:

①令任意路段(i, j)的初始信息素量 τij( 0)= c′(c′为一常数),且令初始信息素增量 Δτij( 0 )= 0。

②在已知给定路网中OD 对数量k 及各OD 对间可选路径数m 的情况下生成正交表构造一个方案数为n 的路径分布表。

③依据初始时段的OD 需求量设定初始蚂蚁数量,并分别将蚂蚁放置于各个起始节点的位置。

④令初始蚂蚁随机选择任意起点r 作为初始位置,并分别依据起点r 所对应的正交路径方案,使蚂蚁逐步从起始节点s 转移至讫点s 为止。

⑤每只蚂蚁独立完成从起点r 到讫点s 的搜索过程,并且任意节点l 都仅能被访问一次。

⑥对蚂蚁所经过的路段进行局部信息素更新,并依据流量更新公式对各个时间段的路段交通流量进行更新。⑦转至④,直至所有隶属于起讫点(r, s)上的蚂蚁均从起点到达终点为止。⑧将初始蚂蚁的数量重置,并依次根据n 个正交路径方案,进行新一轮的搜索,直至所有蚂蚁完成n 次迭代为止。

⑨依据由正交数组所决定的路径确定每条路段所对应的初始解xa (t),并利用普通城市道路交通事件影响范围预测模型仿真计算每组初始解所对应的阻抗函数值 (t)(第h 只蚂蚁所对应的路段a 的阻抗值),进而得出各组初始解所对应的目标函数值。

⑩统计得出每个OD 对下,各条可选路径对目标函数的影响值,并依据统计结果,从各个OD 对中选取最优路径,然后对各条最优路径进行全局信息素更新。

⑪将最优路径重新组合,生成最终的初始方案,得出此时的目标函数值记为Z*,对应的解记为(t)。

⑫依据相应的OD 需求量重置下一时段的蚂蚁数量,并将蚂蚁重新放置于起始节点的位置。

⑬依据状态转移规则进行路径选择,并对蚂蚁所选路段进行局部信息素更新,同时对流量进行更新。

⑭进一步搜索路径,直至所有蚂蚁到达对应的终点,确定此时每个OD 对下的最优路径,并对其进行全局信息素更新。

⑮转至⑩继续迭代,直至所有研究时段的蚂蚁均从起点到达终点为止。

(2)信息素量更新方式

依据蚁群算法的基本原理,蚂蚁会在经过某条路径时释放一定数量的信息素,而这种信息素是蚂蚁选择路径的一种启发因子。当某路径出行成本越小,信息素量就会越大,吸引的蚂蚁数就会越多,继而进一步地增加该路径信息素的数量,这将直接导致其他启发因子的作用被忽略,且由于该路径的蚂蚁数量聚集过多而导致其出行成本上升。为避免此情况发生,本书将信息素量更新方式设定如下:

①全局信息素量更新方式

在每次循环之后,需对路径进行信息素量的更新,此处选择采用蚁群系统(Ant Colony System)的全局更新方式,不再对所有路径进行更新,而是只对本次循环中的最优路径更新。具体方式可用下式来描述:

式中,τij 为路段(i, j)上的信息素量,∂为路径上信息素的挥发系数,Δ为OD 对(r, s)间路段(i, j)上信息素的增量,为本次循环中OD 对(r, s)间的最优路径长度。

②局部信息素量更新方式

在所有蚂蚁完成一次路径选择后,可按下式对路段进行信息素量的更新:

式中,Δτij 为蚂蚁完成一次转移后的路段(i, j)上信息素的增量。Δτij 通常有三种取值方式:为初始时刻路段(i, j)上的信息素量;为第k 只蚂蚁在访问完节点j 后需访问的城市集合。经研究分析得出,第一种取值方式在求解性能方面通常比后两种取值方式要差,而后两种取值方式在性能方面的表现相差甚少,但由于第②种方式所需的计算量较小,因此通常采取Δτij = Δτij (0)的这种方式用于局部更新。即可将上式更新表示为:

③确定状态转移概率

基于上文的问题描述,此处的状态转移概率即为出行者在路径选择中选择下一节点的概率。此概率值除了由蚂蚁之间相互协作所依据的信息素来决定外,路段流量及其路段长度也是主要影响因素。因此,可将此处的状态转移概率表示如下:

式中, (t)为t 时刻蚂蚁k 在节点i 处选择转移至节点j 的概率;ηij 为路段长度dij 的倒数,即为路段流量qij 的倒数,即(当qij = 0 时,取εij = 1);allowedk 为位于节点i 处的蚂蚁k 下一步所能选择的节点集合;β 为一个启发性参数,表示包括路段长度和路段流量在内的其他启发因子相对于信息素的重要程度(β >0)。通过此式可得,出行者将会更倾向于选择信息素量较大、路段长度较短、交通流量较小的路段。

为了使出行者在路径选择中更大可能地选择启发因子及信息素量均较大的路段,本书采用伪随机比例规则来实现下一节点的选择,即设定一概率值P0(0 ≤P0 ≤1),并取一随机数P(0 ≤P ≤1)。当P ≤P0 时,位于节点i 的出行者k 将选择转移至信息素量最大且启发因子最大的节点;而当P >P0 时,位于节点i 的出行者k 将依据式5.15 选择下一步转移的节点。此时出行者从节点i 转移至节点j 的状态转移规则可表示如下:

式中,J 表示依据式5.15 所决定的随机变量

5. 算法实现步骤

下面将算法的具体实现步骤设计如下:

Step1 初始化。令时段nc = 1,并设置离散时间段的总数为Nc,并令任意路段(i, j)的初始信息素量 τij( 0)= c′(c′为一常数),且初始信息素增量Δτij( 0 )= 0。

Step2 确定蚂蚁数量。依据初始时段的OD 需求量设定初始蚂蚁数量,并分别将蚂蚁放置于起始节点的位置。

Step3 生成初始解。依据给定路网中的起讫点,运用正交实验设计法产生一组蚂蚁搜索的初始路径方案,令所有初始蚂蚁完成搜索后,根据式5.14 对所选择路段上的信息素量进行更新,并通过计算分析对比得出最小目标函数值、初始解及最优路径。

Step4 更新全局信息素量。根据式5.11、式5.12 分别对各OD 对下的最优路径的信息素量进行更新。

Step5 重置蚂蚁数量。依据相应时段的OD 需求量重新设定蚂蚁数量,并分别将蚂蚁放置于各个起始节点的位置。

Step6 路径选择。根据式5.15 及式5.16 的状态转移规则,使蚂蚁逐步从起始节点转移至终点。

Step7 更新局部信息素量及流量。根据式5.14 对蚂蚁所选择路段的信息素量进行更新,并依据式5.9 更新路段的交通流量。

Step8 转至Step4,直至所有OD 对中的所有蚂蚁均完成从起点到终点的转移。

Step9 令nc = nc+1,若此时nc <Nc,则转至Step4;若nc = Nc,则循环结束,完成所有时间段的搜索工作。

Step10 输出最优解,即输出各时间段各路段上的交通流量。

6. 算法的程序结构流程

图5-3 基于正交设计的蚁群算法的程序结构流程图

根据上文所述,将算法的程序结构流程图绘制如图5-3 所示。