随着世界范围的城镇化发展,大型城市交通拥堵现象越来越严重,不仅影响人们的工作效率,带来很大经济损失,还造成严重的环境污染和安全事故,给人们的生命健康带来很大威胁.在现有城市空间扩容有限的情况下,如何充分利用现有交通道路资源、缓解城市拥堵现象,已成为现代城市发展中亟待解决的一个热点问题^[1].

目前,缓解城市交通拥堵的主要方法如下:

(1) 调控交通灯的动态优化,比如SCATS(sydney coordinated adaptive traffic system)^[2]和SCOOT(split cycle offset optimization technique)^[3]系统.该类方法主要从宏观交通流角度疏散交通拥堵,通过加快行驶车辆的流通速度来提高道路资源的利用率,但没有考虑到每个微观行驶车辆的不同交通需求;

(2) 单个行驶车辆的路径导航算法主要有:确定性算法,包括A算法^[4]、Dijkstra最短路径算法^[5]、动态规划算法^[6]等;智能算法,包括PSO算法^[7]、遗传算法^[8]、蚁群优化算法^[9]、神经网络算法^[10]等;基于当前交通状况寻优算法,比如TomTom^[11]、Google导航^[12]等.上述方法均为非协商类算法,其问题在于:为每个车辆提供最优路径的时候没有考虑到车辆间的相互影响,因而可能会导致很多车辆涌入相同路段,造成新的交通拥堵,反而延长了车辆行驶时间;

(3) 基于车辆或路径数据的寻优方法.为了将车辆分散在不同路径以缓解交通拥堵现象,有的学者根据车辆行驶的历史路径数据,选择行驶时间相近的一组路径并依据概率推荐给行驶车辆^[13];或者基于路径的拥堵程度进行定价来引导车辆选择行驶路径^[14];或者通过与路网中心的互动博弈^[15]来进行车辆的路径选择.

以上方法对于分散交通流从而减轻交通拥堵程度起到了一定作用,但是这些方法要么是基于静态数据,车辆的路径选择不是基于动态的交通信息且缺乏协作;要么是计算效率较低,不能提供快速精确的路径选择.而且以上方法中,车辆主要是基于行驶时间来进行路径选择,没有考虑到更多的偏好指标,缺乏灵活的个性化选择.

为了克服以往研究中路径选择指标单一化、精度不足、缺乏动态协作等问题,本文引入多Agent系统,将城市路网中的每个行驶车辆构成由多个自治Agent组成的分布式系统^[16],每个车辆Agent具有自调节和协作的特点,可以基于车用自组网VANET^[17]彼此之间进行有效实时的信息交换.为提高路径选择的精度,车辆行驶至每个路口,都要结合对前方路径的不同偏好以及实时交通信息进行动态更新路径.每个车辆都希望选择自己偏好的路径来最优化自己的效用,但为了减少多个车辆进行路径选择时彼此间的相互影响,需要每个车辆根据各自可选路径集合,并结合实时交通路况信息,彼此之间进行协作^[18].假设每个车辆知道自己的可选路径集合和已实现效用,但对于未选择的路径效用并不了解,那么整个城市路网中的所有行驶车辆如何协作才可以使得各自效 用达到最优,同时整个路网的效用达到最大化,这是一个基于非完全信息的随机拥堵博弈问题^[19].在该博弈的学习过程中,参与者在一系列的阶段不断重复地进行博弈.在每个阶段,参与者使用历史经验及观察来选择当前阶段的策略.经过长期选择行为,参与者的策略会以很高的概率收敛于Nash均衡^[20].本文将城市路网中的多个车辆间的协作过程描述为一种随机拥堵博弈,并提出一种自适应学习算法,为多个车辆路径选择方案收敛于Nash均衡提供思路,在保证车辆个体效用最优的同时,最大化城市路网的效用.

综上,本文主要工作可以总结如下:

(1) 创建了城市交通路网动态实时多路口路径选择模型DR²SM(dynamic and real-time route selection model in urban traffic network),通过同时考虑多个路口多个车辆的路径选择策略,可以有效地避免彼此之间的路径冲突,为行驶车辆提供更加精确的个性化路径选择;

(2) 提出了一种行驶车辆对可选路径效用值的计算方法,既考虑了车辆对于路径选择的不同偏好及动态不确定实时路况信息,又将对于道路交通状况的影响考虑在内,极大地提高了车辆路径选择的精度和有效性;

(3) 提出了一种自适应学习算法SALA(self-adaptive learning algorithm),利用车辆彼此之间的信息交互及协商,实现行驶车辆的动态路径选择策略达到Nash均衡,在保证车辆的偏好前提下,将交通流均匀分布在可选路径上,使得城市交通路网道路资源应用效率最大化.

本文第1节介绍相关研究工作.第2节详细介绍DR²SM模型以及行驶车辆对路径效用值的计算方法.第3节介绍行驶车辆进行动态路径选择的自适应学习算法SALA,并对其收敛性进行说明.第4节将DR²SM模型在人工路网和真实的城市交通路网中进行验证,证实其有效性.第5节对全文进行总结,并对未来工作进行展望.

1 相关工作

为充分利用城市道路资源,降低车辆平均延迟时间,Hui等人结合PSO算法对交通管理策略进行优化,通过交叉口控制信息对车辆进行动态路径导航^[21].Hajiahmadi等人将城市路网分成若干区域,对每个区域的宏观交通流进行预测,为区域间的车辆进行动态路径导航,避免相邻区域间的拥堵,降低了集中控制的计算规模^[22]. El-Tantawy等人引入强化学习算法,使得交通灯信号根据实时交通状况彼此协调并进行适应性调节,从而最小化交通时延^[23].徐杨等人提出了一种基于多智能体的交通灯分布式绿波自适应控制方法,通过一个非集中式的协同智能体来控制交通灯,增大交通流的通行^[24].然而,以上方法主要从宏观交通流角度进行路径诱导,没有考虑到微观车辆的个性化行驶需求.

为提高传统PSO算法的全局搜索能力和收敛速度,Li等人提出一种量子PSO算法^[7],对车辆进行路径规划.通过结合模糊推理技术的层次分析法,Li等人将交通过程中需要考虑的因素进行精确化建模,并对行驶车辆进行动态路径导航^[25].Arokhlo等人和Zolfpour-Arokhlo等人提出一种基于多Agent强化学习算法的路径规划模型,将车辆行驶过程中的多影响因素以不同权值的方式考虑进来,为行驶车辆寻找最优路径^{[5, 26]}.Negulescu等人和Zafar等人结合蚁群优化算法对车辆路径进行规划和探索^{[9, 27]}.曹政才等人提出一种基于交通流量预测的路径寻优方法,结合一种高效的动态改进A路径搜索算法提高车辆的行驶效率 ^[28].以上方法均为非协商类算法,对于降低单个车辆的行驶时间有一定效果,但没有考虑到多车辆在同时进行路径选择时彼此之间的路径选择影响.

