基于非參數(shù)回歸-粒子濾波模型的公交到站時間預(yù)測

張孝梅，陳旭梅，張 溪

(1. 北京交通大學(xué) 綜合交通運(yùn)輸大數(shù)據(jù)應(yīng)用技術(shù)交通運(yùn)輸行業(yè)重點(diǎn)實驗室，北京 100044；2.北京交通發(fā)展研究院，北京 100073)

0 引言

隨著生活節(jié)奏的加快，大眾越來越重視時間管理，以期合理分配和高效利用時間。特別是對通勤者而言，時間管理的精細(xì)化程度已從以前的1 h逐漸縮短到15 min，甚至更短；與此同時，他們對出行時間的敏感程度也越來越高；若其選擇公交方式通勤，則期望盡可能掌握公交到站時間，減少等待時間，提高出行效率。

考慮到公交系統(tǒng)具有較強(qiáng)的時變性、非線性等特點(diǎn)，學(xué)者們已提出很多關(guān)于公交到站時間預(yù)測的算法[1-5]，主要有基于歷史數(shù)據(jù)的模型、神經(jīng)網(wǎng)絡(luò)模型[2-3]、支持向量機(jī)模型[4]及卡爾曼濾波模型[5]等方法。其中，基于歷史數(shù)據(jù)的模型對歷史數(shù)據(jù)依賴性很高；支持向量機(jī)模型的參數(shù)確定較為困難且不適用于實時預(yù)測[6]；神經(jīng)網(wǎng)絡(luò)模型結(jié)構(gòu)較難確定且其存在過擬合或欠擬合的問題[7]；卡爾曼濾波模型是將非線性問題通過函數(shù)簡化為線性問題，預(yù)測精度取決于函數(shù)的準(zhǔn)確性[8]。

粒子濾波，是一種基于蒙特卡洛思想進(jìn)行采樣的算法，在處理復(fù)雜非線性問題時具有優(yōu)越性[9]。不少學(xué)者也探索性地將粒子濾波應(yīng)用到公交到站時間預(yù)測中[10-11]。H Chen[8]提出基于大數(shù)據(jù)驅(qū)動的粒子濾波算法來預(yù)測車輛的單程運(yùn)行時間。H Chen[12]又提出基于非顯性狀態(tài)方程的粒子濾波算法來預(yù)測短期、中長期內(nèi)的車輛運(yùn)行時間。E Hans[13]等人構(gòu)建了公交車輛在站停留時間及站間運(yùn)行時間模型，并利用真實數(shù)據(jù)對模型參數(shù)進(jìn)行校正，采用粒子濾波算法對固定線路全天的公交到站時間進(jìn)行預(yù)測。任遠(yuǎn)[7]、B Dhivyabharathi[14]、趙衍青[15]等人將路段進(jìn)行等長度劃分，利用粒子濾波算法對公交車輛在高峰、平峰時段的運(yùn)行時間進(jìn)行分段逐步預(yù)測。而目前研究成果在涉及對站間速度的預(yù)測時，多是采用加權(quán)平均的方法簡化處理，忽略了速度傳達(dá)出的實時交通信息，比如天氣狀況、道路狀況等。

為提高預(yù)測精度并充分利用數(shù)據(jù)信息，本研究基于歷史數(shù)據(jù)，利用非參數(shù)回歸方法對站間速度進(jìn)行預(yù)測，進(jìn)而利用粒子濾波方法對到站時間進(jìn)行預(yù)測。同時，從速度自身的時變特性出發(fā)，在預(yù)測站間速度時采用擴(kuò)展歐式距離作為相似度的度量準(zhǔn)則，保證了相似曲線的相似性。本研究所提的方法預(yù)測精度較高、魯棒性較強(qiáng)，為公交到站時間的預(yù)測提供了一種新思路。

1 粒子濾波算法概述

Xt=f(Xt-1,Wt-1),

(1)

Zt=g(Xt,Vt),

(2)

