基于KNN算法的公交到站時間預測

霍 豪，沈金星，鄭長江

基于KNN算法的公交到站時間預測

霍 豪，沈金星，鄭長江

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

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

交通工程；預測模型；近鄰；到站時間；城市公交

0 引 言

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

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

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

1 公交車到站時間預測模型

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

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

表1 公交車運行時段劃分

1.2 KNN算法介紹

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

1.2.1 距離度量值

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

其中，

（4）

1.2.2 預測算法

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

1.3 評價指標

為了驗證到站時間預測模型的可靠性，本文采用平均絕對誤差率（MAPE）作為預測精度的評價指標。其具體計算公式為

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

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

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

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

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

2.2 道路特征數(shù)據

2.2.1 站間距離數(shù)據

圖1 站點間距離計算方法示意

到和之間的地理距離。假設地球為球體，則其上任意兩個位置點1和2之間的球面距離計算公式為：

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

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

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

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

圖2 站間距

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

3 實例分析

3.1 基礎數(shù)據

實驗選取天津市808路公交線路的地理信息數(shù)據，以及2017年10月9~30日共16個工作日早高峰的車輛運行數(shù)據作為實例驗證的基礎數(shù)據，其中，以10月9~24日共12個工作日早高峰的車輛運行數(shù)據作為訓練集，共85組；以10月26日早高峰的數(shù)據作為驗證集，共2組，用以對模型進行標定；以10月30日早高峰的數(shù)據作為測試集，共1組，用以檢驗模型的預測效果。

3.2 模型參數(shù)標定

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

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

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

3.3 其他到站時間預測模型

3.3.1 基于歷史平均值的預測模型

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

3.3.2 無權重KNN模型

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

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

3.3.3 僅以地理距離作為權重的KNN模型

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

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

3.4 模型預測結果對比分析

本文對上述4種預測模型進行對比分析，以MAPE為評價指標，對第15~24站的到站時間進行預測，比較預測效果。

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

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

圖4 不同預測模型下公交到站時間的MAPE值

圖5 不同模型的MAPE平均值和標準差

4 結 論

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

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

[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算法的公交行程時間預測[J]. 交通運輸系統(tǒng)工程與信息, 2019, 19 (2): 116-121.

[9] 李振龍, 張利國, 錢海峰. 基于非參數(shù)回歸的短時交通流預測研究綜述[J]. 交通運輸工程與信息學報, 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

國家自然科學基金（51808187）；江蘇自然科學基金（BK20170879）；中央高校基本科研業(yè)務費專項資金（2019B13514）；江蘇省博士后科研資助計劃項目（1701086B）

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

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

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

（責任編輯：劉娉婷）