为了避免车辆因为选择相同路径而造成新的拥堵现象,Yamada等人提出基于超路径的路径推荐方法,选择行驶时间相近的一组路径并依据概率推荐给行驶车辆,将交通流分散在一组相似路径上^[13].但该方法不是基于动态的实时交通信息,而是静态的历史交通数据.Pan等人根据实时交通信息,尽量将车辆分散到车流量较低的路径^[29],但没有充分利用实际最短路径的容量,从而会导致有些车辆被诱导到很远的路径.Wang等人通过交通灯收集实时交通信息,并对突发交通拥堵事件进行规避,将车辆均衡分散在整个路网^[30].但该论文考虑的是交通灯及相关路段间的协作,并没有考虑微观车辆的行驶需求.Liang等人从微观车辆角度进行路径导航,通过比较车辆对整个路网交通的影响程度进行排序导航,降低了车辆的平均行驶时间^[31].但该方法没有考虑到车辆彼此间的协作.Wang等人和Zhu等人通过定价策略及动态toll政策对车辆进行路径导航^{[14, 32]}.Groot等人应用扩展的反Stackelberg博弈,使得交通中心引导司机选择能达到系统最优的路径^[15].Adler等人通过路网管理者、信息中心以及车辆之间的协作,寻找一种在时空上充分利用路网容量的有效路径分配方案^[33].以上方法主要是主从式的博弈,类似集中式的Agent协作,计算效率不高.Desai等人基于虚拟Agent协商进行车辆间的路径导航,以此来规避交通拥堵^[16].通过对比3种协商模式研究车辆的个体利益和整个城 市路网利益间的关系.不过该论文没有考虑到多路口车辆同时进行路径选择时路段间交通容量的关联和影响,也没有考虑到突发交通事件对车辆路径选择的影响.

综上,现有的基于城市路网的车辆路径选择研究中存在路径选择指标单一化、精度不足、缺乏动态协作等问题.为此,本文首次构造了一个城市交通路网的动态实时多路口路径选择模型DR²SM,有效描述了多个路口多个车辆同时进行路径选择时的动态策略;提出了一种行驶车辆可选路径效用值的计算方法,既考虑了车辆对于路径选择的不同偏好及动态不确定的实时路况信息,又将对于路径交通状况的影响考虑在内,大大提高路径选择的精度和有效性;提出了一种解决多个车辆进行路径选择时存在的冲突问题的自适应学习算法SALA,在保证车辆的偏好前提下,将交通流均匀分布在可选路径上,使得城市交通路网道路资源应用效率最大化.

2 DR²SM 模型

以往研究中没有针对城市交通路网中的实时交通信息,也没有考虑到多路口车辆选择路径时彼此间的相互影响,为此,本文提出城市交通路网动态实时多路口路径选择模型DR²SM,如图 1所示.相对于其他交通模型,本模型是针对城市路网中多路口的大量车辆同时进行动态路线导航的模型;基于实时动态的交通信息进行路线导航,需要考虑的因素非常多,不仅包括司机对道路的客观属性及主观偏好,还需要考虑到路线选择对应的耗费成本,以及道路上可能出现的突发事件等不确定因素;行驶车辆彼此间通过信息交互寻找个体最优路径,在满足行驶车辆个体利益的同时,实现整个城市路网道路资源利用率的最大化.第2.1节具体描述了模型定义.第2.2节给出了效用计算的具体过程.

2.1 问题模型

给定的城市交通路网可以被建模成有向图G(L,E),L是路口集合,E是路口之间的路段集合,如图 2所示.假设城市交通路网中路口数量为m,l_x(x=1,2,…,m)表示第x个路口,则L={l₁,l₂,…,l_m}.对任意相邻路口l_x和l_y,(l_x,l_y)E表示一条从路口l_x可以直接到达路口l_y的路段.因为城市交通路网中有些路段是单向道,所以如果(l_x,l_y)E,不表示(l_y,l_x)E一定成立.In(l_x)表示能直接开往路口l_x的所有邻居路口集合,Out(l_x)表示从路口l_x开出能 直接到达的所有邻居路口集合.Turn(l_x,l_y)表示从路口l_x开往l_y的车辆可以转向的路口集合,如果从路口l_y可以返回l_x,则Turn(l_y,l_x)=Out(l_y)-{l_x};如果从路口l_y不可以返回l_x,则Turn(l_y,l_x)=Out(l_y).

在以上城市交通路网中行驶车辆的数量设为n,所有的行驶车辆集合表示为N={1,…,i,…,n}.其中,第i个行驶车辆的起点路口和终点路口分别表示为o_i和d_i.在当前时刻t,该车辆已经过的路口集合、刚驶离的路口和即将驶向的路口,分别用$Q_{i}^{t},f_{i}^{t}$和$g_{i}^{t}$来表示.当该车辆驶向路口$g_{i}^{t}$时,根据对前方可选路径的偏好和成本的综合估计,并结合通过实时监控得到的交通状况信息,选择一条可选路径进行转向,用l_k表示该车辆在下一个时间步选择转向的路口,即${{l}_{k}}\in Turn(f_{i}^{t},g_{i}^{t})$;用Action(i,t)表示该车辆在当前时刻t的转向动作,则:

$Action(i,t)=\{(g_{i}^{t}\to {{l}_{k}})|{{l}_{k}}\in Turn(f_{i}^{t},g_{i}^{t})\}$

用$R_{g_{i}^{t},{{d}_{i}}}^{k}$表示在当前时刻t,第i辆车驶向路口$g_{i}^{t}$并经由路口l_k,到达目的地d_i的所有可选路径集合,其中,第h条可选路径表示为$r_{g_{i}^{t},{{d}_{i}}}^{k,h}$,该路径的路段数表示为$s_{g_{i}^{t},{{d}_{i}}}^{k,h}$.

在考虑前方路径可能出现的不确定因素以及该路径的行驶状况及对其影响等情形下,为了选择较偏好的路径,各路口待转向的车辆需同时考虑对可选路径的偏好值、不确定因素值以及耗费成本值,最后可得车辆对可选路径的效用值.这里,用效用函数$u_{g_{i}^{t},{{d}_{i}}}^{k,h}$表示在当前时刻t,第i辆车驶向路口$g_{i}^{t}$并转向路口l_k,经由第h条可选路径到达目的地d_i对应的效用值,定义如下:

$u_{g_{i}^{t},{{d}_{i}}}^{k,h}=p\times P_{g_{i}^{t},{{d}_{i}}}^{k,h}-b\times B_{g_{i}^{t},{{d}_{i}}}^{k,h}-c\times C_{g_{i}^{t},{{d}_{i}}}^{k,h},p,c,b\in (0,1)$