式中，Wt-1,Vt分別為系統(tǒng)的過程噪聲和觀測噪聲。

為更好理解粒子濾波公式，本研究引入圖1說明。其中，由Xt-1指向Xt的單向箭頭表示P(Xt/Xt-1)，即狀態(tài)值Xt-1與狀態(tài)值Xt之間的轉(zhuǎn)移概率，由式(1)計算得到；由Xt指向Zt的單向箭頭表示P(Zt/Xt)，即狀態(tài)值Xt與測量值Zt之間的測量概率，由式(2)計算得到。在粒子濾波中，轉(zhuǎn)移概率和測量概率可為任意函數(shù)。

圖1 粒子濾波抽象示意圖Fig.1 Abstract schematic diagram of particle filtering

本研究采用的粒子濾波算法基于采樣-重要性重采樣思想。首先借助序貫重要性方法(SIS)進(jìn)行粒子采樣，即可充分利用過去的粒子狀態(tài)集預(yù)測當(dāng)前的粒子狀態(tài)集[16]，采樣函數(shù)服從特定的概率分布q(Xt/X1:t-1)；然后根據(jù)當(dāng)前的粒子狀態(tài)集及相應(yīng)權(quán)重得到當(dāng)前系統(tǒng)狀態(tài)值，權(quán)值由式(3)遞推估計得到。

(3)

式(3)中，最優(yōu)的q(Xt/X1:t-1)應(yīng)為真實的后驗概率函數(shù)p(Xt/X1:t-1,Z1:t)，但鑒于真實的后驗概率函數(shù)難以獲得，便采用轉(zhuǎn)移概率函數(shù)p(Xt/Xt-1)替代q(Xt/X1:t-1)[11]，則式(3)可簡化為式(4)，并對權(quán)值進(jìn)行歸一化處理[16]，以便得到系統(tǒng)狀態(tài)值Xt，如式(5)所示。

(4)

(5)

基于序貫重要性采樣的粒子濾波會出現(xiàn)粒子退化的現(xiàn)象[12]，即經(jīng)過一定的迭代次數(shù)后，樣本的概率分布函數(shù)可能會集中于少數(shù)粒子，換句話說，是由少量的幾個數(shù)值代替原來的分布函數(shù)。為解決該問題，本研究采用重要性重采樣方法進(jìn)行粒子重采樣，做法如下：基于式(5)得到的歸一化權(quán)值的分布函數(shù)作為粒子采樣的分布函數(shù),其粒子狀態(tài)值的確定仍采用轉(zhuǎn)移概率函數(shù)p(Xt/Xt-1)[16]。式(3)則進(jìn)一步簡化為式(6)。

(6)

粒子濾波算法流程[10]如下：

Step1：t=0，進(jìn)行粒子初始化；

Step2：Fort=1:T。

(1)重要性采樣

(2)計算權(quán)重

Fori=1:N，根據(jù)式(6)計算權(quán)值 End。

(3)權(quán)重歸一化

Fori=1:N，根據(jù)式(5)使得權(quán)值歸一化 End。

(4)重采樣

根據(jù)權(quán)值歸一化后的分布W(X1:t)，重新采樣N次；

End。

2 公交車輛到站時間預(yù)測模型

首先構(gòu)建了基于粒子濾波算法的公交車輛到站時間預(yù)測模型。為提高到站時間模型的預(yù)測精度，進(jìn)一步對模型參數(shù)中涉及的站間速度進(jìn)行預(yù)測說明。最后，對預(yù)測公交車輛到站時間的算法進(jìn)行詳細(xì)闡述。

2.1 到站時間預(yù)測模型

公交到站時間構(gòu)成要素一般劃分為站點(diǎn)停留時間、區(qū)間運(yùn)行時間[17-18]、交叉口延誤時間[19]等。本研究在描述公交車到站時間的狀態(tài)方程時，以到站時間為參考點(diǎn)，將站點(diǎn)停留時間及交叉口延誤時間等其他構(gòu)成要素均包含在區(qū)間運(yùn)行時間內(nèi)，則基于粒子濾波算法的公交到站時間預(yù)測模型如下。

