基于KNN算法的公交到站時(shí)間預(yù)測

霍 豪，沈金星，鄭長江

基于KNN算法的公交到站時(shí)間預(yù)測

霍 豪，沈金星，鄭長江

（河海大學(xué)，土木與交通學(xué)院，南京 210098）

為提高城市公交到站時(shí)間預(yù)測的準(zhǔn)確性和穩(wěn)定性，提出了一種基于最近鄰（-nearest- neighbor，KNN）算法的公交到站時(shí)間預(yù)測模型。該模型考慮了上下游車站的距離對(duì)二者公交到站時(shí)間相關(guān)性的影響，以及信號(hào)燈數(shù)和彎道數(shù)對(duì)到站時(shí)間的影響。以天津市808路公交線為例，選取1個(gè)月的公交運(yùn)行數(shù)據(jù)對(duì)模型進(jìn)行了訓(xùn)練和驗(yàn)證，并與基于歷史平均值的模型、無權(quán)重KNN模型以及僅以地理距離作為權(quán)重的KNN模型進(jìn)行對(duì)比。結(jié)果表明該模型的預(yù)測誤差較小（平均MAPE為15.17%），且MAPE的標(biāo)準(zhǔn)差為7.28%，明顯小于其他3個(gè)模型，說明該預(yù)測模型在公交車到站時(shí)間預(yù)測上具有較好的精度和穩(wěn)定性。

交通工程；預(yù)測模型；近鄰；到站時(shí)間；城市公交

0 引 言

快速增長的交通量以及由此產(chǎn)生的交通擁堵和環(huán)境污染，是影響世界各國城市居民生活質(zhì)量日益嚴(yán)重的問題，而發(fā)展公共交通是緩解該問題的一種可行且具有可持續(xù)性的方式[1]。Caulfield等[2]的一項(xiàng)調(diào)查表明，公交車的到站時(shí)間是乘客最需要的信息。提供實(shí)時(shí)準(zhǔn)確的到站時(shí)間信息可以幫助出行者減少等待時(shí)間，科學(xué)地規(guī)劃出行，提升乘車體驗(yàn)。到站時(shí)間預(yù)測系統(tǒng)的成功實(shí)施將會(huì)鼓勵(lì)和吸引更多居民從其他交通方式轉(zhuǎn)向公共交通，這種轉(zhuǎn)變能夠減少道路上車輛的數(shù)量，從而緩解擁堵、降低污染[3]。所以，對(duì)公交到站時(shí)間預(yù)測方法的研究具有重要意義。

國內(nèi)外學(xué)者對(duì)公交車到站時(shí)間預(yù)測進(jìn)行過大量的研究。Ramakrishna等[4]利用公交車的定位數(shù)據(jù)、客流數(shù)據(jù)以及瞬時(shí)速度等特征，構(gòu)建了多元回歸模型。該模型對(duì)于發(fā)車頻率高而且高峰特性明顯的線路預(yù)測效果較好，但是沒有考慮非高峰期的預(yù)測精度，也沒有考慮路段彎道數(shù)等道路特征數(shù)據(jù)。Yu等[5]首次利用多條線路數(shù)據(jù)對(duì)公交到站時(shí)間進(jìn)行預(yù)測，證明了此方法比使用單條線路的預(yù)測效果更好，且基于支持向量機(jī)（SVM）的模型比其他模型預(yù)測效果更好，但對(duì)于大樣本，這種方法存在訓(xùn)練時(shí)間過長的問題。Dhivyabharathi等[6]提出了一種基于粒子濾波的公交到站時(shí)間預(yù)測方法，但評(píng)價(jià)指標(biāo)MAPE約為17%，預(yù)測精度不高，誤差較大。Lee等[7]基于最近鄰軌跡（Nearest Neighborhood Trajectory，NNT）的方法，從歷史軌跡數(shù)據(jù)中搜索與當(dāng)前公交車已駛過的路段“最相似”的軌跡，在預(yù)測當(dāng)前公交的后續(xù)行程時(shí)間方面，該方法顯示出很好的效果，而且不用考慮各種外部和內(nèi)部因素。王芳杰等[8]構(gòu)建了基于LightGBM（Light Gradient Boosting Machine）算法的公交行程時(shí)間預(yù)測模型，模型的特征選擇考慮了車輛行駛數(shù)據(jù)、天氣數(shù)據(jù)以及道路特征數(shù)據(jù)，與基于歷史平均值和卡爾曼濾波的行程時(shí)間預(yù)測模型進(jìn)行對(duì)比后的結(jié)果表明，該模型的預(yù)測效果明顯優(yōu)于其他兩個(gè)。