(1)

其中,$P_{g_{i}^{t},{{d}_{i}}}^{k,h},B_{g_{i}^{t},{{d}_{i}}}^{k,h},C_{g_{i}^{t},{{d}_{i}}}^{k,h}$分别表示车辆对于相应可选路径的偏好值、不确定因素值以及耗费成本值;p,b,c是乘法因子,分别表示待转向车辆在选择可选路径时偏好值、不确定因素值以及耗费成本值的权重比例.根据行驶车辆所在地侧重的不同城市交通路网标准,比如车辆通行效率、行驶安全性等,p,b,c分别取不同的值.p,b,c的取值取决于城市规模和路网车流量等因素,当城市规模较大、对应的路网车流量较大的情况下,车辆行驶侧重通行效率,会首先考虑尽量避开较拥堵路径,其次考虑对路径的偏好,此时b,c的取值偏大,p的取值偏小;当城市规模偏小、对应的路网车流量偏小的情况下,车辆行驶侧重较偏好的路径,此时p的取值偏大,b,c的取值偏小.基于以上原则,p,b,c的具体取值在多次实验探索中可取得最优值.行驶车辆对可选路径的效用值越大,则选择该路径的可能性越大.

为了在考虑对可选路径偏好的基础上,均匀分布在相应可选路径上不造成交通路网的拥堵,各路口的多个车辆在转向前的当前时刻t,根据得到的前方实时交通信息,通过信息交互进行拥堵博弈,并基于自适应学习算法SALA选择行驶路径,使得在确保各自耗费成本(包括时间、距离及耗油量等)不超过预期阈值的情况下,各行驶车辆的路径选择策略达到Nash均衡,同时使城市路网道路资源应用效率达到最大化.根据以上描述,城市交通路网多路口实时动态路径选择模型即为求解如下参数优化问题.

$\left. \begin{align} &u_{i}^{t}(r_{i}^{{{t}^{*}}},r_{-i}^{{{t}^{*}}})\ge u_{i}^{t}(r_{i}^{t},r_{-i}^{{{t}^{*}}}),\forall r_{i}^{t}\in R_{i}^{t} \\ &\text{s}\text{.t}\text{. }time_{g_{i}^{t},{{d}_{i}}}^{k,h}\le t\_M_{g_{i}^{t},{{d}_{i}}}^{k}|{{\pi }^{*}}(i,t); \\ &\text{ }dist_{g_{i}^{t},{{d}_{i}}}^{k,h}\le d\_M_{g_{i}^{t},{{d}_{i}}}^{k}|{{\pi }^{*}}(i,t); \\ &\text{ }oil_{g_{i}^{t},{{d}_{i}}}^{k,h}\le o\_M_{g_{i}^{t},{{d}_{i}}}^{k}|{{\pi }^{*}}\left( i,t \right). \\ &\text{ }(i=1,2,...,n;{{l}_{k}}\in Turn(f_{i}^{t},g_{i}^{t});h=1,2,...,R_{g_{i}^{t},{{d}_{i}}}^{k}) \\ \end{align} \right\}$

(2)

其中,$r_{i}^{{{t}^{*}}}$表示当前时刻t,第i个车辆选择的最优路径;$r_{-i}^{{{t}^{*}}}$表示当前时刻t,除了第i个车辆的其他所有车辆的路径选择策略所组成的向量;$u_{i}^{t}$为当前时刻t,第i个车辆路径选择的效用值;$R_{i}^{t}$为当前时刻t,第i个车辆的可选路径集合;p(i,t)表示在当前时刻t,第i个车辆针对其他车辆路径选择的最优策略;$t\_M_{g_{i}^{t},{{d}_{i}}}^{k},d\_M_{g_{i}^{t},{{d}_{i}}}^{k},o\_M_{g_{i}^{t},{{d}_{i}}}^{k}$及$time_{g_{i}^{t},{{d}_{i}}}^{k,h},dist_{g_{i}^{t},{{d}_{i}}}^{k,h},oil_{g_{i}^{t},{{d}_{i}}}^{k,h}$分别表示在当前时刻t,第i个车辆驶向路口$g_{i}^{t}$并转向路口l_k到达目的地d_i对应的耗费时

间成本阈值、耗费距离成本阈值、耗油量成本阈值,以及经由其中的第h条路径到达目的地对应的预期耗费时间成本值、耗费距离成本值、耗油量成本值.

2.2 效用计算

车辆在行驶的过程即将转向时,对未来的路径选择标准不仅依赖于该路径的距离和行驶时间,还会同时考虑其他因素,比如该路径所包含的路段的一些客观属性,包括车道数、是否有人行横道、照明设备是否充足等,以及司机对于道路的不同主观喜好.这些因素综合起来就构成了车辆对某条路段的偏好,具体参数见表 1.

根据表 1中描述的相关参数,可将它们进行权重组合计算一条路段的偏好值P,计算如下:

$P=alt\acute{\ }w1+lan\acute{\ }w2+sdw\acute{\ }w3+lgt\acute{\ }w4+cpl\acute{\ }w5+fmy\acute{\ }w6$

(3)

其中,w1~w6表示相应参数对应的独立权值乘法因子,因子越大,表示对应的参数相对越重要,它们的和为1.一条路径的偏好值为该路径上所有路段的偏好值之和,计算出来的偏好值越大,表示待转向车辆对该道路的偏好越高,对应的道路就越容易被选中.

在车辆行驶过程中,前方道路有时候会出现一些突发事件,比如交通事故、临时管制等,这些事件构成了车辆选择道路时要考虑的不确定因素,具体参数描述见表 2.

对于每个不确定因素值的计算,主要考虑该突发事件对于整个路段交通的影响程度.比如,对于突发交通事故这个不确定因素:如果交通事故影响程度非常大,导致该路段的车辆无法继续通行,则该值可设为INF,表示车辆转向时不会选择该路段;如果有交通事故,但对该路段的交通影响不是很大,依然可以让部分车辆顺利通行,则该值为[0, 1]之间,依据事故的严重程度取值,该值越大,表示事故越严重,对路段交通影响越大.对于临时管制等其他突发事件对应的不确定因素值,计算过程类似.根据对不同突发事件设定的值,可以计算该路段对应的不确定因素值B,如下所示:

$B=accident\acute{\ }a1+activity\acute{\ }a2$

(4)

其中,a1,a2表示相应参数对应的独立权值乘法因子,因子越大,表示对应的参数相对越重要,它们的和为1.一条路径对应的不确定因素值即为各路段对应的不确定因素值之和,计算出来的不确定因素值越大,表示待转向车辆选择该道路的可能性越低.

