基于Spark與粒子濾波算法的公交到站時間預(yù)測系統(tǒng)

劉靖 肖冠烽

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

關(guān)鍵詞：公交到站時間預(yù)測;粒子濾波算法;流計算;Spark

中圖分類號： TP311

文獻標(biāo)志碼：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 引言

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

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

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

1 相關(guān)工作

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

文獻[2]中使用基于多標(biāo)簽分類的神經(jīng)網(wǎng)絡(luò)對公交車到站時間進行預(yù)測，實驗結(jié)果發(fā)現(xiàn)神經(jīng)網(wǎng)絡(luò)的表現(xiàn)要好于決策樹、隨機森林和樸素貝葉斯方法;該文還探討了使用AdaBoost算法和RakEL算法的集成神經(jīng)網(wǎng)絡(luò)，發(fā)現(xiàn)RakEL集成模型在多標(biāo)簽精度方面表現(xiàn)得更好。

文獻[3]中提出了一種聚類和神經(jīng)網(wǎng)絡(luò)相結(jié)合的公交車到站時間預(yù)測模型。該模型中結(jié)合了天氣、節(jié)假日等因素，分時段對公交車的到站時間進行預(yù)測。實驗表明該模型要優(yōu)于傳統(tǒng)的BP神經(jīng)網(wǎng)絡(luò)，而且因為關(guān)鍵算法使用了MapReduce框架進行實現(xiàn)，所以模型適合處理海量數(shù)據(jù)?；谌斯ど窠?jīng)網(wǎng)絡(luò)進行建模的方法在實際應(yīng)用中存在兩類問題：首先訓(xùn)練神經(jīng)網(wǎng)絡(luò)需要大量的數(shù)據(jù)和時間，一個訓(xùn)練好的模型很難適用到不同路況中，使得訓(xùn)練過程需要不間斷地進行，消耗大量的計算能力;其次，計算結(jié)果很難即時體現(xiàn)出城市公共交通、道路建設(shè)以及路況等這些實時性較高的因素對預(yù)測結(jié)果的影響。

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

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

2 公交到站時間預(yù)測模型

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

2.1 計算需求的分析

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

2.1.1 計算框架的選擇

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

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

5 結(jié)語

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

參考文獻：

[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īng)網(wǎng)絡(luò)的公交車到站時間預(yù)測模型[J].計算機應(yīng)用，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行程時間預(yù)測模型研究[J].交通運輸系統(tǒng)工程與信息，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濾波的公交車到站時間預(yù)測[J].計算機應(yīng)用與軟件，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].計算機學(xué)報，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] 周雪梅，彭昌溆，宋興昊，等.基于前車數(shù)據(jù)的動態(tài)公交車輛到站時間預(yù)測模型研[J].交通與運輸（學(xué)術(shù)版），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īng)驗數(shù)據(jù)的車輛到站時間預(yù)測模型[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