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

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

0 引 言

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

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

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

1 現(xiàn)有方法

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

1.1 基于回歸算法

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

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

(2)LRT[16](linear regression on trajectories)算法假設公交行進時間服從多元高斯分布，故而預計到站時間為公交到達目標站點的后驗期望。

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

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

1.2 基于濾波算法

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

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

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

1.3 基于搜索算法

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

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

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

1.4 討 論

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

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

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

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

數(shù)據(jù)集線路數(shù)量線路長度/km站點數(shù)量車輛數(shù)量運營次數(shù)最小值/最大值均值±標準差最小值/最大值均值±標準差最小值/最大值均值±標準差最小值/最大值均值±標準差文獻[14]118.8718.875959--1 5701 570文獻[15]44/1511±5.215/5427.8±17.9--1 276/7 8823 324.5±3 082.8文獻[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

注：文獻[8]只使用了兩條線路的部分只含有3個站臺的區(qū)間，作為個案研究，所以線路長度相對較短。

2.1 公交運營數(shù)據(jù)描述

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

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

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

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

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

為了解決這兩個問題，將每個站點的GPS坐標映射到行進距離中，通過插值得到相應的到達時間。

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

3 實 驗

3.1 評估量設置

為了公平地評估每種算法的總體性能，使用平均絕對誤差(mean absolute error，MAE)、均方根誤差(root mean square error，RMSE)以及平均絕對百分比(mean absolute percentage error，MAPE)來評價預測精度，具體公式如下：

(3)

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

3.2 結(jié)果與討論

分別用上述七種算法在測試集上進行實驗對比。將47條線路按運營距離分為三類，分別為短距離(0～10 km)、中距離(10～15 km)和長距離(>15 km)，計算各線路的MAE、RMSE、MAPE。表2記錄了三種評價指標在各組的均值和標準差。

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

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

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

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

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

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

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

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

圖2 線路563的分布

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

從圖3可以看出，各算法性能大致與表2中相同，但隨著到達站臺距離起點站臺的距離逐漸增加，預測到站時間的絕對誤差隨之增加。值得注意的是，由于SPB算法是通過多條線路來預測公交到站時間，所以在只使用一條線路時，SPB算法性能最差也是預料之中的。

4 結(jié)束語

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

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