龐俊彪，胡安靜 ，黃 晶，杜 勇，于海濤

(1.北京工業(yè)大學(xué) 信息學(xué)部 北京多媒體與智能軟件技術(shù)重點(diǎn)實(shí)驗(yàn)室，北京 100124；2.北京市交通信息中心，北京 100161)

0 引 言

交通在現(xiàn)代社會(huì)中扮演重要的角色，基于聯(lián)合國(guó)人口署公布的報(bào)告：城市人口的增長(zhǎng)率每年以大約1.5%的比例增長(zhǎng)，預(yù)計(jì)在2050年，有大約64億城市居住人口[1]。城市人口的增長(zhǎng)將引發(fā)總出行需求的增長(zhǎng)，就有限的交通資源來(lái)說(shuō)，高效的公交系統(tǒng)既有利于降低城市交通擁堵，提高城市交通運(yùn)轉(zhuǎn)效率，同時(shí)也能減少汽車尾氣排放，提升城市空氣質(zhì)量。在我國(guó)人口數(shù)量多、密度高，城市土地資源緊張，在城市化進(jìn)程加快的過(guò)程中，優(yōu)先發(fā)展城市公共交通是一項(xiàng)利于城市可持續(xù)發(fā)展的重要任務(wù)[2]。

考慮到發(fā)展公共交通帶來(lái)的益處，城市公共交通管理部門希望引進(jìn)相關(guān)的技術(shù)向乘客提供一些公交信息，從而提高交通服務(wù)水平[3]。在美國(guó)，有研究人員針對(duì)乘客所關(guān)心的公交信息種類進(jìn)行問(wèn)卷調(diào)查[4]：在眾多的公交信息中，最讓人關(guān)心的信息之一即為公交車到站時(shí)間。所以，準(zhǔn)確預(yù)測(cè)公交車到站時(shí)間并及時(shí)將信息傳遞給用戶，是提高服務(wù)水平的關(guān)鍵性一步[5]。準(zhǔn)確的到站時(shí)間預(yù)測(cè)，可以有效減少用戶的等待時(shí)間，提高服務(wù)質(zhì)量[6]，方便和鼓勵(lì)用戶使用公共交通出行。正因?yàn)楣坏秸緯r(shí)間預(yù)測(cè)的重要性，使其成為一項(xiàng)重要的研究課題[7]。

在現(xiàn)實(shí)生活中，由于交通運(yùn)輸?shù)碾S機(jī)性，如路口的延時(shí)、用戶在時(shí)間和空間上需求的波動(dòng)、天氣情況等因素，公交到站時(shí)間很難進(jìn)行預(yù)測(cè)。早年間，大多數(shù)公交車到站時(shí)間預(yù)測(cè)的研究，主要是通過(guò)大量調(diào)查，著重于預(yù)測(cè)模型的建立[8-9]。直到1999年，基于自動(dòng)車輛定位技術(shù)(automatic vehicle location，AVL)的全球定位系統(tǒng)(global position system，GPS)的出現(xiàn)，使研究發(fā)生了質(zhì)的飛躍[10-11]。隨后，簡(jiǎn)單的線性預(yù)測(cè)模型被非線性預(yù)測(cè)模型取代，例如核函數(shù)機(jī)[12]、神經(jīng)網(wǎng)絡(luò)[13]等。然而正如O’Sullivan在文獻(xiàn)[14]中關(guān)于公交到站時(shí)間預(yù)測(cè)不確定性的討論所提到的：“公交到站時(shí)間預(yù)測(cè)問(wèn)題的復(fù)雜性在于，公交運(yùn)行時(shí)間是非線性和復(fù)雜的多種因素交互作用的結(jié)果?！?/p>

1 現(xiàn)有方法

回顧現(xiàn)有的大多數(shù)預(yù)測(cè)算法，公交到站時(shí)間預(yù)測(cè)算法根據(jù)原理的不同，大體可以分為三大類：基于回歸算法、基于濾波算法、基于搜索算法。

1.1 基于回歸算法

在基于回歸算法中，將公交到站時(shí)間作為受其他時(shí)空因素控制函數(shù)的響應(yīng)量。因此這類算法之間最大的差異在于，如何定義到站時(shí)間和其他時(shí)空因素之間的非線性關(guān)系。該類算法包括以下四種：

