基于Spark與粒子濾波算法的公交到站時間預測系統

劉靖 肖冠烽

摘 要：針對公交車到站時間預測準確性不高的問題，選用具有流式計算特點的粒子濾波（PF）算法，建立了一個公交到站時間預測模型。為更好地解決使用PF算法過程中存在的預測誤差及粒子優化選擇問題，通過引入上一趟公交車的行駛速度和構造觀測值的方法對預測模型進行改進，使之具有更貼近實際路況的公交到站時間預測精度，并且能同時預測多個公交到達時間。基于該模型和Spark平臺實現了一套公交到站時間實時預測軟件系統，所有到站時間預測結果與實際相比，平峰的最大絕對誤差為207s，平均絕對誤差為71.67s;高峰的最大絕對誤差為270s，平均絕對誤差為87.61s，而預測結果的平均絕對誤差在2min以內是公認的理想結果。實驗結果表明，所提模型及實現系統能準確預測公交到站時間，滿足乘客實際需求。

關鍵詞：公交到站時間預測;粒子濾波算法;流計算;Spark

中圖分類號： TP311

文獻標志碼：A

Abstract： To improve the accuracy of bus arrival time prediction， a Particle Filter （PF） algorithm with stream computing characteristic was used to establish a bus arrival time prediction model. In order to solve the problems of prediction error and particle optimization in the process of using PF algorithm， the prediction model was improved by introducing the latest bus speed and constructing observations， making it predict bus arrival time closer to the actual road conditions and simultaneously predict the arrival times of multiple buses. Based on the above model and Spark platform， a real-time bus arrival time prediction software system was implemented. Compared with actual results， for the off-peak period， the maximum absolute error was 207s， and the mean absolute error was 71.67s; for the peak period， the maximum absolute error was 270s， and the mean absolute error was 87.61s. The mean absolute error of the predicted results was within 2min which was a recognized ideal result. The experimental results show that the proposed model and implementated system can accurately predict bus arrival time and meet passengers actual demand.

Key words： bus arrival time prediction; Particle Filter （PF） algorithm; stream computing; Spark

0 引言

構建云計算支撐的智慧交通平臺是大數據等新技術在城市公共交通領域的重要應用，其中，公交車輛到站時間預測是核心研究內容和研究熱點，利用公交大數據及有效數據分析模型準確地預測公交車到站時間，能夠為市民帶來更好的城市出行體驗，對推進城市公共交通的發展、提升智慧交通普及推廣具有重要意義[1]。

對于人口密集、路況復雜多變的城市，很難找到一個通用且準確高效的公交車到站時間預測模型，尤其是那些由于城市建設、道路維護等原因使得公交路線經常發生改變的城市，由于這類狀況的持續時間長短不一，對公交車的到站時間預測是一個很大的挑戰。目前，現有公交車到站時間預測相關研究已取得較多進展，但仍然存在以下問題：首先，基于大數據訓練挖掘的預測模型往往由于訓練的數據量不夠大而導致所構建的模型預測精度不高，難以應對上述復雜公交行駛情況;此外，近年來興起的基于實時數據處理的模型因較多應用限制條件也往往存在預測精度不高的問題。其次，目前大多研究都將重點放在預測模型的理論研究及實驗評估方面，而在實際中，需要的不僅僅是一個適用、準確的模型，更是一個從數據采集、接入、存儲、清洗到數據處理的一整套大數據平臺化的解決方案，上述每一個環節都是公交車到站時間預測系統的重要部分，特別地，預測模型若使用成熟的大數據分析相關技術加以優化支撐，其預測效率將會大大提高。

本文在具有流式計算特點的粒子濾波（Particle Filter， PF）算法的基礎上進行優化，建立了一個公交到站時間預測模型，并通過引入最近上一趟公交車的行駛速度和構造觀測值的方法，改善了使用PF算法預測公交車到站時間時存在的預測誤差及粒子優化選擇問題，使改進后的PF算法具有更高的預測精度，并且能夠同時預測多個公交到達時間。此外，本文還利用Hadoop Spark平臺的優勢，使用Spark Streaming流式計算框架實現了一套基于上述改進模型的公交到站時間實時預測軟件系統，該系統能夠準確高效地預測公交系統中所有未到終點站的公交車到達其后各站點到站時間，充分滿足乘客對公交車到站時間的日常需求。

