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

(1.貴州大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，貴州 貴陽 550025； 2.貴州省公共大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，貴州 貴陽 550025；3.廈門大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，福建 廈門 361005)

旅行時(shí)間預(yù)測是交通出行者的重要需求，也是路網(wǎng)均衡誘導(dǎo)的關(guān)鍵。隨著城市卡口監(jiān)控系統(tǒng)不斷升級，利用車牌識別數(shù)據(jù)快速、有效推送路段旅行時(shí)間，成為交通領(lǐng)域研究的熱點(diǎn)。車牌識別數(shù)據(jù)作為針對城市道路行駛車輛的實(shí)時(shí)監(jiān)測數(shù)據(jù)，具有持續(xù)生成且數(shù)據(jù)量大、時(shí)空相關(guān)等特性[1]。交通擁堵的本質(zhì)是交通需求失衡，旅行時(shí)間能直觀反映從起點(diǎn)到終點(diǎn)的出行成本，是表征路段交通擁堵狀態(tài)的一個(gè)直觀、有效的交通流參數(shù)。在城市主次干道系統(tǒng)中，隨著擁堵程度的增加，由于信號控制的存在，車輛將以一定的飽和流率放行，路段旅行時(shí)間不會無限增長，而是趨于一個(gè)穩(wěn)定的較高值。為利用車牌識別數(shù)據(jù)高效、準(zhǔn)確計(jì)算旅行時(shí)間，趙卓峰等[1]給出旅行時(shí)間計(jì)算定義，并提出一種基于時(shí)空劃分的流水線式并行計(jì)算模型。數(shù)據(jù)爆發(fā)式增長趨勢下，數(shù)據(jù)流實(shí)時(shí)、連續(xù)、無監(jiān)督異常檢測方法[2]被提出；自動(dòng)編碼器[3]、遞歸神經(jīng)網(wǎng)絡(luò)[4]、遞歸最小二乘濾波[5]等模型，被應(yīng)用于交通流參數(shù)預(yù)測。然而，柴華駿等[6]對道路交叉口車牌識別數(shù)據(jù)進(jìn)行分析時(shí)，發(fā)現(xiàn)道路擁堵時(shí)旅行時(shí)間接近Weibull分布，通暢時(shí)接近對數(shù)正態(tài)分布，使用正態(tài)分布估計(jì)旅行時(shí)間均值誤差較小。這一現(xiàn)象與旅行時(shí)間非平穩(wěn)、隨機(jī)突變特點(diǎn)有關(guān)，也使得常規(guī)統(tǒng)計(jì)預(yù)測模型建模受阻。

交通流變點(diǎn)是交通流模型中某個(gè)或某些參數(shù)突變之點(diǎn)[7]，近年來被逐漸應(yīng)用到交通管理中，如速度預(yù)測[8]、道路交叉口事故監(jiān)測[9]、擁堵狀態(tài)自動(dòng)識別[10]、交通流突變概率估計(jì)[11]、交通法規(guī)干預(yù)效果評價(jià)[12]等。變點(diǎn)發(fā)生后，交通流參數(shù)將發(fā)生質(zhì)的變化。小粒度的收集交通流數(shù)據(jù)，可以快速檢測正在突變的交通流變化，利于路況信息的及時(shí)發(fā)布。結(jié)合多源交通流數(shù)據(jù)，在線Bayesian變點(diǎn)檢測方法被應(yīng)用到個(gè)體出行模式突變概率估計(jì)[13]和交通擁堵概率估計(jì)[14]。然而，變點(diǎn)檢測的關(guān)鍵在于算法的檢測延遲、穩(wěn)健性、變點(diǎn)源剖析以及無監(jiān)督方法，通常非參數(shù)方法比參數(shù)方法穩(wěn)健[15]。同時(shí)，采集到的實(shí)際數(shù)據(jù)常由于設(shè)備故障、交通事件突發(fā)等原因，非平穩(wěn)且存在缺失或異常。交通流變點(diǎn)檢測的難點(diǎn)就在于在線快速區(qū)分真實(shí)突變與異常值，這是大多數(shù)現(xiàn)有變點(diǎn)檢測方法難以做到的，如WU等[16]提出的使用粒子濾波技術(shù)的變點(diǎn)檢測方法，其參數(shù)易于選擇，但其高穩(wěn)健性和檢測精度卻以較高的計(jì)算成本為代價(jià)。因此，利用對異常值不敏感的變點(diǎn)檢測方法，在線檢測路段旅行時(shí)間變點(diǎn)并研究其在線推送問題，具有重要意義。