(1)SPB[8](SVM on probe buses)算法中首先將路徑劃分成路段，隨后從運(yùn)行在下游路段的前一輛公交作為探針，提出了四種特征作為模型的輸入。支持向量機(jī)和支持向量回歸的非線性，從數(shù)學(xué)本質(zhì)上來(lái)說(shuō)都來(lái)源于核函數(shù)。但確定核函數(shù)及其相應(yīng)參數(shù)較為困難，計(jì)算復(fù)雜度大，不適用于解決大規(guī)模計(jì)算量問(wèn)題[15]。實(shí)驗(yàn)中通過(guò)公開(kāi)的源代碼實(shí)現(xiàn)SVM算法。

(2)LRT[16](linear regression on trajectories)算法假設(shè)公交行進(jìn)時(shí)間服從多元高斯分布，故而預(yù)計(jì)到站時(shí)間為公交到達(dá)目標(biāo)站點(diǎn)的后驗(yàn)期望。

(3)AMM[17](additive mixed model)算法使用半?yún)?shù)模型來(lái)建立多因素模型，使用周末與否、當(dāng)前時(shí)間、行進(jìn)距離等因素，用函數(shù)來(lái)描述這些因素與公交到站時(shí)間之間的關(guān)系。文中利用R語(yǔ)言的MGCV包實(shí)現(xiàn)了AMM算法。

(4)MLP[18](multilayer perceptron)算法中使用了三種特征：當(dāng)前時(shí)間、當(dāng)前位置、與目標(biāo)站點(diǎn)之間的距離。多層感知機(jī)是一種特殊的前向傳播神經(jīng)網(wǎng)絡(luò)算法[19]，在本次實(shí)現(xiàn)中遵循原文的設(shè)計(jì)，選擇和調(diào)整隱含層節(jié)點(diǎn)個(gè)數(shù)，報(bào)告節(jié)點(diǎn)數(shù)為15時(shí)得到的最好結(jié)果。文中使用MATLAB中的newff函數(shù)實(shí)現(xiàn)該算法。

1.2 基于濾波算法

遵循經(jīng)典貝葉斯預(yù)測(cè)原理，基于濾波算法根據(jù)預(yù)先提供的路段信息，預(yù)測(cè)給定路段的行程時(shí)間，從而實(shí)現(xiàn)公交到站時(shí)間的預(yù)測(cè)。通過(guò)定義或者利用相應(yīng)的模型學(xué)習(xí)公交車運(yùn)行的動(dòng)力系統(tǒng)，以遞歸的方式進(jìn)行公交車到站時(shí)間預(yù)測(cè)。

卡爾曼濾波器是這類模型的典型代表。它是現(xiàn)代控制領(lǐng)域的一種重要方法，通過(guò)一系列的遞歸數(shù)學(xué)公式，即狀態(tài)方程和觀測(cè)方程組成的線性隨機(jī)系統(tǒng)來(lái)描述，它是一種最優(yōu)化自回歸數(shù)據(jù)處理算法，采用線性無(wú)偏最小均方誤差估計(jì)準(zhǔn)則，對(duì)過(guò)程的狀態(tài)進(jìn)行預(yù)測(cè)。

KFP[20](Kalman filter with probe buses)算法首先將路徑劃分為路段，而后學(xué)習(xí)動(dòng)態(tài)濾波器。實(shí)現(xiàn)過(guò)程中使用期望最大化實(shí)現(xiàn)線性動(dòng)態(tài)濾波。

1.3 基于搜索算法

影響交通的因素眾多，而這一類模型采取了“用替換代替預(yù)測(cè)”的策略來(lái)避免考慮這些因素。簡(jiǎn)單地假定在相似的交通環(huán)境下，公交車到達(dá)各個(gè)站點(diǎn)的時(shí)間是接近的。這種方法一般會(huì)以當(dāng)前車輛的通行時(shí)間作為依據(jù)，去搜索一些相似的歷史數(shù)據(jù)。

基于搜索算法在所預(yù)測(cè)公交運(yùn)行的交通狀況與歷史數(shù)據(jù)相似的情況下，預(yù)測(cè)結(jié)果較好。為了提高準(zhǔn)確率，將一天的時(shí)間按照定義的時(shí)間塊進(jìn)行分層[21]。但當(dāng)處理大數(shù)量軌跡數(shù)據(jù)時(shí)，k-NN的計(jì)算復(fù)雜度將會(huì)很大。

k-NN[20]算法和KR[16](kernel regression)算法均是基于搜索的算法，通過(guò)權(quán)值化歷史相似運(yùn)營(yíng)軌跡進(jìn)行預(yù)測(cè)。如k-NN算法選擇k條和當(dāng)前軌跡最接近的歷史軌跡，獲得這些歷史軌跡到達(dá)下游待預(yù)測(cè)站點(diǎn)的時(shí)間，并分別乘以權(quán)值(如1/K)得到當(dāng)前公交車到達(dá)下游站點(diǎn)的時(shí)間。KR為了達(dá)到非線性[16]，采用基于核函數(shù)(如高斯核，exp(-‖x-y‖2/b))計(jì)算權(quán)值的方法，其中x和y代表當(dāng)前的運(yùn)營(yíng)軌跡和歷史運(yùn)營(yíng)軌跡，b是核的帶寬。實(shí)驗(yàn)中根據(jù)文中的最優(yōu)參數(shù)設(shè)置，設(shè)b=1。