1 相關工作

公交車到站時間預測模型及方法主要基于機器學習類算法，如支持向量機（Support Vector Machine， SVM）和人工神經網絡等，以及基于濾波算法，如卡爾曼濾波（Kalman Filtering， KF）和粒子濾波（PF）等。典型研究詳述如下。

文獻[2]中使用基于多標簽分類的神經網絡對公交車到站時間進行預測，實驗結果發現神經網絡的表現要好于決策樹、隨機森林和樸素貝葉斯方法;該文還探討了使用AdaBoost算法和RakEL算法的集成神經網絡，發現RakEL集成模型在多標簽精度方面表現得更好。

文獻[3]中提出了一種聚類和神經網絡相結合的公交車到站時間預測模型。該模型中結合了天氣、節假日等因素，分時段對公交車的到站時間進行預測。實驗表明該模型要優于傳統的BP神經網絡，而且因為關鍵算法使用了MapReduce框架進行實現，所以模型適合處理海量數據。基于人工神經網絡進行建模的方法在實際應用中存在兩類問題：首先訓練神經網絡需要大量的數據和時間，一個訓練好的模型很難適用到不同路況中，使得訓練過程需要不間斷地進行，消耗大量的計算能力;其次，計算結果很難即時體現出城市公共交通、道路建設以及路況等這些實時性較高的因素對預測結果的影響。

文獻[4]中將KF算法應用到公交車的到站時間預測問題中，實驗表明使用KF模型或者使用基于KF的混合模型在預測公交車到站時間時具有較好的預測精度。文獻[5]中提出了一種基于SVM和KF算法的快速公交系統到站時間預測混合模型，首先使用SVM對到站時間進行預測，然后使用KF算法對預測結果進行動態調整。實驗表明，該模型的預測精度高于基于KF的預測模型。文獻[6]中提出了一種基于長短期記憶神經網絡和KF算法的公交車到站時間預測模型，同樣先使用長短期記憶神經網絡作為靜態模型進行預測，隨后使用KF模型進行動態調整。實驗表明，聯合使用長短期記憶神經網絡和Kalman模型在預測精度和預測結果穩定性方法要好于聯合使用SVM和Kalman模型。但是KF在非高斯程度較大的系統中，會發生預測精度下降的問題。

文獻[7]中將PF算法運用到公交車到站時間預測的問題中提出了一種基于PF的公交車到站實時預測系統。該文使用相對百分誤差（Mean Absolute Percentage Error， MAPE）以及與基于KF方法作對比的方式對預測結果進行評估，結果表明該文中的PF模型實驗結果的精度優于KF算法，而且該模型能夠較好地捕捉高度變化的路況信息;但文中缺乏將模型在應用層面的實現并需針對實際需求作進一步完善。

2 公交到站時間預測模型

公交到站時間預測模型的分析和建立包括：預測計算需求的分析，基于需求的計算框架的選擇及平臺搭建，基于行駛數據的數據預處理，以及基于計算框架預測算法的選擇及改進，最后給出基于改進PF算法的公交到站時間實時預測模型。

2.1 計算需求的分析

首先需要對公交到站時間預測問題作計算上的需求分析，確定所使用的計算框架，并據此選擇合適的算法來建立預測模型。

2.1.1 計算框架的選擇

經過對呼和浩特公交現狀調研發現，所有公交車上的GPS設備每隔一個固定的時間段（通常為15s）會將自身的包括位置信息在內的行駛數據發送給服務器，這種數據具有實時到達且不受系統管理等流式數據的特點。對于服務器而言，每趟公交車行駛數據的到達時間是可知且均勻的，且數據流量不會發生猛烈的波動。經過以上的分析發現，公交車到站時間實時預測系統的應用場景具有一定的實時計算需求，但是這種計算能力又與Samza和Storm這種實時計算框架在使用場景中提供的計算能力不同。對于公交車的到站時間，計算并不需要發生在每一條GPS記錄到達的時刻，即計算不需要時刻進行，只需要每隔一小段時間對一小批新的GPS記錄計算一次即可。具有小批次處理特點的Spark流計算框架更適合上述應用場景，且計算能力足夠應對預測計算需求[7]。