針對(duì)以上問題，本文基于最近鄰（-nearest- neighbor，KNN）算法，探索公交到站時(shí)間模式的相似性，在考慮信號(hào)燈和實(shí)際路況對(duì)公交到站時(shí)間影響基礎(chǔ)上，提出一種新的公交到站預(yù)測模型。本文最后將使用天津市808路公交線路1個(gè)月的到站時(shí)間數(shù)據(jù)作為數(shù)據(jù)庫，將預(yù)測結(jié)果與實(shí)際到達(dá)時(shí)間進(jìn)行比較，以驗(yàn)證模型的準(zhǔn)確性。

1 公交車到站時(shí)間預(yù)測模型

1.1 數(shù)據(jù)狀態(tài)劃分

城市道路交通運(yùn)行狀態(tài)受時(shí)段的影響較大，工作日和非工作日的道路交通情況有著明顯不同，同一天中高峰期和平峰期的交通流量也有較大變化，從而導(dǎo)致公交車的運(yùn)行速度出現(xiàn)明顯差異，所以預(yù)測公交車到站時(shí)間，應(yīng)將工作日和非工作日分別考慮，并按照車輛的運(yùn)行時(shí)間，將公交車的運(yùn)行時(shí)段劃分為4種，如表1所示。

表1 公交車運(yùn)行時(shí)段劃分

1.2 KNN算法介紹

KNN算法是一種廣泛使用的非參數(shù)回歸方法，它根據(jù)參數(shù)和數(shù)據(jù)的相似度，從歷史數(shù)據(jù)中搜索與當(dāng)前狀態(tài)最為接近的近鄰值用于預(yù)測。該算法的基本原理和優(yōu)缺點(diǎn)在李振龍等[9]的研究中有過詳細(xì)介紹，Akbari等[10]則給出了其一般性的公式。它假定數(shù)據(jù)庫中的相似數(shù)據(jù)之間存在相關(guān)性，因此，計(jì)算的時(shí)候只需要利用大量數(shù)據(jù)，而無需提前定義特定的數(shù)學(xué)模型和參數(shù)。KNN算法充分體現(xiàn)了公交到站時(shí)間預(yù)測的非參數(shù)特征，模型參數(shù)包括狀態(tài)向量、距離度量值、近鄰數(shù)，以及預(yù)測算法。由于到站時(shí)間具有較強(qiáng)的空間關(guān)聯(lián)性，故選擇與當(dāng)前站點(diǎn)鄰近的個(gè)上游站點(diǎn)的到站時(shí)間間隔構(gòu)成狀態(tài)向量，用于描述樣本特征。

1.2.1 距離度量值

