一种基于历史轨迹数据的实时公交到站预测算法

A Real-Time Bus Arrival Time Prediction Algorithm Based on Historical GPS

摘要: 实时公交到站预测是智慧出行服务的重要组成部分，可靠的预测结果能够帮助乘客合理规划出行方案、减少等车时间。针对常见实时公交到站算法存在的所需数据类型多、模型复杂、应用场景单一、算法复杂度高等问题，本文提出了一种基于历史轨迹数据的实时公交到站预测算法，为乘客提供时间、剩余站点数量和剩余距离的预测结果。并开发Android应用，接入深圳市实时公交GPS数据，验证了本文所提出算法的准确性和简单性，可满足大规模应用的需求。

Abstract: Real-time bus arrival time prediction is an important part of smart transit service. Reliable pre-dicting results can help passengers to reduce waiting time and plan trip reasonably. Common al-gorithms have many problems, such as many kinds of data needed, complex models, single application scenarios and high complexity of algorithms, this paper presents a real-time bus arrival time prediction algorithm based on historical GPS, providing passengers with remaining travel time, number of stations and distance. And an Android application accessing real-time GPS data in Shenzhen City is developed to verify the accuracy and simplicity of the proposed algorithm to meet the needs of large-scale application.

1. 研究背景

公共交通是城市经济和民众生活中最重要的基础设施之一，发展城市公共交通不仅是缓解城市交通拥堵的有效措施，也是改善城市人居环境，促进城市可持续发展的必然要求。智能交通系统通过实时交通信息发布使得出行者对即将面对的交通环境有足够了解，并据此做出合理出行规划，所以作为公交信息服务的重要组成部分，公交实时到站的可靠预测显得尤为重要 [1] 。

国外关于公交到站时间的研究可追溯到上世纪70年代，根据公交调度提供的发车信息建立静态预测模型，但是由于当时并没有实时公交数据，所以并不能满足公众的出行服务需求。随着GPS定位技术、通信技术的快速发展，使得实时公交数据采集和传输成为可能，从而可以提供动态的到站预测方法 [2] 。

常用的实时到站预测方法有历史平均法、神经网络模型、卡尔曼滤波模型、支持向量机模型 [3] 、基于概率预测模型等 [2] 。但是这些算法大多存在所需数据种类较多、算法复杂、效率不高、适用场景单一，无法进行大规模结果预测等问题 [4] 。

本文提出一种基于历史数据的实施到站预测算法，实时轨迹确定车辆位置，根据历史轨迹数据预测到站时间和距离，相对于其他算法，简单、高效，能够满足深圳全市运行车辆的实时到站时间预测需求，同时预测结果也相对准确，满足实际应用需要。

2. 算法思路

相同路段的交通运行状况具有周期性特征，历史数据对于公交实时到站的预测具有非常重要的参考价值。本文提出一种基于历史平均法的实时公交到站预测算法，不同于传统历史平均法，而是用站点按次序将线路打断为物理区间，如图1所示。

历史行程时间计算以物理区间为基本单元，按工作日、非工作日区分，以一个小时的时间粒度，求得各时间段内物理区间所需的行程时间分布，作为实时公交到站预测的基础。

算法主要包括历史数据处理与实时预测两部分。

Figure 1. Line interruption

图1. 线路打断

2.1. 历史数据处理

针对大多数方法所建立的预测模型需要多种数据支持，本文方法仅需要准备公交线路、站点数据和历史轨迹数据，对于历史轨迹的处理过程包括以下几步：

1) 数据清洗：对历史轨迹数据中位置异常和重复、无效记录进行清洗，将部分有信息缺失的记录根据其他记录进行补齐；

2) 轨迹匹配：根据轨迹点位置和方向角信息判断车辆运行方向，并匹配至公交线路最邻近点上(图2)；

3) 到站时间插值：搜索站点邻近轨迹点，对历史到站时间进行插值。为了简化估计过程，本文假设相邻轨迹点间车辆匀速运行，从而根据距离插值得到站点的到达时间。如图3所示，A、B为相邻两个轨迹点，记录时间分别为 $t_A$ 和 $t_B$ ，中间经过站点x，则到达x的时间

$t_x=t_A+\left(t_B-t_A\right)\ast d_{Ax}/d_{AB}$

4) 路段行程时间：计算物理区间内行程时间，并根据工作日、非工作日，以1个小时为粒度求得各时间段的平均行程时间 $t_{AB}^i$ ，i为第i个时间段(图4)。