一種常用的方法是引入分割成本，如將負(fù)對數(shù)似然、平方損失等函數(shù)作為數(shù)據(jù)分割的成本，進(jìn)而通過最小化該分割成本函數(shù)來檢測變點(diǎn)。解決此類最小化問題，通常采用動(dòng)態(tài)規(guī)劃算法求解。變點(diǎn)個(gè)數(shù)已知時(shí)，為約束最小化問題，RIGAILL[17]就此提出基于函數(shù)修剪的pDPA(pruned Dynamic Programming Algorithm)來解決。然而，實(shí)際問題中變點(diǎn)個(gè)數(shù)往往是未知的。為此，JACKSON等[18]引入懲罰項(xiàng)，將變點(diǎn)檢測轉(zhuǎn)化為成本函數(shù)懲罰最小化問題，提出OP (Optimal Partitioning)算法；它的計(jì)算復(fù)雜度優(yōu)于SNS(Segment Neighborhood Search)[19]，但在數(shù)據(jù)量較大的情況下，計(jì)算依舊復(fù)雜。隨后，KILLICK等[20]提出基于不等式修剪的PELT(Pruned Exact Linear Time)算法，它比OP更有效且計(jì)算簡單。這些方法均可描述為三個(gè)要素的集合，即成本函數(shù)、搜索方法和對變點(diǎn)個(gè)數(shù)的約束[21]。2017年，MAIDSTONE等[22]結(jié)合PELT與pDPA，提出使用函數(shù)修剪最優(yōu)分割(Functional Pruning Optimal Partitioning，F(xiàn)POP)算法來解決懲罰最小化問題，與現(xiàn)有的動(dòng)態(tài)規(guī)劃算法相比，其計(jì)算效率更高、檢測性能更穩(wěn)健。同年，為解決異常值存在情況下實(shí)測數(shù)據(jù)的在線變點(diǎn)檢測問題，F(xiàn)EARNHEAD等[23]提出穩(wěn)健的函數(shù)修剪最優(yōu)分割(Robust Functional Pruning Optimal Partitioning，R-FPOP)算法，它利用對異常值不敏感的有界損失函數(shù)在線穩(wěn)健檢測變點(diǎn)，計(jì)算簡便且準(zhǔn)確率高。

鑒于此，本文針對車牌識別數(shù)據(jù)集上路段旅行時(shí)間精準(zhǔn)推送的需求，利用穩(wěn)健、高效的R-FPOP算法，解決路段旅行時(shí)間均值變點(diǎn)的在線檢測問題，對變點(diǎn)時(shí)域分布進(jìn)行研究，預(yù)測旅行時(shí)間并在線推送其預(yù)測區(qū)間，為交通需求者出行路線的規(guī)劃提供參考。

1 R-FPOP算法

R-FPOP[23]是一種異常值存在下的穩(wěn)健變點(diǎn)檢測算法，它通過使用對異常值不敏感的成本函數(shù)與有效的FPOP[22]動(dòng)態(tài)規(guī)劃算法來求解時(shí)序的最優(yōu)分割，進(jìn)而估計(jì)出變點(diǎn)位置與個(gè)數(shù)。

設(shè)交通流參數(shù)時(shí)序y=(y1,…,yn)，時(shí)刻s到時(shí)刻t的子數(shù)據(jù)集為ys:t=(ys,…,yt)。假設(shè)時(shí)序y存在k個(gè)變點(diǎn)，則y被分割成k+1個(gè)不同區(qū)段。記第j個(gè)變點(diǎn)的位置為τj(j=1,…,k)，固定τ0=0、τk+1=n，得到變點(diǎn)集合τ=(τ0,…,τk+1)，第l個(gè)區(qū)段包括數(shù)據(jù)yτl-1+1,…,yτl(l=1,…,k+1)?；谧钚』杀竞瘮?shù)思想，求解時(shí)序變點(diǎn)的位置與個(gè)數(shù)。對交通流觀測值y，引入一個(gè)包含特征參數(shù)θ的成本函數(shù)γ(y;θ)。定義子數(shù)據(jù)集ys:t的成本函數(shù)：