距離度量值用來度量訓(xùn)練集和測試集數(shù)據(jù)之間的相關(guān)性。在KNN算法中，采用距離度量值將訓(xùn)練集數(shù)據(jù)與測試集數(shù)據(jù)進(jìn)行匹配，搜索二者之間距離最近的個(gè)數(shù)據(jù)，并將這些數(shù)據(jù)作為預(yù)測數(shù)據(jù)，輸入到預(yù)測算法中。由于交通狀態(tài)隨著空間而變化，應(yīng)根據(jù)上游站點(diǎn)和預(yù)測站點(diǎn)間的地理位置密切程度來為距離度量值分配不同的權(quán)重—— 距離預(yù)測站點(diǎn)越遠(yuǎn)的站點(diǎn)，與預(yù)測站點(diǎn)到站時(shí)間規(guī)律差別越大，從而對(duì)距離度量值的貢獻(xiàn)也越大，故本文在計(jì)算時(shí)，加入地理距離值作為權(quán)重系數(shù)。此外，由于信號(hào)燈和彎道對(duì)公交車行駛時(shí)間影響較大，本文還考慮了信號(hào)燈數(shù)和彎道數(shù)這兩項(xiàng)道路特征對(duì)距離度量值的影響。已有研究中，似乎未見關(guān)于此問題的論述，本文僅將信號(hào)燈數(shù)和彎道數(shù)簡單相加，作為該問題的初步探索，認(rèn)為上游某站點(diǎn)與待預(yù)測站點(diǎn)在該值上相差越多，該上游站點(diǎn)對(duì)距離度量值的貢獻(xiàn)就越大，故加入該差值的絕對(duì)值，作為距離度量值中的另一個(gè)系數(shù)。由于存在地理距離和道路特征兩個(gè)權(quán)重系數(shù)，為了消除二者單位和取值范圍差異的影響，需要對(duì)二者進(jìn)行歸一化處理，本文采用常見的min-max標(biāo)準(zhǔn)化方法進(jìn)行該操作。以下將描述怎樣用個(gè)近鄰點(diǎn)的數(shù)據(jù)來預(yù)測公交車從第1站到第站的時(shí)間間隔，即從歷史數(shù)據(jù)中選擇的相似數(shù)據(jù)的個(gè)數(shù)。為狀態(tài)向量的維度，即與待預(yù)測站點(diǎn)進(jìn)行匹配的車站數(shù)。目前有多種距離度量方式可用于近鄰的搜索，例如切比雪夫距離、馬氏距離、歐氏距離等。但用于公交到站時(shí)間預(yù)測時(shí)，通常采用的是歐氏距離作為度量指標(biāo)，本文在此基礎(chǔ)上考慮上述兩項(xiàng)權(quán)重系數(shù)，采用相關(guān)系數(shù)加權(quán)歐氏距離的方法來計(jì)算距離度量值：

其中，

（4）

1.2.2 預(yù)測算法

預(yù)測算法描述了怎樣用搜索到的組最近鄰數(shù)據(jù)來預(yù)測目標(biāo)站點(diǎn)的狀態(tài)向量值。本文采用對(duì)個(gè)最近鄰按距離度量值加權(quán)平均的方法，將較大的權(quán)值賦給較近的近鄰，得到公交車從第1站到第站的到站時(shí)間間隔為：

1.3 評(píng)價(jià)指標(biāo)

為了驗(yàn)證到站時(shí)間預(yù)測模型的可靠性，本文采用平均絕對(duì)誤差率（MAPE）作為預(yù)測精度的評(píng)價(jià)指標(biāo)。其具體計(jì)算公式為

2 數(shù)據(jù)介紹和處理

2.1 公交車運(yùn)行數(shù)據(jù)

本文數(shù)據(jù)采用天津市808路公交車在2017年10月份所有工作日的運(yùn)行數(shù)據(jù)，數(shù)據(jù)字段格式如表2所示。

對(duì)以上數(shù)據(jù)進(jìn)行處理分析，當(dāng)“下一站點(diǎn)編號(hào)”（O_NEXTSTATIONNO）發(fā)生變化時(shí)，說明司機(jī)對(duì)車輛到站提醒裝置進(jìn)行了操作以提醒乘客到站，故將該字段發(fā)生變化后的第一條數(shù)據(jù)判定為公交車的到站數(shù)據(jù)，用公交車到達(dá)下游站點(diǎn)的時(shí)刻減去到達(dá)上游站點(diǎn)的時(shí)刻即得兩站之間的到站時(shí)間間隔。

