基于R-FPOP变点检测的城市路段旅行时间预测

商明菊，胡 尧,2*，周江娥，王 丹

(1.贵州大学 数学与统计学院，贵州 贵阳 550025； 2.贵州省公共大数据重点实验室，贵州 贵阳 550025；3.厦门大学 数学科学学院，福建 厦门 361005)

旅行时间预测是交通出行者的重要需求，也是路网均衡诱导的关键。随着城市卡口监控系统不断升级，利用车牌识别数据快速、有效推送路段旅行时间，成为交通领域研究的热点。车牌识别数据作为针对城市道路行驶车辆的实时监测数据，具有持续生成且数据量大、时空相关等特性[1]。交通拥堵的本质是交通需求失衡，旅行时间能直观反映从起点到终点的出行成本，是表征路段交通拥堵状态的一个直观、有效的交通流参数。在城市主次干道系统中，随着拥堵程度的增加，由于信号控制的存在，车辆将以一定的饱和流率放行，路段旅行时间不会无限增长，而是趋于一个稳定的较高值。为利用车牌识别数据高效、准确计算旅行时间，赵卓峰等[1]给出旅行时间计算定义，并提出一种基于时空划分的流水线式并行计算模型。数据爆发式增长趋势下，数据流实时、连续、无监督异常检测方法[2]被提出；自动编码器[3]、递归神经网络[4]、递归最小二乘滤波[5]等模型，被应用于交通流参数预测。然而，柴华骏等[6]对道路交叉口车牌识别数据进行分析时，发现道路拥堵时旅行时间接近Weibull分布，通畅时接近对数正态分布，使用正态分布估计旅行时间均值误差较小。这一现象与旅行时间非平稳、随机突变特点有关，也使得常规统计预测模型建模受阻。

交通流变点是交通流模型中某个或某些参数突变之点[7]，近年来被逐渐应用到交通管理中，如速度预测[8]、道路交叉口事故监测[9]、拥堵状态自动识别[10]、交通流突变概率估计[11]、交通法规干预效果评价[12]等。变点发生后，交通流参数将发生质的变化。小粒度的收集交通流数据，可以快速检测正在突变的交通流变化，利于路况信息的及时发布。结合多源交通流数据，在线Bayesian变点检测方法被应用到个体出行模式突变概率估计[13]和交通拥堵概率估计[14]。然而，变点检测的关键在于算法的检测延迟、稳健性、变点源剖析以及无监督方法，通常非参数方法比参数方法稳健[15]。同时，采集到的实际数据常由于设备故障、交通事件突发等原因，非平稳且存在缺失或异常。交通流变点检测的难点就在于在线快速区分真实突变与异常值，这是大多数现有变点检测方法难以做到的，如WU等[16]提出的使用粒子滤波技术的变点检测方法，其参数易于选择，但其高稳健性和检测精度却以较高的计算成本为代价。因此，利用对异常值不敏感的变点检测方法，在线检测路段旅行时间变点并研究其在线推送问题，具有重要意义。

一种常用的方法是引入分割成本，如将负对数似然、平方损失等函数作为数据分割的成本，进而通过最小化该分割成本函数来检测变点。解决此类最小化问题，通常采用动态规划算法求解。变点个数已知时，为约束最小化问题，RIGAILL[17]就此提出基于函数修剪的pDPA(pruned Dynamic Programming Algorithm)来解决。然而，实际问题中变点个数往往是未知的。为此，JACKSON等[18]引入惩罚项，将变点检测转化为成本函数惩罚最小化问题，提出OP (Optimal Partitioning)算法；它的计算复杂度优于SNS(Segment Neighborhood Search)[19]，但在数据量较大的情况下，计算依旧复杂。随后，KILLICK等[20]提出基于不等式修剪的PELT(Pruned Exact Linear Time)算法，它比OP更有效且计算简单。这些方法均可描述为三个要素的集合，即成本函数、搜索方法和对变点个数的约束[21]。2017年，MAIDSTONE等[22]结合PELT与pDPA，提出使用函数修剪最优分割(Functional Pruning Optimal Partitioning，FPOP)算法来解决惩罚最小化问题，与现有的动态规划算法相比，其计算效率更高、检测性能更稳健。同年，为解决异常值存在情况下实测数据的在线变点检测问题，FEARNHEAD等[23]提出稳健的函数修剪最优分割(Robust Functional Pruning Optimal Partitioning，R-FPOP)算法，它利用对异常值不敏感的有界损失函数在线稳健检测变点，计算简便且准确率高。

鉴于此，本文针对车牌识别数据集上路段旅行时间精准推送的需求，利用稳健、高效的R-FPOP算法，解决路段旅行时间均值变点的在线检测问题，对变点时域分布进行研究，预测旅行时间并在线推送其预测区间，为交通需求者出行路线的规划提供参考。