其次，在對公交車的到站時間進行預測時，往往需要實時數據與歷史數據互相配合來進行計算，而Spark自身的Spark Streaming流計算框架中的窗口操作支持對一段時間（如一天或一周）之內的數據集合進行流式處理，這樣可以滿足預測過程中需要部分歷史數據的需求。

5 結語

本文基于具有流式計算特點的PF算法研究公交到站時間預測問題，通過引入最近上一趟公交車的行駛速度和構造觀測值的方法，構建新的預測模型，解決了使用基本PF算法過程中存在的預測誤差及粒子優化選擇問題。基于該模型和Spark平臺實現一套公交到站時間實時預測軟件系統，實驗結果表明，本文所提模型及實現系統具有較高的公交到達時間預測精度，能滿足公交到站時間的日常需求。

參考文獻：

[1] LI J L， GAO J， YANG Y， et al. Bus arrival time prediction based on mixed model [J]. China Communications， 2017， 14（5）： 38-47.

[2] KEE C Y， WONG L P， KHADER A T， et al. Multi-label classification of estimated time of arrival with ensemble neural networks in bus transportation network [C]// Proceedings of the 2nd IEEE International Conference on Intelligent Transportation Engineering. Piscataway， NJ： IEEE， 2017， pp.150-154.

[3] 謝芳，顧軍華，張素琪，等.基于MapReduce聚類和神經網絡的公交車到站時間預測模型[J].計算機應用，2017，37（S1）：118-122. （XIE F， GU J H， ZHANG S Q， et al. Predicting model of bus arrival time based on MapReduce clustering and neural network [J]. Journal of Computer Applications， 2017， 37（S1）： 118-122.）

[4] YU B， YANG Z， YAO B. Bus arrival time prediction using support vector machines [J]. Journal of Intelligent Transportation Systems， 2006， 10（4）： 151-158.

[5] 陳旭梅，龔輝波，王景楠.基于SVM和Kalman濾波的BRT行程時間預測模型研究[J].交通運輸系統工程與信息，2012，12（4）：29-34. （CHEN X M， GONG H B， WANG J N. BRT vehicle travel time prediction based on SVM and Kalman filter [J]. Journal of Transportation Systems Engineering and Information Technology， 2012， 12（4）： 29-34.）

[6] 范光鵬，孫仁誠，邵峰晶.基于LSTM和Kalman濾波的公交車到站時間預測[J].計算機應用與軟件，2018，35（4）：91-96. （FAN G P， SUN R C， SHAO F J. Bus Arrival time prediction based on LSTM and Kalman filtering [J]. Computer Applications and Software， 2018， 35（4）： 91-96.）

[7] DHIVYABHARATHI B， KUMAR B A， VANAJAKSHI L. Real time bus arrival time prediction system under Indian traffic condition [C]// Proceedings of the 2016 IEEE International Conference on Intelligent Transportation Engineering. Piscataway， NJ： IEEE， 2016：18-22.

[8] ZAHARIA M， CHOWDHURY M， FRANKLIN M J， et al. Spark： cluster computing with working sets [C]// Proceedings of the 2nd USENIX Workshop on Hot Topics in Cloud Computing. Berkeley， CA： USENIX， 2010： 10.

[9] 王法勝，魯明羽，趙清杰，等.粒子濾波算法[J].計算機學報，2014，37（8）：1679-1694. （WANG F S， LU M Y， ZHAO Q J， et al. Particle filtering algorithm [J]. Chinese Journal of Computers， 2014， 37（8）： 1679-1694）.

[10] 周雪梅，彭昌溆，宋興昊，等.基于前車數據的動態公交車輛到站時間預測模型研[J].交通與運輸（學術版），2011（B12）：52-56. （ZHOU X M， PENG C X， SONG X H， et al. Prediction model of dynamic bus arrival time based on the front bus data [J]. Traffic & Transportation， 2011（B12）： 52-56.）

[11] 涂利明.基于前車與經驗數據的車輛到站時間預測模型[J].計算機時代，2015（1）：1-3. （TU L M. Prediction model of bus arrival time based on front bus data and empirical data[J]. Computer Era， 2015（1）： 1-3.）

[12] The Scala Programming Language [EB/OL]. [2017-10-08]. https：//www.scala-lang.org

[13] Apache Kafka： a distributed streaming platform [EB/OL]. [2017-05-03]. http：//kafka.apache.org