1.4 討 論

雖然現(xiàn)有很多算法，但因?yàn)閿?shù)據(jù)獲取較為困難，導(dǎo)致大多數(shù)算法并沒(méi)有使用大規(guī)模的數(shù)據(jù)集對(duì)其進(jìn)行驗(yàn)證，只使用極少的線路對(duì)算法進(jìn)行性能評(píng)價(jià)，所以無(wú)法比較算法的準(zhǔn)確性。并且在不同的數(shù)據(jù)集上進(jìn)行的實(shí)驗(yàn)無(wú)法公平地比較各算法的性能，每種算法在不同的條件下會(huì)有不同的結(jié)果，比如某算法可能在短距離上的預(yù)測(cè)比較差，但在長(zhǎng)距離的預(yù)測(cè)上卻表現(xiàn)較好，所以各種算法缺少在同一數(shù)據(jù)集上進(jìn)行對(duì)比。

2 大規(guī)模公交運(yùn)營(yíng)數(shù)據(jù)集的構(gòu)建

目前，針對(duì)公交車到站預(yù)測(cè)問(wèn)題，尚沒(méi)有公認(rèn)的大規(guī)模數(shù)據(jù)集，故文中選擇了北京47條公交線路進(jìn)行數(shù)據(jù)采集和預(yù)處理，并建立了北京市公交運(yùn)營(yíng)數(shù)據(jù)集。這些運(yùn)營(yíng)線路在北京市的分布如圖1所示，其中黑色線條表示公交車的路徑軌跡，它們幾乎覆蓋了北京市城區(qū)的主要干道。

將該數(shù)據(jù)集和其他研究所用到的數(shù)據(jù)集在線路數(shù)量、線路長(zhǎng)度、站點(diǎn)數(shù)量等方面進(jìn)行了比較，如表1所示，說(shuō)明了數(shù)據(jù)集的無(wú)偏性和全面性。

數(shù)據(jù)集線路數(shù)量線路長(zhǎng)度/km站點(diǎn)數(shù)量車輛數(shù)量運(yùn)營(yíng)次數(shù)最小值/最大值均值±標(biāo)準(zhǔn)差最小值/最大值均值±標(biāo)準(zhǔn)差最小值/最大值均值±標(biāo)準(zhǔn)差最小值/最大值均值±標(biāo)準(zhǔn)差文獻(xiàn)[14]118.8718.875959--1 5701 570文獻(xiàn)[15]44/1511±5.215/5427.8±17.9--1 276/7 8823 324.5±3 082.8文獻(xiàn)[8]20.6/0.7?0.7±0.133--224/237229.7±6.7文中475.4/24.612.0±4.36/3918.9±6.311/5822.7±8.8718/3 0091 606.5±527.6

注：文獻(xiàn)[8]只使用了兩條線路的部分只含有3個(gè)站臺(tái)的區(qū)間，作為個(gè)案研究，所以線路長(zhǎng)度相對(duì)較短。

2.1 公交運(yùn)營(yíng)數(shù)據(jù)描述

數(shù)據(jù)集共兩部分：公交的動(dòng)態(tài)GPS數(shù)據(jù)；道路網(wǎng)的靜態(tài)信息，如公交站臺(tái)的位置，路口的位置，每個(gè)公交站臺(tái)的相關(guān)統(tǒng)計(jì)量。

公交動(dòng)態(tài)GPS數(shù)據(jù)從北京的47條線路，共1 089輛公交車中收集，數(shù)據(jù)時(shí)間跨度為2015年2月1號(hào)至2015年2月28號(hào)。每條GPS數(shù)據(jù)包括以下信息：公交車的經(jīng)緯度坐標(biāo)，時(shí)間戳，公交號(hào)，線路號(hào)。每30 s產(chǎn)生一條GPS數(shù)據(jù)，且最大位置誤差為50 m。但由于高層建筑或天橋造成的信號(hào)傳輸?shù)淖枞?，GPS數(shù)據(jù)中存在誤差數(shù)據(jù)。因此通過(guò)建立城市的邊界，過(guò)濾這種錯(cuò)誤的GPS數(shù)據(jù)，實(shí)驗(yàn)中設(shè)置經(jīng)度范圍為110～200，緯度范圍為30～50，作為北京市的邊界。

