基于内容的推荐算法在交通信号配时中的应用*

□ 黄霖霖，屈嘉宸，张梦瑶，林 丽

(南京林业大学 汽车与交通工程学院，江苏 南京 210037)

交通信号控制经过近几十年的部署和发展，使得交通安全与效率有了极大的提升。但是传统的固定配时方法使交叉口的延误时间大幅上升，损害了人、货运输的便捷性要求，提高了交通参与者的出行成本以及公路运输的时间成本[1]。

交通信号控制可以追溯到20世纪中期Webster法的提出。由于Webster法易于实施且效果显著，常被选为交通信号控制的设计基础。近年来，有研究者提出利用数据挖掘和智慧交通系统技术改进交通信号控制系统。ZHAO GAO[2]考虑到交通系统中存在大量的无法完全统计和量化的不确定性因素，在交通系统中应用了潜在因子模型。通过训练大量历史数据，利用潜在因子模型成功地处理了在数学中不能精确建模的不确定性因素。方丹丽提出以交通状态对相应配时方案的评级由智慧交通系统生成相应信号控制方案[3]。通过实际计算模拟，预测了交叉口与配时方案的匹配程度。结果显示通过训练数据提供信号配时的方法在降低延误方面优于经典的Webster方法。

上述信控方法必须依赖大量良好的历史数据，而这些数据在现实中通常并不容易获得，因为交通系统的动态性使得数据信息容量超过传统配时方法的处理能力[4]。因此对于配时方案的选择，本文应用基于内容的推荐算法，基于内容的推荐(content based recommendation)根据内容的相似度向用户推荐相似度高的物品或信息，被认为是处理信息过载问题最有效的工具之一[5]。在交通信号配时中应用此算法的过程为：以路况为用户，配时方案为推荐内容，延误为评级，根据路况的特点，通过计算找到相似度最高的k个的路况作为类别标签，根据相似度高低对各类别加权，然后使用KNN (k-Nearest neighbour )算法对各个未使用的配时方案进行分类并预测其延误等级，最终根据权重从k个分类中选取延误最小前n个配时方案构成推荐列表并将其推荐给路况。

使用基于内容的推荐算法来预测交通状况与配时方案的匹配程度时，有以下优点:

①它提供了类似于无模型自适应控制的思想。它不仅可以屏蔽建模过程中的不确定性细节，而且可以保证潜在因素的作用不被忽略;

②交通信号控制系统可以让它执行离线训练，然后结合当前的交通状况在线运行。如此可以保证预测精度和实时性;

③它不需要依赖于大量的数据。同时考虑了道路状况的特点，可以根据需要进行扩充。

总的来说，基于内容的推荐算法是对交通信号控制中推荐内容的补充和优化。

1 信号配时推荐算法介绍

应用基于内容的推荐算法，为当前交通状况推荐以配时方案为内容的有序推荐列表。为提高排序质量，采用标准化折扣增益(nDCG)作为推荐列表的评价指标。

1.1 基于内容的推荐算法步骤

推荐系统的首要目的是推荐最适合用户需求的项目，在本文中，也就是寻找最合适的配时方案以满足不同交通状况下的交通需求。应用基于内容的推荐算法，即采用交通状况中共同特性对交通状况进行刻画，根据特性计算两种交通状况的相似度，然后，从几种最相似的交通状况下配时方案中选出最佳的配时方案。

在基于内容的推荐算法中选择不同的交通状况作为用户，并为其配置相应的OD(origin-destination)矩阵。然后选择一些配时方案作为推荐项目。同时，记录下每一对交通状况和配时方案下的延误时间作为评级依据。因此，将生成一个由延误时间填充的用户-对象矩阵。另外，对于延误数据应该进行一些预处理步骤，使它们更适合评级。

应用基于内容的推荐算法推荐最佳配时方案的流程描述如下:

步骤1:对原始延误数据进行预处理。继而产生一个标准的评级矩阵。

步骤2:将每两个区域行驶的车辆数量作为所有交通状况的共同特性。然后将交通状况a和b用向量(a1,a2,…,ai,…) 和(b1,b2,…,bi,…) 表示。

步骤3：使用欧氏距离计算任意两个交通状况间的相似度[6]。交通状况a与交通状况b的相似度计算，用公式(1)表示如下：

(1)

步骤4:当某些特定交通状况出现时(通常在每周期结束时检测)，KNN算法将根据步骤3生成的相似度，选择k个最相似的交通状况作为类别标签对其他未使用的配时方案进行分类并预测其在此交通状况下的延误等级。应用KNN算法，用于预测交通状况a对配时方案c的评级的公式(2)如下：

