商明菊 胡堯 周江娥 王丹

摘 要：針對城市路段旅行時間精準推送的不足，提出一種基于動態(tài)規(guī)劃變點檢測算法的旅行時間預(yù)測方法。以車牌識別數(shù)據(jù)為研究對象，利用R-FPOP算法對旅行時間均值變點進行在線檢測，研究變點時域分布特征;基于均值變點檢測結(jié)果，預(yù)測旅行時間并給出其預(yù)測區(qū)間。結(jié)果表明：在線檢測出的變點能夠有效辨識旅行時間的均值突變，變點時域分布主要集中在高峰期;旅行時間預(yù)測值對實際序列變化趨勢估計準確，推送的預(yù)測區(qū)間平均覆蓋率為79.54%，具有較優(yōu)的預(yù)測精度。論文方法兼顧旅行時間均值突變且建模簡單，可為路段旅行時間的在線智能推送及交通需求者的路線規(guī)劃提供技術(shù)支持。

關(guān)鍵詞：交通工程;旅行時間預(yù)測;R-FPOP;變點;智能導航

中圖分類號：U491.1

文獻標識碼： A

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

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

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

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

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

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

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

旅行時間預(yù)測值y^t，采用時刻t-1前變點集中距離最近的變點τm后第一個觀測點到時刻t-1時的子數(shù)據(jù)集yτm+1：t-1經(jīng)異常處理后的均值來估計。預(yù)測區(qū)間長度過大是無意義的，基于Sigma原則，定義預(yù)測區(qū)間[y^t-σ^t，y^t+σ^t]。采用異常處理后子數(shù)據(jù)集yτm+1：t-1的標準差作為σ^t的估計。需要特別說明的是，子數(shù)據(jù)集yτm+1：t-1經(jīng)異常處理后：若為空，y^t用y^t-1估計;若時序長度小于2，σ^t用σ^t-1估計。采用預(yù)測誤差百分比絕對值均值（Mean Absolute Percentage Error，MAPE）與預(yù)測區(qū)間覆蓋率（Coverage Ratio，CR）來評價預(yù)測方法性能，計算公式如下：

3 實例測試