行驶车辆在对可选路径的偏好值和不确定因素值已确定的情况下,还需要考虑各路径的行驶状况.当车辆选择某路径进行转向时,会增加被选择路径的车流量,即,对该路径的行驶状况造成一定的影响,同时也被该路径已有的拥堵状态所影响.这种影响包括车辆的行驶时间、距离及耗油量等,称为该车辆选择该路径所付出的成本代价,包括预期耗费时间成本、预期耗费距离成本、预期耗油量成本等.具体参数描述见表 3.

以上参数中:预期耗费距离成本的计算比较简单,只是该路径的实际长度与期望长度的比值;而预期耗费时间成本和预期耗油量成本则相对复杂,与相应路径的拥堵状况有关.为了表示相应路段对应的拥堵状况,本文引入拥堵系数t,该系数的值与路面上的实际车辆数q和该路段的阈值容量Y和堵塞容量D有关.一般来说,道路越拥堵,该道路对应的交通拥堵系数越大,不同阶段的车流量状态(包括自由流、半自由流、堵塞流等)对于交通拥堵系数的增加幅度也是不一样的.具体计算公式如下:

$\tau =\left\{ \begin{array}{*{35}{l}} 1,\text{ }q＜Y \\ q/Y,\text{ }Y\le q＜D \\ D/Y+{{e}^{q/D}},\text{ }D\le q \\ \end{array} \right.$

(5)

该路段的预期耗费时间可以计算为该路段的平均行驶时间与该路段的拥堵系数的乘积,而一条路径上的预期耗费时间成本为各路段上的预期耗费时间之和与该路径的期望时间的比值.类似的,该路径对应的预期耗油量成本为各路段上的预期耗油量之和与该路径的期望耗油量的比值.综合上面已计算出来的各预期耗费成本值,可以计算一条路径对应的耗费成本值C,具体如下:

$C=time\acute{\ }t1+dist\acute{\ }t2+oil\acute{\ }t3$

(6)

其中,t1~t3表示相应参数对应的独立权值乘法因子,因子越大,表示对应的参数相对越重要,它们的和为1.计算出来的耗费成本值越大,表示待转向车辆选择该道路的可能性越低.

3 面向拥堵博弈的自适应学习算法

为了使行驶车辆能智能感知实时交通信息并通过彼此协商进行路线选择,本文引入多Agent系统对行驶车辆进行仿真,并对其动态路径选择策略进行优化,使得整个路网中的多个车辆通过随机拥堵博弈,并结合马尔可夫学习过程,探索寻求各自最佳路径,最终达到混合Nash均衡,降低车辆的平均行驶时间,同时使城市路网的道路使用效率达到最大.第3.1节描述了交通流及效用值之间的计算关系.第3.2节描述了车辆间的随机拥堵博弈相关概念.第3.3节具体描述了车辆Agent在拥堵博弈过程中的自适应学习算法.

3.1 交通流和效用值

为表示城市路网中交通流与行驶车辆选择某条路径的效用值之间的关系,本文定义了以下符号和术语. N={1,…,i,…,n}表示n个行驶车辆Agent集合.R_i={1,…,h,…,M_i}(iN)表示第i个车辆Agent的可选路径集,R_-i表示除第i个车辆Agent外的其他所有车辆Agent的路线选择策略集合.若两个车辆的起点和终点相同,则它们的可选路径集也相同.r_iR_i表示第i个车辆Agent的路径选择策略,r_-iR_-i表示其他车辆Agent的路径选择策略组合.所有车辆的路径选择策略可以表示为向量$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r}=({{r}_{1}},...,{{r}_{i}},...,{{r}_{n}})\in R$或者$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r}=({{r}_{i}},{{r}_{-i}})\in R$,其中,R=R₁xR₂x…xR_n. ${{u}_{i}}(\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r}):R\to \mathbb{R}$表示所有车辆Agent的路径选择策略$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r}$下,第i个车辆Agent所获得的效用值.从上一节车辆路径

选择对应的效用值计算过程可以得知:行驶车辆选择某条路径的效用值,除了车辆对该路径的偏好以及对应的不确定因素之外,主要和该路径上各路段的交通流量有关.而该值又取决于各车辆的路径选择策略,因此有如下定义.

已知E是城市路网内所有路段集合,定义q_e表示路段eE上的交通流量.车辆i(iN)的可选路径集R_i2^|E|,其中一条可选路径hR_i,由若干路段eh组成.在t时刻,车辆i访问可选路径h(hR_i)的次数是一个0-1函数,定义如下:

$z_{i,h}^{t}=1\{r_{i}^{t}=h\}$

(7)

其中,1{×}是一个指示函数:如果大括号里的判断成立,则取值为1;否则为0.因此,可以得到t时刻路段eh的交通流量为

$q_{e}^{t}=\sum\nolimits_{i\in N}{\sum\nolimits_{h\in {{R}_{i}}}{\delta _{i,h}^{e}}}z_{i,h}^{t},\forall e\in E$

(8)

其中,$\{\delta _{i,h}^{e}\}$表示某个路段与路网中所有车辆可选路径的关系矩阵.其中,元素$\delta _{i,h}^{e}$表示路段e与第i个车辆的第h条可选路径的关系:如果路段e包含在第i个车辆的第h条可选路径中,则该值为1;否则为0.各行驶车辆在时刻t将可选路径集及对各可选路径的偏好值发送至信息中心,由信息中心结合城市路网实时交通信息,在每个博弈阶段将各车辆的可选路径选择进行一次组合,进而对各路段交通流量进行计算.假定每个车辆都是根据以往历史经验按照某一个固定概率彼此独立进行路径选择,并且每个车辆都可以观察到其他车辆的路径选择,结合上一节的效用计算公式,即可计算出车辆i在时刻t对选择路径的平均效用$u_{i}^{t}(r_{i}^{t},r_{-i}^{t})$.为了使车辆的随机路径选择过程趋向稳定,加上一个由随机选择产生的噪音$\varepsilon _{i}^{t}(r_{i}^{t})$,即构成车辆i在时刻t的已知效用$U_{i}^{t}$,如下所示:

$U_{i}^{t}=u_{i}^{t}(r_{i}^{t},r_{-i}^{t})+\varepsilon _{i}^{t}(r_{i}^{t})$

(9)

假定在每个时刻t,所有车辆都观测到前面每个时刻(0,…,t-1)选择路径的已知效用,并参照该信息选择时刻t的路径.根据在前面每个时刻的已知效用值,可以得到在时刻t车辆i对于路径h的估测效用(该效用值即为车辆i进行路径选择的最大化目标)为

$\hat{u}_{i,h}^{t}=\frac{1}{Z_{i,h}^{t}}\sum\nolimits_{s=0}^{t-1}{U_{i}^{s}}z_{i,h}^{s}$