道路網(wǎng)的靜態(tài)信息包括：公交站臺(tái)的位置，線路號(hào)，行車方向，路口位置，公交站臺(tái)的規(guī)模(每個(gè)站臺(tái)有多少種線路的公交?？?。其中路口預(yù)示有時(shí)間延后的可能性，公交站臺(tái)的規(guī)模間接提供了公交在該站臺(tái)可能停駐的時(shí)長(zhǎng)。

2.2 大規(guī)模公交運(yùn)營(yíng)數(shù)據(jù)集構(gòu)建

將GPS數(shù)據(jù)和靜態(tài)信息數(shù)據(jù)協(xié)同映射為“到達(dá)時(shí)間-行駛距離數(shù)據(jù)對(duì)”。通過(guò)計(jì)算兩個(gè)連續(xù)GPS數(shù)據(jù)點(diǎn)之間的距離，首先累積兩點(diǎn)之間的距離，得到了行進(jìn)距離。接著需要解決以下兩個(gè)問(wèn)題：將每個(gè)公交站臺(tái)映射到行進(jìn)距離中；獲得每個(gè)站臺(tái)的到達(dá)時(shí)間。

為了解決這兩個(gè)問(wèn)題，將每個(gè)站點(diǎn)的GPS坐標(biāo)映射到行進(jìn)距離中，通過(guò)插值得到相應(yīng)的到達(dá)時(shí)間。

這一步驟中通過(guò)克里金插值法(Kriging interpolation)[21]的泛化算法，高斯過(guò)程(Gaussian process)[16]，得到插值點(diǎn)。由此，GPS數(shù)據(jù)和站點(diǎn)位置最終轉(zhuǎn)化為一個(gè)時(shí)間空間聯(lián)合的軌跡。

3 實(shí) 驗(yàn)

3.1 評(píng)估量設(shè)置

為了公平地評(píng)估每種算法的總體性能，使用平均絕對(duì)誤差(mean absolute error，MAE)、均方根誤差(root mean square error，RMSE)以及平均絕對(duì)百分比(mean absolute percentage error，MAPE)來(lái)評(píng)價(jià)預(yù)測(cè)精度，具體公式如下：

(3)

其中，i表示該線路的第i次運(yùn)營(yíng)；N表示運(yùn)營(yíng)的總量；K表示該線路站點(diǎn)的數(shù)量。

3.2 結(jié)果與討論

分別用上述七種算法在測(cè)試集上進(jìn)行實(shí)驗(yàn)對(duì)比。將47條線路按運(yùn)營(yíng)距離分為三類，分別為短距離(0～10 km)、中距離(10～15 km)和長(zhǎng)距離(>15 km)，計(jì)算各線路的MAE、RMSE、MAPE。表2記錄了三種評(píng)價(jià)指標(biāo)在各組的均值和標(biāo)準(zhǔn)差。

表2 現(xiàn)有算法在本數(shù)據(jù)集上實(shí)現(xiàn)結(jié)果的比較

根據(jù)表2可知，KFP算法的總體性能最低，主要原因是KFP作為一種基于濾波算法，在預(yù)測(cè)時(shí)間時(shí)，只依靠下一步準(zhǔn)確的測(cè)量對(duì)預(yù)測(cè)模型進(jìn)行“糾正”。如果從歷史數(shù)據(jù)學(xué)習(xí)到的動(dòng)力系統(tǒng)和現(xiàn)實(shí)的交通情況出入較大，結(jié)果會(huì)迅速變差，并且不斷累積和傳播。

k-NN和KR算法在各種情況和各種指標(biāo)下的表現(xiàn)很相近，正如所預(yù)期的那樣，基于搜索的算法只有在當(dāng)前的交通環(huán)境和搜索到的歷史軌跡所對(duì)應(yīng)的交通環(huán)境相似時(shí)才能預(yù)測(cè)較為準(zhǔn)確的結(jié)果。

值得注意的回歸類算法，如LRT和AMM都取得了較好的結(jié)果，因?yàn)檫@些方法避免了多步超前預(yù)測(cè)的難點(diǎn)，不需要迭代進(jìn)行預(yù)測(cè)。其中LRT并不像k-NN和KR算法，只統(tǒng)計(jì)了歷史相似軌跡，它捕獲了公交不同路段之間運(yùn)行狀態(tài)的線性疊加關(guān)系，故而在大量數(shù)據(jù)的情況下，預(yù)測(cè)效果最好。