狀態(tài)方程：

(7)

式中，Xt為t站點(diǎn)公交車輛到站時間；A為系數(shù)矩陣；Xt-1為t-1站點(diǎn)公交車輛到站時間；Lt為站間距長度；Vt為根據(jù)歷史數(shù)據(jù)預(yù)測的站間速度；W為系統(tǒng)的過程噪聲。

測量方程：

Zt=HXt+V，

(8)

式中，H為系數(shù)矩陣；Zt為觀測到的公交車輛到達(dá)時間；V為測量噪聲。

本研究選取A，H為單位矩陣，假設(shè)W，V服從高斯分布[7,9]，且二者相互獨(dú)立。

2.2 站間速度預(yù)測模型

在對公交車輛到站時間預(yù)測算法介紹之前，先對式(7)中站間速度Vt的預(yù)測過程做出詳細(xì)說明。

假設(shè)站間速度是以天為循環(huán)周期變化[20]，且不同日期的同一時刻站間速度具有很強(qiáng)的相似性。對站間速度的預(yù)測采用非參數(shù)預(yù)測方法。預(yù)測模型的基本思想是，尋找與當(dāng)前速度趨勢相近的速度曲線圖，并通過相似度進(jìn)行衡量，進(jìn)而得到下一站間速度預(yù)測值。因平均站間速度曲線可能具有提前或者滯后的相似性[21]，所以本研究采用擴(kuò)展歐式距離方法作為評價曲線相似度的度量準(zhǔn)則，即分別向前、向后擴(kuò)展一個數(shù)據(jù)點(diǎn)，如圖2所示。因此，同一條相似曲線的3個相鄰點(diǎn)會取3次參與預(yù)測站間速度，從一定程度上減少一些噪音干擾，進(jìn)而保證了相似曲線的精確性。

圖2 速度曲線相似圖Fig.2 Similarity diagram of speed curves

其中，擴(kuò)展歐式距離公式說明見式(9)～式(11)。式(9)為同位相似曲線對應(yīng)的計算公式，式(10)為錯位相似(提前)曲線對應(yīng)的計算公式，式(11)為錯位相似(滯后)曲線對應(yīng)的計算公式。

(9)

(10)

(11)

式中，t為待預(yù)測站間;j為待預(yù)測站間t的前j個站間;Vt-j為待預(yù)測速度曲線中站間t-j已預(yù)測的速度;V′t-j為站間t-j的歷史速度;d為待預(yù)測速度曲線與歷史速度曲線之間的距離。

預(yù)測站間速度Vt的算法流程如下：

Step1：初始化：對線路運(yùn)行方向前4個站間的站間速度V1，V2，V3，V4進(jìn)行賦值；

Step2：對該線路其他的站間速度Vt進(jìn)行順序預(yù)測。

Fort=5∶T。

(1)構(gòu)建歷史數(shù)據(jù)集：從歷史站間速度數(shù)據(jù)庫中挑選出同條線路每天相近時刻運(yùn)行的站間速度曲線。

(2)根據(jù)式(9)～式(11)，挑選出與前4個站間速度Vt-1，Vt-2，Vt-3，Vt-4變化趨勢最相似的K條歷史曲線。

(3)獲取K條歷史曲線中站間速度V′t，并根據(jù)曲線相似性大小給予權(quán)重，預(yù)測得到站間速度Vt，見式(12)。

End

(12)

2.3 公交到站時間預(yù)測算法流程

基于粒子濾波的公交到站時間預(yù)測模型的算法流程如下。

Step 0：選定此次預(yù)測的線路編號、日期、時間點(diǎn)。

Step 1：t=0，粒子初始化；

Step2：Fort=1∶T。

(1)重要性采樣

(2)預(yù)測

(3)計算權(quán)重

Fori=1∶N根據(jù)式(6)計算權(quán)值 End。

(4)權(quán)重歸一化

