基于KNN算法的公交到站时间预测

霍 豪，沈金星，郑长江

基于KNN算法的公交到站时间预测

霍 豪，沈金星，郑长江

（河海大学，土木与交通学院，南京 210098）

为提高城市公交到站时间预测的准确性和稳定性，提出了一种基于最近邻（-nearest- neighbor，KNN）算法的公交到站时间预测模型。该模型考虑了上下游车站的距离对二者公交到站时间相关性的影响，以及信号灯数和弯道数对到站时间的影响。以天津市808路公交线为例，选取1个月的公交运行数据对模型进行了训练和验证，并与基于历史平均值的模型、无权重KNN模型以及仅以地理距离作为权重的KNN模型进行对比。结果表明该模型的预测误差较小（平均MAPE为15.17%），且MAPE的标准差为7.28%，明显小于其他3个模型，说明该预测模型在公交车到站时间预测上具有较好的精度和稳定性。

交通工程；预测模型；近邻；到站时间；城市公交

0 引 言

快速增长的交通量以及由此产生的交通拥堵和环境污染，是影响世界各国城市居民生活质量日益严重的问题，而发展公共交通是缓解该问题的一种可行且具有可持续性的方式[1]。Caulfield等[2]的一项调查表明，公交车的到站时间是乘客最需要的信息。提供实时准确的到站时间信息可以帮助出行者减少等待时间，科学地规划出行，提升乘车体验。到站时间预测系统的成功实施将会鼓励和吸引更多居民从其他交通方式转向公共交通，这种转变能够减少道路上车辆的数量，从而缓解拥堵、降低污染[3]。所以，对公交到站时间预测方法的研究具有重要意义。

国内外学者对公交车到站时间预测进行过大量的研究。Ramakrishna等[4]利用公交车的定位数据、客流数据以及瞬时速度等特征，构建了多元回归模型。该模型对于发车频率高而且高峰特性明显的线路预测效果较好，但是没有考虑非高峰期的预测精度，也没有考虑路段弯道数等道路特征数据。Yu等[5]首次利用多条线路数据对公交到站时间进行预测，证明了此方法比使用单条线路的预测效果更好，且基于支持向量机（SVM）的模型比其他模型预测效果更好，但对于大样本，这种方法存在训练时间过长的问题。Dhivyabharathi等[6]提出了一种基于粒子滤波的公交到站时间预测方法，但评价指标MAPE约为17%，预测精度不高，误差较大。Lee等[7]基于最近邻轨迹（Nearest Neighborhood Trajectory，NNT）的方法，从历史轨迹数据中搜索与当前公交车已驶过的路段“最相似”的轨迹，在预测当前公交的后续行程时间方面，该方法显示出很好的效果，而且不用考虑各种外部和内部因素。王芳杰等[8]构建了基于LightGBM（Light Gradient Boosting Machine）算法的公交行程时间预测模型，模型的特征选择考虑了车辆行驶数据、天气数据以及道路特征数据，与基于历史平均值和卡尔曼滤波的行程时间预测模型进行对比后的结果表明，该模型的预测效果明显优于其他两个。

针对以上问题，本文基于最近邻（-nearest- neighbor，KNN）算法，探索公交到站时间模式的相似性，在考虑信号灯和实际路况对公交到站时间影响基础上，提出一种新的公交到站预测模型。本文最后将使用天津市808路公交线路1个月的到站时间数据作为数据库，将预测结果与实际到达时间进行比较，以验证模型的准确性。

1 公交车到站时间预测模型

1.1 数据状态划分

城市道路交通运行状态受时段的影响较大，工作日和非工作日的道路交通情况有着明显不同，同一天中高峰期和平峰期的交通流量也有较大变化，从而导致公交车的运行速度出现明显差异，所以预测公交车到站时间，应将工作日和非工作日分别考虑，并按照车辆的运行时间，将公交车的运行时段划分为4种，如表1所示。