(10)

其中,$Z_{i,h}^{t}$表示直到时刻t为止(不包括该时刻)车辆i访问路径h的次数,定义如下:

$Z_{i,h}^{t}=\sum\nolimits_{s=0}^{t-1}{z_{i,h}^{s}}$

(11)

结合公式(10)和公式(11),可以得到公式(12),即,车辆i根据前一时刻对于路径h的估测效用以及当前时刻t获知的已知效用,可得到当前时刻t路径h的估测效用:

$\hat{u}_{i,h}^{t}=\hat{u}_{i,h}^{t-1}+\frac{1\{r_{i}^{t-1}=h\}}{Z_{i,h}^{t}}(U_{i}^{t-1}-\hat{u}_{i,h}^{t-1})$

(12)

3.2 随机拥堵博弈

当城市路网中的所有车辆在接近路口进行最佳路径选择时,基于可选路径的估测效用进行协商,这个协商过程称为随机拥堵博弈.在博弈过程中,每个车辆基于自适应学习算法选择最大化估测效用的可选路径,以较高的概率达到混合Nash均衡.在自适应学习算法里,包括一个效用学习和策略学习同步更新方案,同时更新Logit模型参数.然而,当前车辆无法获取未选择路径的效用值,因此,该算法依赖于估测效用的最佳响应函数,并且该响应函数由一个随机近似理论递归更新.

3.2.1 混合Nash均衡

本文用混合策略$\pi _{i}^{t}({{r}_{i}})$表示车辆i在时刻t选择可选路径r_i的概率,即:

$\pi _{i}^{t}({{r}_{i}})=\Pr [r_{i}^{t}={{r}_{i}}]$

(13)

其中,对于车辆i的任意一条可选路径1≤h≤M_i,都有$0\le \pi _{i}^{t}(h)\le 1$并且$\sum\nolimits_{h=1}^{{{M}_{i}}}{\pi _{i}^{t}(h)}=1$.假定每个车辆都认为其他车辆会根据混合策略独立进行路径选择,那么车辆i在基于混合策略空间$\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {\pi }$里的平均效用为

${{u}_{i}}(\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {\pi })={{E}_{\pi }}[{{u}_{i}}(\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r})]=\sum\nolimits_{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r}\in R}{{{u}_{i}}(\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r})}\prod\nolimits_{j\in N}{{{\pi }_{j}}({{r}_{j}})}$

(14)

当每个车辆相对其他车辆的路径选择策略来说都是最佳路径时,则达到了混合Nash均衡,即满足:

${{u}_{i}}({{\pi }^{*}})={{\max }_{{{r}_{i}}\in {{R}_{i}}}}{{u}_{i}}({{r}_{i}},\pi _{-i}^{*})$

(15)

3.2.2 最佳响应函数

当城市路网中的车辆行驶到各路口进行路径选择时,因为彼此间的选择会相互影响,每个车辆都是基于对可选路径的估测效用${{\hat{u}}_{i}}(h)$来进行最佳路径选择,所以它们会基于概率来进行选择,而不是确定性选择.根据各车辆进行路径选择的概率以及对应的可选路径估测效用,每个车辆通过一个最佳响应函数来确定自己的最佳响应,以期找到路径选择的Nash均衡点.基于文献^[34],定义车辆i选择路径的最佳响应函数为

$\gamma _{i,h}^{t}=\arg {{\max }_{{{\pi }_{i}}\in {{\Sigma }_{i}}}}\left[ \sum\nolimits_{h\in {{R}_{i}}}{\pi _{i,h}^{t}\hat{u}_{i,h}^{t}+{{\mu }_{i}}{{\psi }_{i}}(\pi _{i}^{t})} \right]$

(16)

其中,m_i>0是一个与用户相关的光滑参数,而y_i:(R_i) 是车辆i的个体信息,是一个光滑严格可微凹函数,有关个体信息函数的典型例子就是熵函数:

${{\psi }_{i}}({{\pi }_{i}})=-\sum\nolimits_{h\in {{R}_{i}}}{{{\pi }_{i,h}}}\log {{\pi }_{i,h}}$

(17)

由此可以得到下面的最佳响应函数Logit型:

$\gamma _{i,h}^{t}=\frac{\exp \{\hat{u}_{i,h}^{t}/{{\mu }_{i}}\}}{\sum\nolimits_{w\in {{R}_{i}}}{\exp \{\hat{u}_{i,w}^{t}/{{\mu }_{i}}\}}},h\in {{R}_{i}},i\in N$

(18)

为了${{\{\gamma _{i,h}^{t}\}}_{t\ge 0}}$成为车辆i的最佳响应,用递归估计效用来渐近逼近已知效用.基于文献^[35]中的随机近似理论,用下面的更新公式来近似表示公式(12):

$\hat{u}_{i,h}^{t+1}=\hat{u}_{i,h}^{t}+{{\xi }^{t+1}}\frac{1\{r_{i}^{t}=h\}}{\gamma _{i,h}^{t}}(U_{i}^{t}-\hat{u}_{i,h}^{t})$

(19)

其中,对于每个车辆i,${{\{\xi _{i}^{t}\}}_{t>0}}$是一个确定性序列,满足以下条件:

$\sum\nolimits_{t\ge 0}{\xi _{i}^{t}=\infty ,\sum\nolimits_{t\ge 0}{{{(\xi _{i}^{t})}^{2}}}＜\infty }$

(20)

公式(19)的收敛性属性可以用文献^[36]中的常微分方程组(ODE)来近似.如果系统处于一个平稳过程,其中每个车辆都独立选择路径,并假定其他车辆都保持原先的路径,那么估测效用将会收敛到已知效用的期望值.在更一般的情况下,所有的车辆都同时改变路径,系统呈现不平稳过程.文献^[37]已证实,公式(19)中的参数x^t如果满足下面的条件,将是一个车辆特定的参数$\{\xi _{i}^{t}\}$:

$t\to \infty ,\frac{\xi _{i}^{t}}{\xi _{i}^{t+1}}\to 0$

(21)

根据文献^[38]提出的扰动微分方程理论,文献^[37]提供了下面的引理:结合车辆特定参数x^t,公式(19)得出的值$\hat{u}_{i}^{t}$,只要它一直保持有界,那么它将会收敛到一个由异常扰动微分方程定义的有关交通流的内部联通的链递归集合.

3.3 自适应学习算法

在自适应学习算法中,本文使用了Logit模型参数,该参数基于由已实现的效用定义的后悔值进行递归更新.如果每个车辆成功选择了更好路径,后悔值会渐近地收敛于一个非常小的值,同时,每个车辆选择最佳路径的概率也会增大.最后,基于马尔可夫链模型证明了该算法收敛于e-Nash均衡.