(2)

公式(2)中rb,c是交通状况b给予配时方案c的评级，它是延误的倒数。

步骤5:在步骤4之后，得到了一个有序的推荐列表(c1,c2,…,ci,ci+1,…)。其中ci是第i个最合适的配时方案，优于ci+1。

步骤6:在Paramics软件中验证获得的配时方案。根据Paramics软件仿真的结果，得到另一个有序列表(c1’,c2’,…,ci’,ci+1’,…)。

步骤7:比较列表(c1,c2,…,ci,ci+1,…)和列表(c1’,c2’,…,ci’,ci+1’,…)，评价预测的有效性。

1.2 推荐列表的评价指标

通过预测当前路况与未使用的配时方案的匹配程度获得推荐方案的关键在于寻找几个最合适的配时方案，构成一个有序列表。在一个高质量的有序推荐列表中，相似度越高，配时方案在列表中的位置就应该越靠前。同时，列表中的所有配时方案都应尽可能地与当前的路况匹配。因此采用nDCG(标准化折扣累积增益)[7]作为评价指标，定义如下:

(3)

其中DCGP代表推荐列表中处于第p位的对象的折扣累积增益。IDCGP(理想化折扣累积增益)是第p位对象的最大折扣累积增益。nDCGP是标准化折扣累积增益。

DCG用于分级相关性的度量，根据其在结果列表中的位置来度量返回结果的有效性或增益。以此为推荐列表中的对象排序[8]。其在位置P处的定义如下：

(4)

其中reli为列表中位置i处结果的分级相关性。

对于选定的p值，每个位置的累积增益应该进行归一化。通过与理想化折扣累积增益IDCG对比。可以获得所有推荐对象对应的nDCG值。

2 推荐方法Paramics仿真

2.1 交叉路口建模

推荐方案基于各种交通状况参数，如延误时间等参数进行制定。为了便于理解，引入如图1所示的一个典型的交叉路口。交叉路口由向量I=(r1,r2,…,rm)表示，m为连接到交叉口的道路数，在图1中m=4，ri是一个5维向量,表示为ri=(l1,l2,l3,l4,l5)，l1代表U型转弯车道，l2代表左转车道，l3代表直行车道，l4代表直行右转车道，l5代表右转车道。它们都是依次表示的，lj的数值代表每种车道的数量。例如,ri=(0,1,2,0,1)表示有1条左转车道，2条直车道和1条右转车道。假定车辆在转弯时会沿着给定的路径行驶。

图1 实验交叉路口设置

2.2 初始数据设置

在2.1节图1属于有4条道路交汇的典型单交叉口仿真路网，即I=(r1,r2,r3,r4)。每路有3条车道，1条左转车道，1条直行车道和1条右转车道，即r1=r2=r3=r4=(0,1,1,0,1)。在Paramics中，时间步长设置为0.5s，而仿真持续时间为1h。每条车道的长度为1000m。

图2 实验相位设置

图2依序列举了实验采用的交叉路口信号灯的四种相位。在每个配时方案中，每个相位的黄灯时间被设置为3s。另外，在每个相位中总是允许右转。

在实验中使用了40组不同OD矩阵代表40种不同的交通需求，由此创建了40种不同的交通状况。以及使用了40个固定的配时方案，这些配时周期长度从88s到122s不等。配时方案的范围覆盖了大多数交通情况的范围。车辆数从120到23400不等。

2.3 实验仿真过程

首先将3个OD矩阵与3个配时方案进行交叉实验，并收集这9个实验的延误数据。在Paramics软件中进行仿真的3个OD矩阵吸发量设置见表1，表2和表3中的OD 1,OD 2和OD 3。其中，OD 1设置区1和区2的出行量多于区3和区4，OD 2设置第3区和第4区的出行量多于区1和区2。OD 3设置每个区的出行量相等。

表1 实验中的OD 1数据

表2 实验中的OD 2数据

表3 实验中的OD3 数据

表4 实验中的3个配时方案

表4中给出了3个配时方案，在每个配时方案中，周期时长设置为100s。在配时方案1中，相位1和相位2的时长比相位3和相位4长6s，而在配时方案2中相位3的时长和相位4比相位1和相位2长6s。在配时方案3中各个相位的时长相等。

表5 实验中获得的延误时间