1 R-FPOP算法

R-FPOP[23]是一种异常值存在下的稳健变点检测算法，它通过使用对异常值不敏感的成本函数与有效的FPOP[22]动态规划算法来求解时序的最优分割，进而估计出变点位置与个数。

设交通流参数时序y=(y1,…,yn)，时刻s到时刻t的子数据集为ys:t=(ys,…,yt)。假设时序y存在k个变点，则y被分割成k+1个不同区段。记第j个变点的位置为τj(j=1,…,k)，固定τ0=0、τk+1=n，得到变点集合τ=(τ0,…,τk+1)，第l个区段包括数据yτl-1+1,…,yτl(l=1,…,k+1)。基于最小化成本函数思想，求解时序变点的位置与个数。对交通流观测值y，引入一个包含特征参数θ的成本函数γ(y;θ)。定义子数据集ys:t的成本函数：

(1)

即特征参数θ与子数据集中每个观测值成本函数总和的最小值。进而得到分割整个数据集的惩罚成本函数：

(2)

式中，β为待定惩罚参数且满足β>0。β的大小对变点的位置与个数有重大影响[24]，其值越大，估计出的变点个数越少。

为监测时序的均值突变，通常采用平方损失函数[25]：

γ(y;θ)=(y-θ)2，

(3)

作为分割成本。然而，在线检测时此函数易受异常值影响。只有有界成本函数对于任意极端异常值的存在是稳健的[23]。最简单的成本函数就是双权损失(biweight loss)函数[26]：

(4)

该函数通过引入阈值K，使得它对极端异常值具有稳健性且可保证成本函数有界。在此基础上，利用FPOP算法动态求解惩罚最小化问题。

对数据集y1:t(t=1,…,n)，设候选变点集St={τ=τ1:k:0<τ1<…<τk

(5)

假设距离当前时刻t最近的区段特征参数为θ，定义：

(6)

γ(yt;θ)+β}]

β)+β]}+γ(yt;θ)

=min{Qt-1(θ),Qt-1+β}+γ(yt;θ)。

(7)

于是，Qt(θ)关键取决于Qt-1(θ)与Qt-1+β。将成本函数γ(yt;θ)视为θ的函数，如视双权损失函数为θ的分段二次函数。交通流参数时序均值必然在极值范围内，若θ在数据集极值区间上取值，则式(7)最小化问题可拆分为两步，第一步：

(8)

第二步：

(9)

因此，只需递推计算Qt(θ)并存储时刻t的最小成本及变点位置，就可以实现均值变点的在线检测。

2 路段旅行时间预测方法

在车辆行驶轨迹途径路段各交叉口的前提下，路段起止卡口系统先后采集到同一车辆的采集时间差即为车辆旅行时间。它为车辆行经路段的实际花费成本，其值越小，表明交通运行状态越好，路段越通畅；反之，越拥堵。

由于车牌识别错误、漏检等系统误差的存在，原始数据存在噪声；同时，在某些情况下，如偶然停车、中途离开等真实数据偏差的存在，使得车辆旅行时间不能反映整个交通流实际运行状态。因此，为屏蔽不合理车辆旅行时间带来的影响，当车辆经过起止卡口的时差小于某一临界值D时，才采集该车旅行时间。考虑到短时在线推送的必要性及数据采集的可靠性，当检测到的车辆数不低于2时，直接采用中位数法[1]获取路段旅行时间；若某时段检测到的车辆数低于2，不对该时段观测值进行填补，变点检测时不计分割成本即可。实际数据处理时，由于公交车行经站台需停车上下客，故将其剔除。虽然出租车也存在停车待客现象，但考虑到它作为交通需求者便捷出行的首选，对交通运行状态的评估起着关键作用，将其保留。

(10)

(11)

式中，N为旅行时间预测时序长度，I(·)为示性函数。

3 实例测试

表1 研究路段地理位置说明Tab.1 Description of geographical location of the research road sections

表2 研究路段算法参数Tab.2 Algorithm parameters of the research road sections s

3.1 路段旅行时间均值变点

采用R-FPOP算法对测试集各路段旅行时间时序进行在线均值变点检测。以7月29日路段I为例，除时序起止点外，共在线检测出8个变点，区段示意见图1(a)。从图1(a)中可以发现，在交通需求的随机扰动下，路段旅行时间均值跳跃现象明显，呈现出由一种稳定态突变到另一种稳定态的随机现象。由图1(b)可知，在异常值干扰的情况下，在线变点仍然能被快速检测，最短检测延迟时间为2 s。