選取貴陽市一環(huán)寶山北路、北京路沿線的路段為研究對象，以2017年7月車牌識別數(shù)據(jù)為例，對旅行時間時序進行均值變點檢測，各路段地理位置說明見表1。為估計變點檢測算法參數(shù)，取1日至23日車輛日記錄缺失比不高于10%的數(shù)據(jù)作為訓練集;同時，取24日至30日的數(shù)據(jù)作為測試集，用于檢驗預(yù)測方法的有效性。調(diào)取車輛卡口監(jiān)測信息，對行駛路線與路段卡口方位匹配的車輛，在剔除不符合起止卡口監(jiān)測點時差臨界值D的觀測值后，計錄車輛旅行時間，最后采用中位數(shù)法得到路段旅行時間（單位：s）。為確?？焖偻扑?，采集粒度取2 min，每天共720個觀測值。檢測時段采用時間點標記，如時段[00：00-00：02）記為“00：00”。在訓練集上通過模糊聚類與中位數(shù)法，確定各路段旅行時間臨界值D與噪聲標準差σ^，結(jié)果見表2。

3.1 路段旅行時間均值變點

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

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

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

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

利用在線均值變點實時劃分區(qū)段的子數(shù)據(jù)集來預(yù)測各路段旅行時間，計算預(yù)測值的MAPE與預(yù)測區(qū)間覆蓋率指標來衡量預(yù)測精度，結(jié)果分別見圖4、表3、表4。對旅行時間在線推送方法進行說明：以7月29日路段II為例，假設(shè)當前時刻“10：16”，檢出的最近變點為“09：56”，于是將時段[09：58-10：16）內(nèi)異常處理后觀測值的均值144.11（s）記為y^10：16，同時估計出σ^10：16為10.71（s），進一步得到預(yù)測區(qū)間[133.40，154.82]，真實值150.00（s）被預(yù)測區(qū)間準確覆蓋，預(yù)測誤差百分比絕對值為393%。

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

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

4 結(jié)論

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

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

參考文獻：

[1]趙卓峰，丁維龍，張帥. 海量車牌識別數(shù)據(jù)集上基于時空劃分的旅行時間計算方法[J].電子學報，2016，44（5）：1227-1233.

[2]AHMAD S， LAVIN A， PURDY S， et al. Unsupervised real-time anomaly detection for streaming data[J]. Neurocomputing， 2017，262：134-147.

[3]LV Y， DUAN Y， KANG W， et al. Traffic flow prediction with big data： a deep learning approach[J]. IEEE Transactions on Intelligent Transportation Systems， 2015，16（2）：865-873.

[4]GUO T， XU Z， YAO X， et al. Robust online time series prediction with recurrent neural networks[C]//International Conference on Data Science and Advanced Analytics. Montreal， Canada： IEEE， 2016：816-825.

[5]COMERT G， BEZUGLOV A， CETIN M. Adaptive traffic parameter prediction： effect of number of states and transferability of models[J]. Transportation Research Part C： Emerging Technologies， 2016，72（11）：202-224.

[6]柴華駿，李瑞敏，郭敏. 基于車牌識別數(shù)據(jù)的城市道路旅行時間分布規(guī)律及估計方法研究[J].交通運輸系統(tǒng)工程與信息，2012，12（6）：41-47.

[7]王曉原，雋志才，賈洪飛，等. 交通流突變分析的變點統(tǒng)計方法研究[J].中國公路學報，2002，15（4）：69-74.

[8]JEON S， HONG B. Monte Carlo simulation-based traffic speed forecasting using historical big data[J]. Future Generation Computer Systems， 2016， 65： 182-195.

[9]SUREGAONKAR S， ASHOK S D， KARAR V， et al. Change point monitoring for vehicle incident detection at intersection[C]//International Conference on Science Technology Engineering and Management. Chennai， India： IEEE， 2017：100-105.

[10]YAN Q， SUN Z， GAN Q， et al. Automatic identification of near-stationary traffic states based on the PELT changepoint detection[J]. Transportation Research Part B： Methodological， 2018， 108（2）：39-54.

[11]ARNESEN P， HJELKREM O A. An estimator for traffic breakdown probability based on classification of transitional breakdown events[J]. Transportation Science，2017， 52（3）：593-602.

[12]SHENG R， ZHONG S， BARNETT A G， et al. Effect of traffic legislation on road traffic deaths in Ningbo， China[J]. Annals of Epidemiology，2018， 28（8）：576-581.

[13]ZHAO Z， KOUTSOPOULOS H N， ZHAO J. Detecting pattern changes in individual travel behavior： a Bayesian approach[J]. Transportation Research Part B： Methodological， 2018，112（06）：73-88.

[14]KIDANDO E， MOSES R， SANDO T， et al. Evaluating recurring traffic congestion using change point regression and random variation Markov structured model[J]. Transportation Research Record， 2018， 2672（20）：63-74.

[15]AMINIKHANGHAHI S， COOK D J. A survey of methods for time series change point detection[J]. Knowledge and Information Systems， 2017， 51（2）：339-367.

[16]WU J， CHEN Y， ZHOU S， et al. Online steady-state detection for process control using multiple change-point models and particle filters[J]. IEEE Transactions on Automation Science and Engineering， 2016， 13（2）：688-700.

[17]RIGAILL G. A pruned dynamic programming algorithm to recover the best segmentations with 1 to Kmax change-points[J]. Journal de la Société Francaise de Statistique， 2015， 156（4）：180-205.

[18]JACKSON B， SCARGLE J D， BARNES D， et al. An algorithm for optimal partitioning of data on an interval[J]. IEEE Signal Processing Letters， 2005， 12（2）：105-108.

[19]AUGER I E， LAWRENCE C E. Algorithms for the optimal identification of segment neighborhoods[J]. Bulletin of Mathematical Biology， 1989， 51（1）：39-54.

[20]KILLICK R， FEARNHEAD P， ECKLEY I A. Optimal detection of changepoints with a linear computational cost[J]. Journal of the American Statistical Association， 2012， 107（500）：1590-1598.

[21]TRUONG C， OUDRE L， VAYATIS N. Selective review of offline change point detection methods. ArXiv e-print，2019，1801.00718v2.

[22]MAIDSTONE R， HOCKING T， RIGAILL G， et al. On optimal multiple changepoint algorithms for large data[J]. Statistics and Computing， 2017， 27（2）：519-533.

[23]FEARNHEAD P， RIGAILL G. Changepoint detection in the presence of outliers[J]. Journal of the American Statistical Association， DOI：10.1080/01621459.2017.1385466.

[24]HAYNES K， ECKLEY I A， FEARNHEAD P. Computationally efficient changepoint detection for a range of penalties[J]. Journal of Computational and Graphical Statistics，2017， 26（1）：134-143.

[25]YAO Y C， AU S T. Least-squares estimation of a step function[J]. Sankhy?。篢he Indian Journal of Statistics， Series A，1989，51（3）：370-381.

[26]HUBER P J. Robust statistics[M]//LOVRIC M. International Encyclopedia of Statistical Science. Berlin， Heidelberg： Springer， 2011：1248-1251.

[27]FRYZLEWICZ P. Wild binary segmentation for multiple change-point detection[J]. The Annals of Statistics，2014， 42（6）：2243-2281.

（責任編輯：于慧梅）