(1)

即特征參數(shù)θ與子數(shù)據(jù)集中每個(gè)觀測值成本函數(shù)總和的最小值。進(jìn)而得到分割整個(gè)數(shù)據(jù)集的懲罰成本函數(shù)：

(2)

式中，β為待定懲罰參數(shù)且滿足β>0。β的大小對變點(diǎn)的位置與個(gè)數(shù)有重大影響[24]，其值越大，估計(jì)出的變點(diǎn)個(gè)數(shù)越少。

為監(jiān)測時(shí)序的均值突變，通常采用平方損失函數(shù)[25]：

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

(3)

作為分割成本。然而，在線檢測時(shí)此函數(shù)易受異常值影響。只有有界成本函數(shù)對于任意極端異常值的存在是穩(wěn)健的[23]。最簡單的成本函數(shù)就是雙權(quán)損失(biweight loss)函數(shù)[26]：

(4)

該函數(shù)通過引入閾值K，使得它對極端異常值具有穩(wěn)健性且可保證成本函數(shù)有界。在此基礎(chǔ)上，利用FPOP算法動(dòng)態(tài)求解懲罰最小化問題。

對數(shù)據(jù)集y1:t(t=1,…,n)，設(shè)候選變點(diǎn)集St={τ=τ1:k:0<τ1<…<τk

(5)

假設(shè)距離當(dāng)前時(shí)刻t最近的區(qū)段特征參數(shù)為θ，定義：

(6)

γ(yt;θ)+β}]

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

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

(7)

于是，Qt(θ)關(guān)鍵取決于Qt-1(θ)與Qt-1+β。將成本函數(shù)γ(yt;θ)視為θ的函數(shù)，如視雙權(quán)損失函數(shù)為θ的分段二次函數(shù)。交通流參數(shù)時(shí)序均值必然在極值范圍內(nèi)，若θ在數(shù)據(jù)集極值區(qū)間上取值，則式(7)最小化問題可拆分為兩步，第一步：

(8)

第二步：

(9)

因此，只需遞推計(jì)算Qt(θ)并存儲時(shí)刻t的最小成本及變點(diǎn)位置，就可以實(shí)現(xiàn)均值變點(diǎn)的在線檢測。

2 路段旅行時(shí)間預(yù)測方法

在車輛行駛軌跡途徑路段各交叉口的前提下，路段起止卡口系統(tǒng)先后采集到同一車輛的采集時(shí)間差即為車輛旅行時(shí)間。它為車輛行經(jīng)路段的實(shí)際花費(fèi)成本，其值越小，表明交通運(yùn)行狀態(tài)越好，路段越通暢；反之，越擁堵。

由于車牌識別錯(cuò)誤、漏檢等系統(tǒng)誤差的存在，原始數(shù)據(jù)存在噪聲；同時(shí)，在某些情況下，如偶然停車、中途離開等真實(shí)數(shù)據(jù)偏差的存在，使得車輛旅行時(shí)間不能反映整個(gè)交通流實(shí)際運(yùn)行狀態(tài)。因此，為屏蔽不合理車輛旅行時(shí)間帶來的影響，當(dāng)車輛經(jīng)過起止卡口的時(shí)差小于某一臨界值D時(shí)，才采集該車旅行時(shí)間?？紤]到短時(shí)在線推送的必要性及數(shù)據(jù)采集的可靠性，當(dāng)檢測到的車輛數(shù)不低于2時(shí)，直接采用中位數(shù)法[1]獲取路段旅行時(shí)間；若某時(shí)段檢測到的車輛數(shù)低于2，不對該時(shí)段觀測值進(jìn)行填補(bǔ)，變點(diǎn)檢測時(shí)不計(jì)分割成本即可。實(shí)際數(shù)據(jù)處理時(shí)，由于公交車行經(jīng)站臺需停車上下客，故將其剔除。雖然出租車也存在停車待客現(xiàn)象，但考慮到它作為交通需求者便捷出行的首選，對交通運(yùn)行狀態(tài)的評估起著關(guān)鍵作用，將其保留。