3.3.1 马尔可夫学习过程

在驶向多路口的多个车辆进行路径选择博弈时,每个车辆的个体信息和所选路段的成本取决于其他路段的交通流,车辆的路径选择策略受到干扰,此时,车辆的理性选择是较好响应,而不是最好响应.本文的方法是基于马尔可夫学习模型进行状态转移,该模型将博弈过程中的状态看做一个学习层次,描述了状态迁移的过程.在每一个时间步t=1,2,…,用X(t)表示博弈状态,变量v为该状态下为学习者的数目,学习者就是成功地找到了最佳响应路径的车辆;而剩下的(n-v) 个车辆则是非学习者.将非学习者的路径选择行为标为0;另一方面,将学习者的路径选择行为标为1,在接下来的时间步里,学习者将会保持行为不变.

用s_v表示在状态X(t)下某辆车选择最佳路径的概率,而(1-s_v)则表示某辆车没有选择到最佳路径的概率.那么如图 3所示,状态迁移概率表示为

$\left. \begin{align} &\Pr [X(t+1)=v+1|X(t)=v]=\frac{n-v}{n}{{\sigma }_{v}},0\le v\le n-1 \\ &\Pr [X(t+1)=v-1|X(t)=v]=\frac{v}{n}(1-{{\sigma }_{v}}),1\le v\le n \\ &\Pr [X(t+1)=v|X(t)=v]=\frac{n-v}{n}(1-{{\sigma }_{v}})+\frac{v}{n}{{\sigma }_{v}},0\le v\le n \\ &\Pr [X(t+1)={v}'|X(t)=v]=0,{v}'\notin \{v-1,v,v+1\} \\ \end{align} \right\}$

(22)

尽管信息分析中心知道当前状态,但是每个车辆并不知道自己当前所处的状态.根据马尔可夫链的性质可知,该马尔可夫链模型是不可约且非周期性的,所以会收敛到一个稳定的迁移概率l,这可以在解决下面等式的时候找到^[39]:

$\frac{{{\lambda }_{v+1}}}{{{\lambda }_{v}}}=\left( \frac{n-v}{v+1} \right)\left( \frac{{{\sigma }_{v}}}{1-{{\sigma }_{v}}} \right)\sum\nolimits_{v=0}^{n}{{{\lambda }_{v}}}=1$

(23)

3.3.2 算法过程

在各车辆驶向路口选择前行路径的过程中,给定初始路径选择行为向量及对应的效用值$\{{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r}}^{0}},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {U}}^{0}}\}$,后面的路径选择行为及效用值$\{{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r}}^{t}},{{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {U}}^{t}}\}(t>0)$会相继产生.假定车辆i仅仅知道每个阶段t>0已实现的效用值$\{U_{i}^{t}\}$,并基于一定规则对可选路径的选择进行概率分布.信息中心在各车辆Agent对可选路径基于混合策略产生的路径选择向量的基础上,结合城市路网实时交通信息对路径的效用值进行计算并发送给各车辆,使得行驶车辆知道每个时刻已实现的路径效用值并将其保存.行驶车辆在已实现的各时刻路径效用值基础上,通过探索来选择当前时刻的最佳路径TBR(tentative best route).

(1) 初始化路径

当车辆Agent在快要到达路口前向信息中心发送对前方路段的偏好信息以后,察觉到需要协商路径选择时,自适应学习算法就被启动了,这个过程称为初始化条件.

在最初时刻t=0,每个车辆Agent i随机选择最初路径$r_{i}^{0}$;在下一时刻t=1,将该路径作为试探性最佳路径TBR ${{h}^{*}}=r_{i}^{1}=r_{i}^{0}$.

(2) 适应性学习阶段

在随后的每一个时刻,每个车辆i通过探索来选择试探性最佳路径TBR h,然后将该路径包含到最佳路径集中(即,以最大化各车辆估测效用为目标):

$B_{i}^{t}=\{{{h}^{*}}\in {{R}_{i}}:{{h}^{*}}=\arg {{\max }_{{{r}_{i}}\in {{R}_{i}}}}{{\hat{u}}_{i}}({{r}_{i}})\}$

(24)

基于下面的概率分配规则(以高概率选择最大估测效用路径,以低概率随机选择其他路径),车辆i通过探索来选择试探性最佳路径TBR h:

$\pi _{i}^{t}({{r}_{i}})=\left\{ \begin{array}{*{35}{l}} \varepsilon \beta _{i}^{t}({{r}_{i}})+(1-\varepsilon ),\text{ }{{r}_{i}}={{h}^{*}} \\ \varepsilon (1-\beta _{i}^{t}({{h}^{*}}))/(|{{R}_{i}}|-1),\text{ }{{r}_{i}}\ne {{h}^{*}} \\ \end{array} \right.$

(25)

其中,e是一个很小的任意正数.TBR的选择概率如下所示:

$\beta _{i}^{t}({{r}_{i}})=K\exp \{{{\hat{u}}_{i}}({{r}_{i}})/\mu _{i}^{t}\},{{r}_{i}}={{h}^{*}}$

(26)

其中,K是归一化因子,而Logit参数$\mu _{i}^{t}$根据下面的式子进行更新,即,根据用户的经验自动进行更新:

$\left. \begin{align} &\mu _{i}^{t}=\max [{{\varepsilon }_{\mu }},\mu _{i}^{t}] \\ &\mu _{i}^{t}=\mu _{i}^{t-1}+(H_{i}^{t}-\mu _{i}^{t-1})/t \\ \end{align} \right\}$

(27)

其中,$H_{i}^{t}$表示车辆的后悔值,定义为$H_{i}^{t}=U_{i}^{t}-\bar{U}_{i}^{t}$,其中,$\bar{U}_{i}^{t}={\sum\nolimits_{s=1}^{t}{U_{i}^{s}}}/{t}\;$.当时间t变得非常大时,后悔值$H_{i}^{t}$接近于0.

新的路径选择向量${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r}}^{t}}$,根据各车辆的混合策略${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {\pi }}^{t}}$产生.

公式(25)中的第一个等式表明:车辆i至少给每个可选路径分配概率eb_i(h),而给TBR分配的概率要多一点,以此来强化TBR.公式(25)和公式(26)一起表示车辆i的重新规划(适应性学习)过程,以此来试探性选择TBR.

(3) 路径选择迭代过程

如果TBR被重复选中,则该车辆在后面的阶段都保持该路径选择不变;如果根据混合策略选中的路径并不是TBR,那么车辆将根据公式(25)和公式(26)继续探索TBR.

(4) 输出最佳路径选择

如果在约定次数内各车辆Agent都已找到自己的TBR,即:各车辆路径选择达到Nash均衡时,或者计算到离连接点(基于GPS定位)有一段给定距离时,算法终止.这被称为终止条件.当算法执行完毕,车辆Agent按照最终的路径选择方案转向相应的路口继续行驶.