AMM是半?yún)?shù)回歸模型的一種。該算法考慮多種因素，通過(guò)函數(shù)來(lái)描述因素和到站時(shí)間之間的關(guān)系，是一個(gè)統(tǒng)計(jì)型原理模型建立框架，靈活地整合了多種因素，算法總體性能較好。

SPB由于其預(yù)測(cè)結(jié)果與支持向量機(jī)中核函數(shù)及其參數(shù)的選擇關(guān)系較大，所以參數(shù)較難控制，且SPB算法使用下游前一輛公交作為探針，所以對(duì)于前一輛公交的信息較為依賴，在某些情況下結(jié)果較差。

MLP算法的核心是典型的多層感知機(jī)網(wǎng)絡(luò)，這是一種具有三層(輸入層、隱藏層和輸出層)神經(jīng)元的前向型神經(jīng)網(wǎng)絡(luò)，文中使用了三種特征，分別為當(dāng)前時(shí)刻，當(dāng)前位置和目標(biāo)站點(diǎn)之間的距離，輸入特征較少，沒(méi)有考慮時(shí)序間的關(guān)聯(lián)性。

此外，由于交通的復(fù)雜性，預(yù)測(cè)其在較遠(yuǎn)時(shí)空下的狀態(tài)相對(duì)較難，還將考慮在不同預(yù)測(cè)距離的情況下，算法的預(yù)測(cè)能力是否會(huì)有較大的變化。將預(yù)測(cè)距離劃分為2 km一段，即[0,2)，[2,4)，[4,6)……通過(guò)圖2來(lái)描述絕對(duì)誤差在不同預(yù)測(cè)距離區(qū)間內(nèi)的分布。

圖2 線路563的分布

為了清晰地比較幾種算法的誤差分布，利用最長(zhǎng)的563路公交線路對(duì)上述7種算法進(jìn)行測(cè)試，如圖2所示。該線路具有29個(gè)站點(diǎn)，且線路穿過(guò)了旅游勝地(香山)，著名的歷史景點(diǎn)(頤和園)，集中商業(yè)區(qū)(中關(guān)村)，分別對(duì)應(yīng)圖2中A區(qū)域、B區(qū)域、C區(qū)域，通常擁有較大客流量，線路總體路況復(fù)雜，對(duì)于預(yù)測(cè)公交到站時(shí)間來(lái)說(shuō)，具有挑戰(zhàn)性，適合進(jìn)行算法性能的比較。實(shí)驗(yàn)結(jié)果如圖3所示，其中圖中折線為第95個(gè)百分位的絕對(duì)誤差。

從圖3可以看出，各算法性能大致與表2中相同，但隨著到達(dá)站臺(tái)距離起點(diǎn)站臺(tái)的距離逐漸增加，預(yù)測(cè)到站時(shí)間的絕對(duì)誤差隨之增加。值得注意的是，由于SPB算法是通過(guò)多條線路來(lái)預(yù)測(cè)公交到站時(shí)間，所以在只使用一條線路時(shí)，SPB算法性能最差也是預(yù)料之中的。

4 結(jié)束語(yǔ)

文中提供了一個(gè)大規(guī)模公交運(yùn)營(yíng)數(shù)據(jù)集，包括不同運(yùn)營(yíng)距離的線路，幾乎覆蓋了北京市城區(qū)的主要干道。與其他研究所用到的數(shù)據(jù)集進(jìn)行了比較，表明該數(shù)據(jù)集有無(wú)偏性、全面性以及大規(guī)模等特點(diǎn)，為公平地比較現(xiàn)有算法提供了可靠準(zhǔn)確的數(shù)據(jù)基礎(chǔ)。在將各算法按照原設(shè)計(jì)實(shí)現(xiàn)后，在該數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對(duì)比，發(fā)現(xiàn)基于回歸算法的各方法具有更穩(wěn)定的性能。且各方法在不同長(zhǎng)度線路上的結(jié)果中LRT算法的結(jié)果最好且穩(wěn)定。

隨著線路的行進(jìn)，公交到站時(shí)間預(yù)測(cè)的準(zhǔn)確性越來(lái)越差，從絕對(duì)誤差看出預(yù)測(cè)到站時(shí)間越來(lái)越不準(zhǔn)確。所以從預(yù)測(cè)準(zhǔn)確度的角度看，到站預(yù)測(cè)算法還有很大的研究空間。尤其是如何融合多種異構(gòu)信息進(jìn)行預(yù)測(cè)，目前只能關(guān)聯(lián)時(shí)間、空間兩種因素，而對(duì)于路況、道路約束、天氣等因素?zé)o法進(jìn)行建模和利用。這也將是到站時(shí)間預(yù)測(cè)未來(lái)努力的方向之一。