(10)

(11)

式中，N為旅行時(shí)間預(yù)測時(shí)序長度，I(·)為示性函數(shù)。

3 實(shí)例測試

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

表2 研究路段算法參數(shù)Tab.2 Algorithm parameters of the research road sections s

3.1 路段旅行時(shí)間均值變點(diǎn)

采用R-FPOP算法對測試集各路段旅行時(shí)間時(shí)序進(jìn)行在線均值變點(diǎn)檢測。以7月29日路段I為例，除時(shí)序起止點(diǎn)外，共在線檢測出8個(gè)變點(diǎn)，區(qū)段示意見圖1(a)。從圖1(a)中可以發(fā)現(xiàn)，在交通需求的隨機(jī)擾動(dòng)下，路段旅行時(shí)間均值跳躍現(xiàn)象明顯，呈現(xiàn)出由一種穩(wěn)定態(tài)突變到另一種穩(wěn)定態(tài)的隨機(jī)現(xiàn)象。由圖1(b)可知，在異常值干擾的情況下，在線變點(diǎn)仍然能被快速檢測，最短檢測延遲時(shí)間為2 s。

利用動(dòng)態(tài)規(guī)劃思想，由在線變點(diǎn)檢測結(jié)果遞推得到全天時(shí)序的最優(yōu)分割，即離線變點(diǎn)，結(jié)果如圖2所示。由圖2可知，各路段離線均值變點(diǎn)時(shí)域上分布不均勻，如 [10:00-12:00)兩小時(shí)內(nèi)，路段IV共檢測出9個(gè)變點(diǎn)，而路段I只檢測出1個(gè)變點(diǎn)。這也反映了旅行時(shí)間集群性與均值變點(diǎn)隨機(jī)性特點(diǎn)。以路段IV為例，離線變點(diǎn)τ3(09:36)、τ4(10:22)、τ5(10:32)、τ6(10:36) 劃分得到區(qū)段yτ3+1:τ4、yτ4+1:τ5、yτ5+1:τ6的旅行時(shí)間均值分別為139.83 (s)、391.17 (s)、651.00 (s)，τ4、τ5處跳躍度分別為251.34 (s)、259.83 (s)?？梢园l(fā)現(xiàn)，各區(qū)段旅行時(shí)間徒升、跳躍幅度大，[10:24-10:34)行經(jīng)路段IV的出行成本為[09:38-10:24)的2.80倍。若“10:24”檢測到旅行時(shí)間突變同時(shí)發(fā)布誘導(dǎo)信息，有助于出行者及時(shí)規(guī)劃調(diào)整行車路線。從圖2也可發(fā)現(xiàn)，受貴陽市一環(huán)商業(yè)經(jīng)濟(jì)圈交通需求的影響，高峰時(shí)段旅行時(shí)間跳躍現(xiàn)象頻繁且跳躍度波動(dòng)較大。采用非參數(shù)Wilcoxon秩檢驗(yàn)，評估離線變點(diǎn)是否將相鄰時(shí)序長度均大于15的實(shí)際序列準(zhǔn)確劃分。顯著性水平0.01下，相鄰區(qū)段均值檢驗(yàn)p值均顯著，這實(shí)證了R-FPOP算法檢測的均值變點(diǎn)有效且檢測性能優(yōu)。

圖1 均值變點(diǎn)在線檢測結(jié)果(7月29日)Fig.1 Online detection results of the mean change points (July 29)

圖2 均值變點(diǎn)離線檢測結(jié)果(7月29日)Fig.2 Offline detection results of the mean change points (July 29)