表2 公交車運(yùn)行數(shù)據(jù)格式

2.2 道路特征數(shù)據(jù)

2.2.1 站間距離數(shù)據(jù)

圖1 站點(diǎn)間距離計(jì)算方法示意

到和之間的地理距離。假設(shè)地球?yàn)榍蝮w，則其上任意兩個(gè)位置點(diǎn)1和2之間的球面距離計(jì)算公式為：

式中：表示地球半徑，取6 370.856 km；表示經(jīng)度值；表示緯度值。

由該方法可求得天津市808路公交第5~24站各站點(diǎn)與其上一站之間的距離，如圖2所示。

2.2.2 信號(hào)燈數(shù)和彎道數(shù)

通過在電子地圖上調(diào)查和記錄，得到該條公交線路上第5~24站各站點(diǎn)與其上一站之間的信號(hào)燈數(shù)和彎道數(shù)，如表3所示。

圖2 站間距

表3 與前一站之間的信號(hào)燈數(shù)和彎道數(shù)

3 實(shí)例分析

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

實(shí)驗(yàn)選取天津市808路公交線路的地理信息數(shù)據(jù)，以及2017年10月9~30日共16個(gè)工作日早高峰的車輛運(yùn)行數(shù)據(jù)作為實(shí)例驗(yàn)證的基礎(chǔ)數(shù)據(jù)，其中，以10月9~24日共12個(gè)工作日早高峰的車輛運(yùn)行數(shù)據(jù)作為訓(xùn)練集，共85組；以10月26日早高峰的數(shù)據(jù)作為驗(yàn)證集，共2組，用以對(duì)模型進(jìn)行標(biāo)定；以10月30日早高峰的數(shù)據(jù)作為測試集，共1組，用以檢驗(yàn)?zāi)Ｐ偷念A(yù)測效果。

3.2 模型參數(shù)標(biāo)定

KNN模型的預(yù)測效果依賴于不同近鄰數(shù)和狀態(tài)向量的維度的組合方式，通過對(duì)訓(xùn)練集和驗(yàn)證集數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，得到不同（）組合方式下的MAPE值，選取MAPE最小的組合方式對(duì)模型進(jìn)行標(biāo)定，如圖3所示，這里的最大值取15，的最大值取10。

從圖3中可以看出，工作日早高峰的（）組合方式中，當(dāng)=4、=9時(shí)，MAPE取得最小值，為13.02%，故以該參數(shù)組合標(biāo)定本文所提出的預(yù)測模型。

圖3 不同（K，D）組合下的MAPE值

3.3 其他到站時(shí)間預(yù)測模型

3.3.1 基于歷史平均值的預(yù)測模型

以公交車在2017年10月9~24日中工作 日早高峰各個(gè)公交站的到站時(shí)間為歷史數(shù)據(jù)，計(jì)算得出公交車到站時(shí)間的均值作為預(yù)測值； 以10月30日早高峰公交車的到站時(shí)間作為測試數(shù)據(jù)。

3.3.2 無權(quán)重KNN模型

該模型的預(yù)測算法與本文提出的模型相同，但在計(jì)算模型參數(shù)中的距離度量值時(shí)，不考慮權(quán)重，公式為：

式中各自變量的含義與公式（1）中相同。

3.3.3 僅以地理距離作為權(quán)重的KNN模型

該模型的預(yù)測算法與本文提出的模型相同，但在計(jì)算模型參數(shù)中的距離度量值時(shí)，權(quán)重僅考慮匹配站點(diǎn)與待預(yù)測站點(diǎn)之間的地理距離，不考慮道信號(hào)燈數(shù)和彎道數(shù)，公式為：

式中各自變量的含義與公式（1）和（2）中相同。

3.4 模型預(yù)測結(jié)果對(duì)比分析