利用动态规划思想，由在线变点检测结果递推得到全天时序的最优分割，即离线变点，结果如图2所示。由图2可知，各路段离线均值变点时域上分布不均匀，如 [10:00-12:00)两小时内，路段IV共检测出9个变点，而路段I只检测出1个变点。这也反映了旅行时间集群性与均值变点随机性特点。以路段IV为例，离线变点τ3(09:36)、τ4(10:22)、τ5(10:32)、τ6(10:36) 划分得到区段yτ3+1:τ4、yτ4+1:τ5、yτ5+1:τ6的旅行时间均值分别为139.83 (s)、391.17 (s)、651.00 (s)，τ4、τ5处跳跃度分别为251.34 (s)、259.83 (s)。可以发现，各区段旅行时间徒升、跳跃幅度大，[10:24-10:34)行经路段IV的出行成本为[09:38-10:24)的2.80倍。若“10:24”检测到旅行时间突变同时发布诱导信息，有助于出行者及时规划调整行车路线。从图2也可发现，受贵阳市一环商业经济圈交通需求的影响，高峰时段旅行时间跳跃现象频繁且跳跃度波动较大。采用非参数Wilcoxon秩检验，评估离线变点是否将相邻时序长度均大于15的实际序列准确划分。显著性水平0.01下，相邻区段均值检验p值均显著，这实证了R-FPOP算法检测的均值变点有效且检测性能优。

图1 均值变点在线检测结果(7月29日)Fig.1 Online detection results of the mean change points (July 29)

图2 均值变点离线检测结果(7月29日)Fig.2 Offline detection results of the mean change points (July 29)

进一步分析车辆日记录缺失比不低于10%的全数据集上在线检测的旅行时间均值变点特征。在频率分布基础上，利用核密度法估计均值变点时域分布的密度曲线，结果见图3。从图3可以看出，各研究路段旅行时间均值变点时域分布有较大差异，路段I、IV变点主要集中在早高峰，而路段II、III变点在晚高峰出现的概率略高于早高峰，这与路段双向各时段的交通需求密切相关。路段A是相邻片区大部分车辆由东向西进入贵阳市一环的首选，路段B紧邻集医疗、教育、金融为一体的繁华经济生活圈，这两条路段早高峰的交通发生量相对较大。若向出行者及时发布旅行时间历史均值及其突变概率，可在一定程度上合理引导其规划最优路线，进而均衡路网交通需求。

图3 研究路段在线变点时域分布Fig.3 Temporal distributions of the online change points of the research road sections

3.2 路段旅行时间预测

图4 旅行时间预测区间估计结果(7月29日)Fig.4 Estimation results of the travel time prediction intervals (July 29)

从图4可以看出，各路段旅行时间时序虽波动较大，但预测时序与真实时序整体走势相契合。由表3可知，测试集上路段I-IV旅行时间平均MAPE分别为13.47%、11.53%、10.01%、9.88%，整体平均MAPE为11.22%，这说明时序的变化趋势得到了较好预测。由表4可知，测试集上路段I-IV平均覆盖率分别为81.67%、78.31%、79.23%、78.94%，整体平均覆盖率为79.54%，预测精度较高，这说明提出的预测方法具有一定的实时性与有效性。由此，可为导航系统智能推送路段旅行时间预测值及其预测区间，将路段出行成本量化，从而诱导交通需求者择优出行，进而缓解交通拥堵，提高城市道路使用率。

表3 测试集旅行时间预测误差百分比绝对值均值Tab.3 Mean absolute percentage error of the travel time predictions for test set %

表4 测试集旅行时间预测区间覆盖率Tab.4 Coverage ratio of the travel time prediction intervals for test set %

综上，结合路段旅行时间的均值突变信息对旅行时间进行预测，得到了较准确的预测结果，方法的突出优点在于它建模简单、可操作性强，能够满足在线智能推送的需要。实际应用时，若实时数据长时段缺失，可与历史数据进行时空模式匹配来进行预测。

4 结论

(1)在实时获取车牌识别数据的情况下，本文利用稳健的变点检测算法对路段旅行时间均值变点进行在线检测，将其结果用于预测旅行时间。研究发现R-FPOP算法可以较好的辨识旅行时间均值突变且检测延迟小，均值变点具有随机性且高峰期内出现的概率较大；推送的旅行时间平均MAPE为11.22%、预测区间平均覆盖率为79.54%，预测效果优良。

(2)本文方法建模简单且操作性强，对于导航系统路段旅行时间的精准推送以及交通信息服务等具有一定的支撑作用。为保证卡口数据采集质量，研究路段较短，进一步需结合信号灯的影响以及多元时间序列在线变点检测方法，探究出行路线旅行时间的预测。