图 4给出了自适应学习算法的详细流程图.该算法考虑到了城市交通路网中多路口行驶车辆在同时进行路径选择时的相互影响,因此,该算法具有精度高、自适应性强、鲁棒性好等优点.

在自适应学习算法中,通过动态规划方法求解各个车辆最佳路径选择的Nash均衡,算法时间复杂度是O(n^m).与传统的路径选择算法,比如单源最短路径算法(时间复杂度为O(n²))、多源最短路径算法(时间复杂度为O(n³))相比,可以看出本文算法时间复杂度相对较高,但是传统的路径选择算法主要是针对单个车辆的最佳路径选择,没有考虑到多个车辆彼此间的影响,更没有考虑到真实城市路网交通环境的动态不确定性,而本文算法旨在通过多路口多个车辆间的拥堵博弈,使得行驶车辆在综合考虑对路径的偏好、路径拥挤程度以及不确定因素的情况下,均匀分布在城市路网中,从而更加适应真实城市路网环境,极大地减缓了整个城市交通路网的拥堵程度,有效降低了车辆的平均行驶时间.

3.3.3 算法的收敛性

假定拥堵博弈有一个纯Nash均衡,那么由自适应学习算法产生的行为向量${{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\rightharpoonup}$}} {r}}^{t}}$会在ε非常小、时间t非常大的情况下,以概率ρ<1收敛到ε-Nash均衡.

首先,对于平稳概率来说,存在下式:

${{\lambda }_{v}}=\left( \frac{v+1}{n-v} \right)\left( \frac{1-{{\sigma }_{v}}}{{{\sigma }_{v}}} \right){{\lambda }_{v+1}},0\le v\le n-1$

(28)

其中,${{\sigma }_{v}}=1-\varepsilon (1-\beta _{v}^{*}),\beta _{v}^{*}$是在学习者数量为v的状态时分配给试探性最佳响应路径TBR的选择概率.定义σ=min_0≤v≤nσ_v作为选择TBR的最低概率,可以选择ε来保证d=(1-σ)/σ<1.如果选择ε≤1/n,那么存在下式:

${{l}_{0}}\le \ldots \le {{l}_{n}}_{-1}\le {{l}_{n}}$

(29)

假设最后一个状态,所有的车辆都以概率1找到了TBR,也就是说,λ_n=ρ=1.这表示λ₀=…=λ_n-1=0,并且所有的车辆几乎都收敛到了纯Nash均衡,这种情况可能会在车辆彼此间都了解对方路径选择的问题里出现.然而在车辆彼此间并不了解对方路径选择的问题里,概率ρ必须小于1.根据公式(21),对于一个给定的概率λ_n=ρ,可以构建序列等式{λ_n-1,…,λ₀},它们的和为

$\Phi =\sum\nolimits_{v=0}^{n-1}{{{\lambda }_{v}}}=\left( \left( n\cdot \frac{n-1}{2}\cdot ...\cdot \frac{1}{n} \right){{\delta }^{n}}+...+n\cdot \frac{n-1}{2}\cdot {{\delta }^{2}}+n\delta \right)\rho =\rho \sum\nolimits_{v=1}^{n}{\left( \begin{matrix} n \\ v \\ \end{matrix} \right)}{{\delta }^{v}}$

(30)

使用二项公式,可以得到φ=ρ{(1+δ)ⁿ-1}.因而有:

$r=1/{{(1+d)}^{n}}={{\{1-e(1-{{b}^{*}})\}}^{n}}＜1$

(31)

如果分配给TBR的最小概率接近于1,那么所有用户都能成功找到最佳路径的概率ρ也会非常接近于1.然而,采用非常小的数值ε会带来相反的效果.在一次迭代相对比较早的阶段,一个车辆会以很大的概率选择了错误的路径,然后再来修正.如果增加一些更低的概率,意味着一些车辆被允许获得较好响应,也就是说,λ=λ_n+ λ_n-1+…+λ_n-s,那么ε-Nash均衡将会以相对较高的概率达到.

4 实验验证

为了验证DR²SM模型的有效性,本文使用JADE作为Agent模拟器,VanetMobiSim用来模拟车辆运动,分别针对人工路网和真实路网进行了实验.不同的公路网在VanetMobiSim中使用场景扩展标记语言文件来配置,Agent行为(体现DR²SM解决方案思想)在JADE中来模拟.第4.1节针对多个路口的人工路网,设定不同数量的路口和车辆.为了验证DR²SM模型中多个车辆通过协商后的路径选择更加精确有效,本文将该模型与3种非协商算法分别进行比较.第4.2节扩展到更大的真实公路格状网,分别针对不同车流量密度的场景(畅通流、自由流、混合流、堵塞流)进行测试,进一步验证DR²SM模型在真实交通场景中的有效性.

4.1 场景1:人工路网

本场景选取人工路网中的某一区域作为实验对象,道路由5条主干道(实线)和3条次干道(虚线)组成,路网中的道路都是双向的,每条道路的长度、道路通行能力和时速限制都不相同,彼此交叉.图中标识处为7个目的地节点,编号分别为A~G,在仿真实验中,它们或为出行起点或为出行终点,如图 5所示.为了偏好评估,道路被特征化为ST(最短时间)路径、SD(最短距离 )路径、F(最熟悉)路径或者它们的组合.每个车辆Agent最初被随意指派一个主要的或者一个次优偏好路径.如果一个路段的车容量超出了阈值容量,则车辆的行驶速度会降低,路段开始进入拥堵.当道路的车容量超出道路通行能力时,车辆的行驶速度进一步降低,进入非常慢速的行驶阶段.

为了验证使用DR²SM模型进行车辆间的相互协商对降低整个路网行驶时间的影响程度,本文通过改变路径效用计算公式中不同参数的权值系数,将该模型与3个非协商算法分别进行比较:最短路径算法(p=0,b=0)、基于偏好的算法(c=0,b=0)、基于偏好的最短路径算法(p=c,且p!=0,b=0).这些算法中都没有车辆间通信,所以不能通过车辆间彼此协商来避免道路选择冲突,也不考虑道路是否存在不确定性突发事件.在最短路径算法中,所有的车辆都选择从源地址到目的地之间行驶距离最短的路径,而不管该路径的道路属性是否符合车辆偏好,选择一条路径的效用仅仅取决于选择这条路径所耗费的成本.在基于偏好的路径选择算法中,每个车辆基于自己的偏好选择最好的路径, 不管是否超出了该路径的道路通行能力,选择一条路径的效用仅仅取决于相应车辆对于这条路径的偏好值.在基于偏好的最短路径选择算法中,所有车辆选择它们偏好的路径中最短的那条,而不管是否超出了该路径的道路通行能力.