表1 公交车运行时段划分

1.2 KNN算法介绍

KNN算法是一种广泛使用的非参数回归方法，它根据参数和数据的相似度，从历史数据中搜索与当前状态最为接近的近邻值用于预测。该算法的基本原理和优缺点在李振龙等[9]的研究中有过详细介绍，Akbari等[10]则给出了其一般性的公式。它假定数据库中的相似数据之间存在相关性，因此，计算的时候只需要利用大量数据，而无需提前定义特定的数学模型和参数。KNN算法充分体现了公交到站时间预测的非参数特征，模型参数包括状态向量、距离度量值、近邻数，以及预测算法。由于到站时间具有较强的空间关联性，故选择与当前站点邻近的个上游站点的到站时间间隔构成状态向量，用于描述样本特征。

1.2.1 距离度量值

距离度量值用来度量训练集和测试集数据之间的相关性。在KNN算法中，采用距离度量值将训练集数据与测试集数据进行匹配，搜索二者之间距离最近的个数据，并将这些数据作为预测数据，输入到预测算法中。由于交通状态随着空间而变化，应根据上游站点和预测站点间的地理位置密切程度来为距离度量值分配不同的权重—— 距离预测站点越远的站点，与预测站点到站时间规律差别越大，从而对距离度量值的贡献也越大，故本文在计算时，加入地理距离值作为权重系数。此外，由于信号灯和弯道对公交车行驶时间影响较大，本文还考虑了信号灯数和弯道数这两项道路特征对距离度量值的影响。已有研究中，似乎未见关于此问题的论述，本文仅将信号灯数和弯道数简单相加，作为该问题的初步探索，认为上游某站点与待预测站点在该值上相差越多，该上游站点对距离度量值的贡献就越大，故加入该差值的绝对值，作为距离度量值中的另一个系数。由于存在地理距离和道路特征两个权重系数，为了消除二者单位和取值范围差异的影响，需要对二者进行归一化处理，本文采用常见的min-max标准化方法进行该操作。以下将描述怎样用个近邻点的数据来预测公交车从第1站到第站的时间间隔，即从历史数据中选择的相似数据的个数。为状态向量的维度，即与待预测站点进行匹配的车站数。目前有多种距离度量方式可用于近邻的搜索，例如切比雪夫距离、马氏距离、欧氏距离等。但用于公交到站时间预测时，通常采用的是欧氏距离作为度量指标，本文在此基础上考虑上述两项权重系数，采用相关系数加权欧氏距离的方法来计算距离度量值：

其中，

（4）

1.2.2 预测算法

预测算法描述了怎样用搜索到的组最近邻数据来预测目标站点的状态向量值。本文采用对个最近邻按距离度量值加权平均的方法，将较大的权值赋给较近的近邻，得到公交车从第1站到第站的到站时间间隔为：

1.3 评价指标

为了验证到站时间预测模型的可靠性，本文采用平均绝对误差率（MAPE）作为预测精度的评价指标。其具体计算公式为

2 数据介绍和处理

2.1 公交车运行数据

本文数据采用天津市808路公交车在2017年10月份所有工作日的运行数据，数据字段格式如表2所示。

对以上数据进行处理分析，当“下一站点编号”（O_NEXTSTATIONNO）发生变化时，说明司机对车辆到站提醒装置进行了操作以提醒乘客到站，故将该字段发生变化后的第一条数据判定为公交车的到站数据，用公交车到达下游站点的时刻减去到达上游站点的时刻即得两站之间的到站时间间隔。

表2 公交车运行数据格式

2.2 道路特征数据

2.2.1 站间距离数据

图1 站点间距离计算方法示意

到和之间的地理距离。假设地球为球体，则其上任意两个位置点1和2之间的球面距离计算公式为：

式中：表示地球半径，取6 370.856 km；表示经度值；表示纬度值。

由该方法可求得天津市808路公交第5~24站各站点与其上一站之间的距离，如图2所示。