2.2. 实时预测

要进行 实时公交到站时间预测，首先要确定车辆所处的线路位置，非环线的公交大都包含上行和下行两个方向，而公交GPS轨迹信息只包含它所处位置的经纬度、时间、车辆方向角等，并不包含运行方向。此时，需要通过位置和方向角判断车辆运行方向。

如图5所示，线路l有上行和下行两个方向，轨迹点P的方向角为α，与上行方向的夹角更小，并且P点到线路上行方向的最近点P’的距离|PP’| < 30米，则将P点匹配到线路上行方向上的P’点处。此时，可以推出车辆位于物理区间 $\left(i,i+1\right)$ 内，从而可以预测车辆到达后续站点 $i+1,i+2,i+3,\cdots ,i+n$ 的剩余时间：

$t_{P^{\prime },i+1}=t_{i,i+1}\ast d_{P^{\prime },i+1}/d_{i,i+1}$

$T_n=t_{P^{\prime },i+1}+t_{i,i+1}+\cdots +t_{n-1,n}$

3. 算法应用

以本文算法为核心，以深圳市一个月公交历史轨迹数据为基础进行处理分析，得到工作日和非工作日各时间段每个物理区间的行程时间分布作为时间预测基础，开发Android应用服务，接入深圳全市接入实时11,000余辆(非全样)GPS公交数据，为乘客提供全市范围内约1万个公交站点700余条线路的实时公交到站预测服务(图6)。

用户通过应用自动获取的位置信息提供最近站点信息，或者选择输入需要查询的站点信息，即可输出经过对应站点的所有线路车辆实时到站信息，同时可以显示某一条线路上所有车辆的位置信息，前端20秒刷新一次预测结果，保证信息的时效性。

(a) 匹配前 (b) 匹配后

Figure 2. Schematic diagram of trace matching

图2. 轨迹匹配结果示意图

Figure 3. Arrival time interpolation diagram

图3. 到站时间插值示意图

Figure 4. Historical data processing

图4. 历史数据处理过程

Figure 5. Real-time location acquisition

图5. 实时位置获取

Figure 6. User interface

图6. 用户界面

3.1. 数据表设计

实时到站数据表设计如下，包含车辆编号、线路名称、方向名称，每条记录表达当前车辆和公交站点的相对位置和时间预测信息，以12路某辆公交车为例，实时获取其位置位于地王大厦站与市委站之间，后续站点的到站预测如表1所示。

3.2. 算法效率分析

为满足大规模实时公交到站预测，以深圳市一天实时到站预测算法运行时间为例，测试时间包含从数据接收、处理、计算，到预测结果数据入库全过程，分时间段单次更新所需运行时间分布如图7所示。

图7可以看出，高峰期运行车辆较多导致计算成本增加，单次更新所需时间大约为5秒左右，完全满足实际刷新速度的要求，从而证明本文所提算法的简单、高效性。

3.3. 实测验证

为验证算法有效性，笔者特进行了实地验证，以深圳市竹子林①站为例，通过7:00~9:00早高峰时期车辆到站状况与本文预测结果进行对比，实测证明，在实时接入数据缺失的情况下，本文所提方法仍可以实现70%以上的准确预测，从而证明了本文所提算法的有效性。

4. 总结与展望

实时公交到站预测是公交信息服务的重要组成部分，本文提出的实时公交到站算法有效解决了当前常见实时公交到站算法存在的所需数据种类多、模型复杂、计算复杂度高等问题。

但是，面对复杂的交通状况，本文算法仍需要从以下几个方面进行改进：

1) 对于行程时间预测的精细度有待进一步提高，加入车辆停靠时间、信号灯导致的延迟等因素 [5] ；

2) 对于异常突发事件如事故、台风天气导致的车辆延迟情况，需要在算法中加入异常处理模块。

Table 1. Data display example

表1. 数据表示例

Figure 7. Algorithm efficiency analysis

图7. 算法效率分析

致谢

感谢深圳市科技计划项目(项目编号GGFW2016033017241891，项目名称“深圳市交通大数据公共技术服务平台”)和深圳市战略性新兴产业发展专项资金2017年第一批扶持计划(项目名称：深圳市交通碳排放工程实验室，批复文号：深发改(2017)550号)的资助。

基金项目

深圳市科技计划项目(GGFW2016033017241891)，深圳市战略性新兴产业发展专项(深发改(2017)550号)。