从9组实验中得到的延误数据可以转换成一个延误矩阵，列于表5。延误时间采用的单位是s。

表6 实验中的OD 4数据

除了3个OD用以模拟交通状况，添加OD4预测该OD量在3个配时方案下的匹配度。OD4的设置见表6。

然后采用基于内容的推荐算法计算OD4与其它三种OD矩阵的相似度，列于表7。

表7 OD 4与其他三种OD的相似度

利用上述数据，通过第1节所述的方法预测OD 4和3个配时方案之间的匹配程度。预测结果表明，OD 3与OD 4最为匹配。而Paramics软件仿真的结果表明，配时方案3是最匹配的，而配时方案2是最不匹配的。这与预测结果相同。

2.4 全交通情况仿真实验

实际情况中交通情景更为复杂，需要通过稀疏延误矩阵预测交通状况与其未使用的配时方案之间的匹配程度。

首先，通过Paramics软件对40个OD矩阵搭配40个配时方案进行仿真，得到延误时间的稀疏矩阵作为评级标准，其稀疏度为75%。然后，向每个OD矩阵推荐了6个未使用的配时方案。得到有序推荐列表Li=(c1,c2,c3,c4,c5,c6),其中Li代表第i个OD的列表。此外，在Paramics软件中，还将每个OD矩阵搭配其Li中的6个推荐的配时方案进行了仿真。然后根据延误数据得到每个OD的理想顺序列表Li，=(c1’，c2’,c3’,c4’,c5’,c6’)。假定ODi与列表Li中cj(其中j=1,2,3,4,5,6)的相似度依次是5 4 3 2 1 0。然后计算每个OD推荐列表Li的nDCG值，结果见图3:

图3 40个交通状况的nDCG@6

从图3中不难看出基于内容的推荐算法表现出了良好的性能，所有OD矩阵的nDCG值均大于0.6。且多数趋近于1。这表明了基于内容的推荐算法的有效性。

3 推荐配时方法与Webster固定配时方法的比较

经过排序后，每个Li中的第一项c1都对应于ODi中最好的未使用的配时方案。为了获得最终的最佳配时方案Cbest，需要将c1和使用的配时方案进行比较。

为了比较基于内容的推荐算法与Webster方法的性能，对上述的40个交通状况采用Webster方法获取对应的配时方案。采用Webster方法进行交叉口信号配时时，需设定的相关参数见表8，其中AR为全红时间，以s为单位，l为每相位平均损失时间(以s为单位，不包括全红时期和黄灯时期)，S为交叉口饱和交通量,用扩展为一小时的饱和流率来表示，单位采用Vehs/h。

表8 Webster方法的参数

通过用近似解法，可以得到Webster配时方法下最佳周期时长为:

(5)

式中：L为每个周期的总损失时间，s；l为起动损失时间，s；A为黄灯时间，s；I为绿灯间隔时间，s；Y为交叉口交通流量比。

将40个OD矩阵搭配对应最优周期Cbest得到的延误时间与搭配Webster方法得到的配时方案同时进行仿真，并将得到的延误时间进行比较，数据见图4。

图4 延误时间比较

图4中交通状况1-40是对应交通流从小到大的顺序，与Webster方法相比，基于内容的推荐算法的推荐的配时方案总体延误时间要小得多。此外，当处于第9至第20交通状况之间时，基于内容的推荐算法推荐的配时方案相比webster方法的得到的配时方案，其延误明显更低。尽管如此，在最初的5到8的交通状况中，两种方法产生的延误并没有较大的差别。当交通流量较小时，使用基于内容的推荐算法推荐的配时方案与webster方法推荐的配时方案延误并没有太大差距。同时，当交通流量过大时，延误时间会在小范围内波动。另外，当交通状况为1-4时，无法应用Webster方法配时。因为Webster方法应用时交叉口交通流量比Y应该保持在0.4到0.9之间。在这些低OD量情况下，基于内容的推荐算法表现良好。

4 结束语

本文的灵感来自于推荐系统的思想，通过基于内容的推荐算法，研究不同配时方案与各交通状况之间的匹配度高低。实验结果表明，反馈顺序推荐列表与理想序列列表有很高的相关性，证明了该方法的有效性。然后，将基于内容的推荐算法与传统Webster进行比较，发现基于内容的推荐算法在降低运输过程中交叉口等待延误方面优于Webster方法。未来的研究将考虑更多影响交通环境和代表交通状况的因素以及将基于内容的推荐算法与协同过滤方法相结合。