2.2.2 信号灯数和弯道数

通过在电子地图上调查和记录，得到该条公交线路上第5~24站各站点与其上一站之间的信号灯数和弯道数，如表3所示。

图2 站间距

表3 与前一站之间的信号灯数和弯道数

3 实例分析

3.1 基础数据

实验选取天津市808路公交线路的地理信息数据，以及2017年10月9~30日共16个工作日早高峰的车辆运行数据作为实例验证的基础数据，其中，以10月9~24日共12个工作日早高峰的车辆运行数据作为训练集，共85组；以10月26日早高峰的数据作为验证集，共2组，用以对模型进行标定；以10月30日早高峰的数据作为测试集，共1组，用以检验模型的预测效果。

3.2 模型参数标定

KNN模型的预测效果依赖于不同近邻数和状态向量的维度的组合方式，通过对训练集和验证集数据进行实验，得到不同（）组合方式下的MAPE值，选取MAPE最小的组合方式对模型进行标定，如图3所示，这里的最大值取15，的最大值取10。

从图3中可以看出，工作日早高峰的（）组合方式中，当=4、=9时，MAPE取得最小值，为13.02%，故以该参数组合标定本文所提出的预测模型。

图3 不同（K，D）组合下的MAPE值

3.3 其他到站时间预测模型

3.3.1 基于历史平均值的预测模型

以公交车在2017年10月9~24日中工作 日早高峰各个公交站的到站时间为历史数据，计算得出公交车到站时间的均值作为预测值； 以10月30日早高峰公交车的到站时间作为测试数据。

3.3.2 无权重KNN模型

该模型的预测算法与本文提出的模型相同，但在计算模型参数中的距离度量值时，不考虑权重，公式为：

式中各自变量的含义与公式（1）中相同。

3.3.3 仅以地理距离作为权重的KNN模型

该模型的预测算法与本文提出的模型相同，但在计算模型参数中的距离度量值时，权重仅考虑匹配站点与待预测站点之间的地理距离，不考虑道信号灯数和弯道数，公式为：

式中各自变量的含义与公式（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%，说明其预测的稳定性最好。

图4 不同预测模型下公交到站时间的MAPE值

图5 不同模型的MAPE平均值和标准差

4 结 论

本文通过考虑公交车运行过程中对预测结果会产生影响的道路特征，提出了一种基于KNN算法的公交到站时间预测模型，并与基于历史平均值的预测模型、无权重KNN模型以及仅以地理距离作为权重的KNN模型的预测结果进行对比，结果显示，本文提出的预测模型在预测难度较大的站点上的MAPE指标明显低于其他模型，且预测的稳定性得到有效提升。

在后续研究中，会采用待预测站点的信号灯数和弯道数较多的公交线路进行进一步实验，同时利用更多不同时段和地点的数据对模型进行比较和验证。此外，也将定量分析地理距离、信号灯数和弯道数在计算模型参数中的距离度量值时的权重，进一步提高模型的预测精度。

[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]. 交通运输系统工程与信息, 2019, 19 (2): 116-121.

[9] 李振龙, 张利国, 钱海峰. 基于非参数回归的短时交通流预测研究综述[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）；中央高校基本科研业务费专项资金（2019B13514）；江苏省博士后科研资助计划项目（1701086B）

霍豪（1994—），男，汉族，湖北黄冈人，河海大学土木与交通学院硕士研究生，主要研究方向：交通运输规划与管理，E-mail：8536744@qq.com

郑长江（1966—），男，汉族，安徽滁州人，博士、教授、博士生导师，主要研究方向：交通运输规划与管理、交通信息与控制和交通安全等，E-mail: zheng@hhu.edu.cn

霍豪，沈金星，郑长江. 基于KNN算法的公交到站时间预测[J]. 交通运输工程与信息学报，2020, 18(4): 76-82, 102

（责任编辑：刘娉婷）