本文對(duì)上述4種預(yù)測模型進(jìn)行對(duì)比分析，以MAPE為評(píng)價(jià)指標(biāo)，對(duì)第15~24站的到站時(shí)間進(jìn)行預(yù)測，比較預(yù)測效果。

這4種模型預(yù)測到站時(shí)間的MAPE如圖4所示，其中帶權(quán)重KNN1表示僅以地理距離作為權(quán)重的KNN模型，帶權(quán)重KNN2表示本文提出的預(yù)測模型。由圖可知，在第15站、21站、23站等預(yù)測精度整體偏低且預(yù)測難度較大的站點(diǎn)，帶權(quán)重KNN2模型都取得了4個(gè)模型中最低或者次低的MAPE值，預(yù)測效果較好，而在第16站、19站、24站等預(yù)測難度較小的站點(diǎn)，無權(quán)重KNN模型和帶權(quán)重KNN1模型預(yù)測精度更高。

圖5顯示了不同模型預(yù)測10個(gè)站點(diǎn)到站時(shí)間的MAPE平均值和標(biāo)準(zhǔn)差，可以看到，無權(quán)重KNN模型、帶權(quán)重KNN1模型和帶權(quán)重KNN2模型的平均預(yù)測誤差比較接近，分別為14.45%、14.01%、15.17%，較歷史平均法的預(yù)測效果（MAPE均值為17.14%）有明顯提升，其中帶權(quán)重KNN1模型最小，說明其平均預(yù)測精度最高；而帶權(quán)重KNN2模型的MAPE標(biāo)準(zhǔn)差最小，為7.28%，說明其預(yù)測的穩(wěn)定性最好。

圖4 不同預(yù)測模型下公交到站時(shí)間的MAPE值

圖5 不同模型的MAPE平均值和標(biāo)準(zhǔn)差

4 結(jié) 論

本文通過考慮公交車運(yùn)行過程中對(duì)預(yù)測結(jié)果會(huì)產(chǎn)生影響的道路特征，提出了一種基于KNN算法的公交到站時(shí)間預(yù)測模型，并與基于歷史平均值的預(yù)測模型、無權(quán)重KNN模型以及僅以地理距離作為權(quán)重的KNN模型的預(yù)測結(jié)果進(jìn)行對(duì)比，結(jié)果顯示，本文提出的預(yù)測模型在預(yù)測難度較大的站點(diǎn)上的MAPE指標(biāo)明顯低于其他模型，且預(yù)測的穩(wěn)定性得到有效提升。

在后續(xù)研究中，會(huì)采用待預(yù)測站點(diǎn)的信號(hào)燈數(shù)和彎道數(shù)較多的公交線路進(jìn)行進(jìn)一步實(shí)驗(yàn)，同時(shí)利用更多不同時(shí)段和地點(diǎn)的數(shù)據(jù)對(duì)模型進(jìn)行比較和驗(yàn)證。此外，也將定量分析地理距離、信號(hào)燈數(shù)和彎道數(shù)在計(jì)算模型參數(shù)中的距離度量值時(shí)的權(quán)重，進(jìn)一步提高模型的預(yù)測精度。

[1] SHIMAMOTO H, MURAYAMA N, FUJIWARA A, et al. Evaluation of an existing bus network using a transit network optimisation model: a case study of the Hiroshima City Bus network [J]. Transportation, 2010, 37 (5): 801-823.

[2] CAULFIELD B and O’MAHONY M. A stated preference analysis of real-time public transit stop information [J]. Journal of Public Transportation, 2009, 12 (3): 1-20.

[3] LE T P L and TRINH T A. Encouraging public transport use to reduce traffic congestion and air pollutant: a case study of Ho Chi Minh City, Vietnam [J]. Proceeding of Sustainable Development of Civil, Urban And Transportation Engineering, 2016 (142): 236-243.