進(jìn)一步分析車輛日記錄缺失比不低于10%的全數(shù)據(jù)集上在線檢測的旅行時(shí)間均值變點(diǎn)特征。在頻率分布基礎(chǔ)上，利用核密度法估計(jì)均值變點(diǎn)時(shí)域分布的密度曲線，結(jié)果見圖3。從圖3可以看出，各研究路段旅行時(shí)間均值變點(diǎn)時(shí)域分布有較大差異，路段I、IV變點(diǎn)主要集中在早高峰，而路段II、III變點(diǎn)在晚高峰出現(xiàn)的概率略高于早高峰，這與路段雙向各時(shí)段的交通需求密切相關(guān)。路段A是相鄰片區(qū)大部分車輛由東向西進(jìn)入貴陽市一環(huán)的首選，路段B緊鄰集醫(yī)療、教育、金融為一體的繁華經(jīng)濟(jì)生活圈，這兩條路段早高峰的交通發(fā)生量相對較大。若向出行者及時(shí)發(fā)布旅行時(shí)間歷史均值及其突變概率，可在一定程度上合理引導(dǎo)其規(guī)劃最優(yōu)路線，進(jìn)而均衡路網(wǎng)交通需求。

圖3 研究路段在線變點(diǎn)時(shí)域分布Fig.3 Temporal distributions of the online change points of the research road sections

3.2 路段旅行時(shí)間預(yù)測

圖4 旅行時(shí)間預(yù)測區(qū)間估計(jì)結(jié)果(7月29日)Fig.4 Estimation results of the travel time prediction intervals (July 29)

從圖4可以看出，各路段旅行時(shí)間時(shí)序雖波動(dòng)較大，但預(yù)測時(shí)序與真實(shí)時(shí)序整體走勢相契合。由表3可知，測試集上路段I-IV旅行時(shí)間平均MAPE分別為13.47%、11.53%、10.01%、9.88%，整體平均MAPE為11.22%，這說明時(shí)序的變化趨勢得到了較好預(yù)測。由表4可知，測試集上路段I-IV平均覆蓋率分別為81.67%、78.31%、79.23%、78.94%，整體平均覆蓋率為79.54%，預(yù)測精度較高，這說明提出的預(yù)測方法具有一定的實(shí)時(shí)性與有效性。由此，可為導(dǎo)航系統(tǒng)智能推送路段旅行時(shí)間預(yù)測值及其預(yù)測區(qū)間，將路段出行成本量化，從而誘導(dǎo)交通需求者擇優(yōu)出行，進(jìn)而緩解交通擁堵，提高城市道路使用率。

表3 測試集旅行時(shí)間預(yù)測誤差百分比絕對值均值Tab.3 Mean absolute percentage error of the travel time predictions for test set %

表4 測試集旅行時(shí)間預(yù)測區(qū)間覆蓋率Tab.4 Coverage ratio of the travel time prediction intervals for test set %

綜上，結(jié)合路段旅行時(shí)間的均值突變信息對旅行時(shí)間進(jìn)行預(yù)測，得到了較準(zhǔn)確的預(yù)測結(jié)果，方法的突出優(yōu)點(diǎn)在于它建模簡單、可操作性強(qiáng)，能夠滿足在線智能推送的需要。實(shí)際應(yīng)用時(shí)，若實(shí)時(shí)數(shù)據(jù)長時(shí)段缺失，可與歷史數(shù)據(jù)進(jìn)行時(shí)空模式匹配來進(jìn)行預(yù)測。

4 結(jié)論

(1)在實(shí)時(shí)獲取車牌識別數(shù)據(jù)的情況下，本文利用穩(wěn)健的變點(diǎn)檢測算法對路段旅行時(shí)間均值變點(diǎn)進(jìn)行在線檢測，將其結(jié)果用于預(yù)測旅行時(shí)間。研究發(fā)現(xiàn)R-FPOP算法可以較好的辨識旅行時(shí)間均值突變且檢測延遲小，均值變點(diǎn)具有隨機(jī)性且高峰期內(nèi)出現(xiàn)的概率較大；推送的旅行時(shí)間平均MAPE為11.22%、預(yù)測區(qū)間平均覆蓋率為79.54%，預(yù)測效果優(yōu)良。

(2)本文方法建模簡單且操作性強(qiáng)，對于導(dǎo)航系統(tǒng)路段旅行時(shí)間的精準(zhǔn)推送以及交通信息服務(wù)等具有一定的支撐作用。為保證卡口數(shù)據(jù)采集質(zhì)量，研究路段較短，進(jìn)一步需結(jié)合信號燈的影響以及多元時(shí)間序列在線變點(diǎn)檢測方法，探究出行路線旅行時(shí)間的預(yù)測。