(5)重采樣

根據(jù)步驟(4)得到的分布W(X1∶t)，產(chǎn)生新的N個粒子，即Xi′t～W(X1∶t)；

End。

3 案例分析

3.1 基礎(chǔ)數(shù)據(jù)描述

為驗證模型的有效性及正確性，選取北京市市區(qū)3條典型線路(全天客運(yùn)量均處于較高水平)為研究對象，預(yù)測其早高峰時段的公交車輛到站時間。其中，3條線路分別為公交1路(老山公交場站-四惠樞紐站)、特11路(時代莊園北站-宋家莊樞紐站)、300路快車內(nèi)環(huán)(草橋-草橋)。本研究選取2019年3月1日至3月29日共21個工作日的歷史GPS速度數(shù)據(jù)，對4月1日至4月4日在特定時刻(7:30)發(fā)車后的區(qū)間運(yùn)行速度進(jìn)行預(yù)測，進(jìn)而對公交的到站時間進(jìn)行預(yù)測。

本案例選取的公交到站時間觀測數(shù)據(jù)來源于公交車載GPS技術(shù)采集的逐秒速度數(shù)據(jù)；區(qū)間長度數(shù)據(jù)是基于北京市公交線網(wǎng)，借助ArcGIS計算的站間距離；站間平均速度的歷史數(shù)據(jù)是基于逐秒速度數(shù)據(jù)集成的平均站間速度?？紤]3條線路的最大發(fā)車間隔(由首發(fā)站發(fā)車間隔計算得到，受GPS班次數(shù)據(jù)識別算法的影響)，本研究在選取預(yù)測時間點(diǎn)時增加了10 min的彈性時間。如預(yù)測某一線路發(fā)車時刻為7:30的公交車輛站間運(yùn)行速度，則從歷史速度數(shù)據(jù)庫中選取發(fā)車時刻為7:20—7:40的運(yùn)行數(shù)據(jù)。需要說明的是，彈性時間越大，預(yù)測準(zhǔn)確度越高，但也將相對耗時。

3.2 公交到站時間預(yù)測結(jié)果3.2.1 站間速度預(yù)測結(jié)果

目前，普遍采用加權(quán)平均模型等對站間速度進(jìn)行預(yù)測。圖3為利用非參數(shù)回歸方法、加權(quán)平均法兩種方法，預(yù)測4月1日(星期一)300路快車內(nèi)環(huán)公交發(fā)車時刻為7:30的各站間速度的誤差對比圖。由圖可知，非參數(shù)回歸方法的預(yù)測結(jié)果與實際值更為接近，而加權(quán)平均法預(yù)測結(jié)果與實際值有較大偏差。

圖3 300路快車內(nèi)環(huán)站間速度預(yù)測對比Fig.3 Comparison of predicted average speeds between inner ring stops of No.300 express bus

為進(jìn)一步衡量預(yù)測精度，本研究采用平均絕對誤差(MAE)、標(biāo)準(zhǔn)誤差(RMSE)、平均絕對百分誤差(MAPE)3個指標(biāo)來對兩種方法進(jìn)行評價。計算公式如式(13)～式(15)所示。

(13)

(14)

(15)

式中，Si為區(qū)間速度實際值;S′i為區(qū)間速度預(yù)測值;n為樣本量。

早高峰時段(發(fā)車時刻為7:30)，3條線路的站間速度預(yù)測效果如表1所示。從3條線路的MAE，RMSE及MAPE3個指標(biāo)可看出，非參數(shù)回歸法均優(yōu)于加權(quán)平均法；特別是300路快車內(nèi)環(huán)，基于非參數(shù)回歸方法預(yù)測的站間速度平均絕對誤差為0.64 km/h，平均絕對百分誤差小于1.00%，預(yù)測精度較高，為后續(xù)預(yù)測公交車輛到站時間提供了基礎(chǔ)性數(shù)據(jù)支撐。

表1 早高峰時段站間速度預(yù)測誤差匯總表(一周平均)Tab.1 Prediction errors of speed between stops at morning peak hours (one-week average)

