劉靖 肖冠烽

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

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

中圖分類號(hào)： TP311

文獻(xiàn)標(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)建云計(jì)算支撐的智慧交通平臺(tái)是大數(shù)據(jù)等新技術(shù)在城市公共交通領(lǐng)域的重要應(yīng)用，其中，公交車輛到站時(shí)間預(yù)測(cè)是核心研究內(nèi)容和研究熱點(diǎn)，利用公交大數(shù)據(jù)及有效數(shù)據(jù)分析模型準(zhǔn)確地預(yù)測(cè)公交車到站時(shí)間，能夠?yàn)槭忻駧砀玫某鞘谐鲂畜w驗(yàn)，對(duì)推進(jìn)城市公共交通的發(fā)展、提升智慧交通普及推廣具有重要意義[1]。

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

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

1 相關(guān)工作

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

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

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

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

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

2 公交到站時(shí)間預(yù)測(cè)模型

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

2.1 計(jì)算需求的分析

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

2.1.1 計(jì)算框架的選擇

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

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

5 結(jié)語

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

參考文獻(xiàn)：

[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ò)的公交車到站時(shí)間預(yù)測(cè)模型[J].計(jì)算機(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行程時(shí)間預(yù)測(cè)模型研究[J].交通運(yùn)輸系統(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濾波的公交車到站時(shí)間預(yù)測(cè)[J].計(jì)算機(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].計(jì)算機(jī)學(xué)報(bào)，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ù)的動(dòng)態(tài)公交車輛到站時(shí)間預(yù)測(cè)模型研[J].交通與運(yùn)輸（學(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)驗(yàn)數(shù)據(jù)的車輛到站時(shí)間預(yù)測(cè)模型[J].計(jì)算機(jī)時(shí)代，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