为了观测DR²SM模型在不同规模路网中的性能表现,设定路网协商的规模从小到大依次选择4个(1,2,5,6)、9个(1,2,3,5,6,7,9,10,11)以及16(1~16)个路口.在每个路口规模确定的场景中,又设定若干子场景,分别考察道路车辆数小于道路的阈值容量(case 1)、大于阈值容量而小于堵塞容量(case 2)以及大于堵塞容量时(case 3)的性能表现.仿真实验以A,B,C,D作为源地址,E,F,G作为目的地.在到达每个路口之前,车辆Agent彼此间交换信息,并通过协商进行路径选择.在这个过程中,假定借助GPS(global position system),交通信息是准确的,车辆对于前方路口的交通状况也完全知晓.在不同场景中,本文提出的DR²SM模型相对3个非协商算法的行驶时间减少百分比如图 6所示.

从图 6中的仿真结果可以看出:

(1) 对于多路口的路网,DR²SM模型相比较3个非协商算法可以减少行驶时间,尤其相对最短路径算法更有优势,可以减少5%~37%.在DR²SM模型中,车辆之间彼此通信并协同分散在可选路径上,以最小化旅行时间成本.而在最短路径算法中,所有的车辆只选择最短路径(不管道路容量限制),这是造成拥堵的根本原因.基于偏好的算法和基于偏好的最短路径算法受用户的偏好驱动(有可能不只是偏好一条路径),实际上这就会使一定比例的车辆分散在一些可选路径上,而不是都拥挤在一条最短路径上.因此在大多数情况下,DR²SM模型相对最短路径算法获得的收益要比相对基于偏好的算法和基于偏好的最短路径算法获得的收益要大;

(2) 在参与协商的路口数量一定的情况下,当路网中的车辆数刚刚超过路网阈值容量时,行驶时间减少百分比反而上升;但当车辆数超过堵塞容量时,行驶时间减少百分比则最低.这表明:当路网中车辆刚开始增多时,通过车辆间的协商进行路径选择可以使得车辆更好地分散在路网中,但是当路网过于拥堵时,车辆间的协商对于车流量的分散作用不是很明显;

(3) 随着参与协商和路径优化的路口数量增加,行驶时间减少得更为明显.这表明了DR²SM模型中参与协商的路口越多,参与协商的车辆行驶的路程越长,行驶时间减少的比例会更大.这是因为在这种情况下,车辆在行驶的过程中遇到更多的路口,有更多的机会进行协商以选择更好的路线分配,因而更有利于车辆在城市路网中更好地分布,从而使得城市道路资源利用得更加充分.

4.2 场景2:真实路网

为了验证DR²SM模型的稳定性和可扩展性,本文在更大的真实格状路网上进行了对比实验.在这个场景中,DR²SM模型应用于武汉市武昌区的一个真实格状网,如图 7所示.该城市路网包含24个主要路口,其中,路口1~路口4、路口6、路口11、路口12、路口16、路口20、路口22、路口24作为测试路网的源点和终点.路网中的道路由36条路段组成,每条路段均为双向道路,道路状况参数根据实际情况进行设定,各行驶车辆对于各路段的偏好属性值进行随机分配.各路段彼此交叉,并有时速限制.

为了观测DR²SM模型在不同交通流密度中的性能表现,本文分别针对交通路网中道路饱和度为0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8的情形进行了实验,其中,道路饱和度为0.1~0.2,0.3~0.4,0.5~0.6,0.7~0.8对应的交通流状态分别表示夜里10点以后的畅通流、下午3点~4点的自由流、中午12点~2点的混合流、早晨7点~8点的堵塞流这4种常见的交通场景,相应的车辆总数在9 000辆~90 000辆左右.选择路网中的任意路口作为源点和终点,分别将DR²SM模型和最短路径算法、基于偏好的算法、基于偏 好的最短路径算法这3个非协商算法进行比较.图 8给出了在这4种场景中,分别采用DR²SM模型相对3个非协商算法的行驶时间减少百分比.

从图 8的结果可以看出:

(1) 即使路网规模更大,行驶车辆更多,DR²SM模型相对3个非协商算法依然有8%~36%的行驶时间减少百分比;

(2) 随着道路饱和度的增加,DR²SM模型相对3个非协商算法的行驶时间减少百分比不断增加.当道路饱和度达到0.5时,即,在道路稍有拥堵时的混合流状态下,DR²SM模型的行驶时间减少百分比最高;但随着车流量继续增大,当道路处于非常拥堵的堵塞流状态时,DR²SM模型的协商结果对于行驶时间减少的比例反而下降.这与在人工路网上进行仿真的实验结果一致.

5 结 论

为了有效缓解城市交通拥堵问题,同时考虑行驶车辆的个性化交通需求以及城市路网中交通状况的动态不确定性,本文提出了一种城市交通路网动态实时多路口路径选择模型DR²SM.路网内的行驶车辆基于对可选路径的偏好,同时结合可选路径的实时交通状况,彼此之间通过自适应学习算法SALA不断地动态更新前行路径,使得各行驶车辆的路线选择策略达到Nash均衡,同时使路网资源应用效率达到最大化.为了验证DR²SM模型的有效性,本文分别基于人工路网和真实的城市交通路网进行了大量实验,并得出以下结论:

(1) 对于多路口的人工路网,DR²SM模型相比较最短路径算法、基于偏好的算法、基于偏好的最短路径算法等非协商算法可以减少车辆Agent的平均行驶时间;尤其相对最短路径算法更为优势,可以减少5%~37%的行驶时间.在参与协商的路口数量一定的情况下,当路网中的车辆数刚刚超过路网阈值容量时,行驶时间减少百分比反而上升;但当车辆数超过堵塞容量时,行驶时间减少百分比则最低.随着参与协商和路径优化的路口数量增加,行驶时间减少得更为明显;

(2) 在真实城市路网中,随着道路饱和度的增加,DR²SM模型相对3个非协商算法的行驶时间减少百分比不断增加;尤其当道路饱和度达到0.5时,即,在道路稍有拥堵时的混合流状态下,DR²SM模型的行驶时间减少百分比最高.但随着车流量继续增大,当道路处于非常拥堵的堵塞流状态时,DR²SM模型的协商结果对于行驶时间减少的比例反而下降.

进一步的研究仍然需要在以下两个方面继续:

(1) 进一步探讨改变行驶车辆中不遵从系统推荐路径的车辆比例,对于整个城市路网中车辆平均行驶时间的影响;

(2) 同时,考虑路口的交通信号灯周期在车辆路径选择时的影响.

致谢 我们真诚地向对本文的工作给予支持和建议的审稿人、主编、编辑、同行,同学和老师表示感谢.