[4] RAMAKFISHNA Y, RAMAKRISHNA P, LAKSHMANANV, et a1．Use of GPS probe data and passenger data for prediction of bus transit travel time [C]// American Society of Civil Engineers. Transportation Land Use, Planning, and Air Quality Congress. Reston, VA United States: American Society of Civil Engineers, 2008: 124-133.

[5] YU B, LAM W H K, and TAM M L. Bus arrival time prediction at bus stop with multiple routes [J]. Transportation Research Part C: Emerging Technologies, 2011, 19 (6): 1157-1170.

[6] DHIVYABHARATHI B, KUMAR B A, and VANAJAKSHIL L. Real time bus arrival time prediction system under Indian traffic condition[C]// 2016 IEEE International Conference on Intelligent Transportation Engineering (ICITE) , Singapore: IEEE, 2016: 18-22.

[7] LEE W C, SI W P, CHEN L J, et al. HTTP: A new framework for bus travel time prediction based on historical trajectories[C]// 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2012) , 2012: 279-288.

[8] 王芳杰, 王福建, 王雨晨, 等. 基于LightGBM算法的公交行程時(shí)間預(yù)測[J]. 交通運(yùn)輸系統(tǒng)工程與信息, 2019, 19 (2): 116-121.

[9] 李振龍, 張利國, 錢海峰. 基于非參數(shù)回歸的短時(shí)交通流預(yù)測研究綜述[J]. 交通運(yùn)輸工程與信息學(xué)報(bào), 2008, 6 (4): 34-39.

[10] AKBARI M, OVERLOOP P J V, and AFSHAR A. Clusterednearest neighbor algorithm for daily inflow forecasting [J]. Water Resources Management, 2011, 25 (5): 1341-1357.

Bus Arrival Time Prediction Based on KNN Algorithm

HUO Hao，SHEN Jin-xing，ZHENG Chang-jiang

(College of Civil and Transportation Engineering, Hohai University, Nanjing 210098, China)

To improve the accuracy and stability of predicting urban bus arrival times, a bus arrival time prediction model based on-nearest-neighbor (KNN) algorithm is proposed. The model considers the effects of the distances between upstream and downstream stations on their correlations with bus arrival times. It also considers the effects of the numbers of signals and turns on the arrival times. With a single bus line (No. 808) in Tianjin, China used as an example, the model is trained and verified using one month’s bus running data and compared with three models: historical mean, the non-weighted KNN model, and the KNN model in which only geographical distances are used as weights. The results show that the prediction error of this model is small, where the average mean absolute percentage error (MAPE) is 15.17%. In addition, the standard deviation of MAPE is 7. 28%, which is significantly less than those of the other three models, indicating that the prediction model exhibits higher accuracy and stability in predicting bus arrival times.

traffic engineering; prediction model;-nearest-neighbor; arrival time; urban bus

1672-4747（2020）04-0076-08

U491.1+4

A

10.3969/j.issn.1672-4747.2020.04.010

2020-03-07

國家自然科學(xué)基金（51808187）；江蘇自然科學(xué)基金（BK20170879）；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金（2019B13514）；江蘇省博士后科研資助計(jì)劃項(xiàng)目（1701086B）

霍豪（1994—），男，漢族，湖北黃岡人，河海大學(xué)土木與交通學(xué)院碩士研究生，主要研究方向：交通運(yùn)輸規(guī)劃與管理，E-mail：8536744@qq.com

鄭長江（1966—），男，漢族，安徽滁州人，博士、教授、博士生導(dǎo)師，主要研究方向：交通運(yùn)輸規(guī)劃與管理、交通信息與控制和交通安全等，E-mail: zheng@hhu.edu.cn

霍豪，沈金星，鄭長江. 基于KNN算法的公交到站時(shí)間預(yù)測[J]. 交通運(yùn)輸工程與信息學(xué)報(bào)，2020, 18(4): 76-82, 102

（責(zé)任編輯：劉娉婷）