3.2.2 到站時間預(yù)測結(jié)果

圖4為利用非參數(shù)回歸-粒子濾波(本研究所提算法)、加權(quán)平均法-粒子濾波、非參數(shù)回歸-卡爾曼濾波、加權(quán)平均法-卡爾曼濾波4種算法，得出的早高峰時段內(nèi)線路各站點(diǎn)到站時間預(yù)測誤差(一周平均)的對比圖。由圖4可知，利用非參數(shù)回歸-粒子濾波算法得到3條線路的預(yù)測結(jié)果均優(yōu)于其他3種方法,且因為3條線路運(yùn)行情況復(fù)雜程度不同，造成預(yù)測誤差存在差異，300路快車內(nèi)環(huán)的預(yù)測效果要明顯優(yōu)于其他兩條線路。

表2為利用4種算法得出的線路預(yù)測平均誤差匯總表，由表可知，從線路角度來看，4種方法中預(yù)測效果最好的為非參數(shù)回歸-粒子濾波，其次是加權(quán)平均法-粒子濾波算法和非參數(shù)回歸-卡爾曼濾波算法，最后為加權(quán)平均法-卡爾曼濾波算法；利用本研究所提算法得到的1路到站時間的平均絕對誤差均處于1.28 min之內(nèi)，特11路的平均絕對誤差均處于0.97 min之內(nèi)，300路快車內(nèi)環(huán)的平均絕對誤差均處于0.63 min之內(nèi)；3條線路的標(biāo)準(zhǔn)誤差均在3 min內(nèi)，平均絕對百分誤差均小于4%。

圖4 到站時間預(yù)測誤差Fig.4 Prediction errors of bus arrival time

以粒子數(shù)目的變化對該模型的敏感度進(jìn)行分析。以300路快車內(nèi)環(huán)為例，如圖5所示，線路平均到站時間預(yù)測的估計誤差呈帶狀分布，且隨著粒子數(shù)目的增多，標(biāo)準(zhǔn)差越小越穩(wěn)定，即預(yù)測效果越好。

4 結(jié)論

考慮到速度數(shù)據(jù)包含眾多信息，本研究提出了一種基于非參數(shù)回歸-粒子濾波算法，利用歷史速度數(shù)據(jù)趨勢來預(yù)測公交車輛的到站時間模型。

(1)采用非參數(shù)回歸方法，利用歷史趨勢來預(yù)測站間速度的變化趨勢：創(chuàng)造性地對歷史數(shù)據(jù)的選取時刻和站間速度趨勢參照點(diǎn)進(jìn)行拓展，增加模型的預(yù)測魯棒性。結(jié)果表明該方法的預(yù)測精度高于加權(quán)平均方法。

(2)采用粒子濾波算法對公交到站時間進(jìn)行預(yù)測，為避免粒子退化，每次迭代均采用重抽樣技術(shù)；選取北京市內(nèi)3條線路，利用非參數(shù)回歸-粒子濾波(本研究所提算法)、加權(quán)平均法-粒子濾波、非參數(shù)回歸-卡爾曼濾波、加權(quán)平均法-卡爾曼濾波4種算法對公交到站時間進(jìn)行預(yù)測，證明了本研究所提算法的優(yōu)越性；對模型進(jìn)行敏感度分析，發(fā)現(xiàn)隨著粒子數(shù)目的增多，標(biāo)準(zhǔn)差逐漸穩(wěn)定在1.1 min左右，說明模型的穩(wěn)定性較好。

圖5 粒子數(shù)目對模型敏感度的影響Fig.5 Influence of particle number on model sensitivity

未來擬對公交車輛到站時間預(yù)測模型進(jìn)行深入研究，將公交車輛站間運(yùn)行時間進(jìn)行細(xì)化，進(jìn)一步區(qū)分出在站停留時間、交叉口候車時間等成分，使得對站間速度、到站時間的預(yù)測更加合理。