基于动态时间规整的车辆终点及行程时间计算方法

摘要

本发明公开了基于动态时间规整的车辆终点及行程时间计算方法，本发明方法采用半正矢公式计算两点间实际距离，更加符合实际地理空间情景；结合GPS数据呈时间序列的特点，使用适用于时间序列相似性度量的动态时间弯曲算法，有效地缩短了特征量的搜索比对时间，克服了GPS历史值序列与实时参考序列尺度不能完全一致的问题，具有概念简单和算法鲁棒性好的特点；通过特征工程处理使用高性能、适合模型的特征集，同时结合机器学习算法进一步使得预测过程更为准确。本发明作为基于动态时间规整的车辆终点及行程时间计算方法可广泛应用于交通领域。

说明书

技术领域

本发明涉及交通领域，尤其是基于动态时间规整的车辆终点及行程时间计算方法。

背景技术

出租车公司以及近年来兴起了一批打车软件平台，在进行车辆的动态调度时，都需要掌握每个车辆出行终点和抵达时间的信息。如果车辆调度员能够知道出租车完成当前出行的终点和所需的时间，则可以为下一个乘车需求分配距离最近且时间点最契合的车辆，大大降低出租车公司的运营成本，同时提高运营效率。

目前大部分出租车都载有GPS设备，在整个出租车系统的调度和管理过程中，面临的一个重要问题就是，如何能在海量的GPS数据中挖掘出有用信息，供运营者和管理者参考使用。处理海量的GPS数据，遇到的几个技术难点如下：(1)计算能力问题：当前大部分处理设备，并不具备处理数量规模巨大的GPS数据的运行和存储能力，大部分处理器并不擅长存储复杂的数据结构，也不擅长高效地查询数据，或者处理超过内存能力的数据；(2)实时性问题：整个路网中运营的出租车，产生的实时GPS数据，虽然可以通过诸如MySQL、PostgreSQL、SQLite或者Oracle等数据库进行批量处理，但是由于在数据传输及计算过程中的耗时，导致计算结果并不能较为及时地反馈给管理中心进行实时车辆动态调度。由此产生了对于出租车运行终点及其行程时间的预测的实际需求，本作品利用出租车的历史出行轨迹和当前已知的部分行驶轨迹，预测出租车出行终点和行程时间，为出租车管理者动态调度车辆资源提供决策支持。

现有的传统技术方案中对于车辆出行起点-终点的预测方法，主要有：(1)滚动预测模型，通过时间序列的方法对车辆目的地先估计、再预测；(2)转化为动态规划问题，利用诸如最短路径等数学规划的方法，根据已知信息反解车辆目的地相关信息；(3)统计学方法，利用车辆出行起点-终点的历史数据，构造出起讫点矩阵；并使用部分观测值，运用多元正态近似(multivariate normal approximation)等统计学方法进行车辆目的地的估计与预测。

上述技术方案的缺点分别在于：(1)滚动预测模型，在预测时，由于滚动时间窗口的时间间隔选择的差异性，导致对于车辆目的地的估计与预测具有一定的滞后性，无法达到实时应用的目标；(2)转化为动态规划问题，由于车辆时空分布的不确定性及状态空间的维数问题，在递归求解动态规划问题的过程中，经常会占用大量计算资源，使得估计整个路网中车辆的目的地变得非常困难，限制了这类方法的大规模工程应用；(3)统计学方法，该方法是基于贝叶斯框架下的一种预测方法，虽然具有较高的计算效率，但是对于先验分布的选择，需要根据从业者的相关经验进行判断，具有一定的主观性。

术语解释：

Haversine(半正矢)公式：用于计算空间中两点距离，球面模型是对真实地理空间的合理抽象。半正矢公式的本质为球面余弦函数变换，能够消除计算较近两点间距离时误差较大的问题，具有更高的计算精度。

动态时间弯曲算法：动态时间弯曲是一种针对时变数据序列的匹配方法，属于优化的范畴。动态时间弯曲算法通过计算时序数据之间的最短弯曲路径进行序列匹配，能有效缩短特征量的搜索比对时间，克服测试序列与参考序列尺度不能完全一致的问题，具有概念简单和算法鲁棒性好的特点。

特征工程：特征工程指由数据集生成、提取、删除或者组合变化得到特征的过程，是优化机器学习算法性能的技术手段。

支持向量回归：支持向量回归是建立在统计学习理论的VC维理论和结构风险最小原理基础上的，根据有限的样本信息在模型复杂性和准确性之间寻求最佳平衡，将向量映射到一个更高维的空间里，在高维空间中构造线性决策函数来实现线性回归。

发明内容

为了解决上述技术问题，本发明的目的是：提供基于动态时间规整实现符合实际地理空间情况、鲁棒性好的车辆行程时间计算方法。

本发明所采用的技术方案是：基于动态时间规整的车辆终点及行程时间计算方法，包括有以下步骤：

A、利用经纬度数据与地图数据进行匹配计算，得到训练数据集和测试数据集中每一次的出行轨迹数据；

B、采用基于球面模型的半正矢公式，分别计算测试数据集中出行轨迹数据的起点和训练数据集中每一次出行轨迹数据的起点之间的距离，从而得到多个相似出行轨迹数据样本；

C、采用多变量的动态时间弯曲距离算法，计算测试数据集中出行轨迹数据和步骤B中多个相似出行轨迹数据样本之间的动态时间弯曲距离，从而得到多个最近似的出行轨迹数据样本；

D、对步骤C中得到的多个最近似的出行轨迹数据样本进行特征工程处理；

E、根据步骤D所得结果，对测试数据集中出行轨迹数据的终点及行程时间进行计算。

进一步，所述步骤B中距离计算公式为：

其中hav是变量θ的Haversine函数：

d为两点之间的距离，r是球体的半径，是两点的纬度，λ₁,λ₂是两点的经度。

进一步，所述步骤D中的特征工程处理具体为：对特征间的相关性计算和特征对标签的敏感度计算，选取对标签的敏感度大、特征间的相关性小的特征。

进一步，所述步骤E中测试数据集中出行轨迹数据的终点的计算方法为：对多个最近似的出行轨迹数据样本的终点经纬度求几何平均值。

进一步，所述步骤E中测试数据集中出行轨迹数据的行程时间通过支持向量回归模块计算得到。

本发明的有益效果是：本发明方法采用半正矢公式计算两点间实际距离，更加符合实际地理空间情景；结合GPS数据呈时间序列的特点，使用适用于时间序列相似性度量的动态时间弯曲算法，有效地缩短了特征量的搜索比对时间，克服了GPS历史值序列与实时参考序列尺度不能完全一致的问题，具有概念简单和算法鲁棒性好的特点；通过特征工程处理使用高性能、适合模型的特征集，同时结合机器学习算法进一步使得预测过程更为准确。

附图说明

图1为本发明方法的步骤流程图。

具体实施方式

下面结合附图对本发明的具体实施方式作进一步说明：

参照图1，基于动态时间规整的车辆终点及行程时间计算方法，包括有以下步骤：

A、利用经纬度数据与地图数据进行匹配计算，得到训练数据集和测试数据集中每一次的出行轨迹数据；

其中，经纬度数据利用车载GPS设备采集，再将采集所得的数据与地图数据进行匹配，以此提供本发明所需的原始数据。

B、采用基于球面模型的半正矢公式，分别计算测试数据集中出行轨迹数据的起点和训练数据集中每一次出行轨迹数据的起点之间的距离，从而得到多个相似出行轨迹数据样本；

进一步作为优选的实施方式，对于车辆位置参数(即经纬度数据)采用基于球面模型的半正矢(Haversine)公式，所述步骤B中距离计算公式为：

其中hav是变量θ的Haversine函数：

d为两点之间的距离，r是球体的半径，是两点的纬度，λ₁,λ₂是两点的经度。

由于球面模型是对真实地理空间的合理抽象，半正矢公式的本质为球面余弦函数变换，因此能够消除计算较近两点间距离时误差较大的问题，具有更高的计算精度。

作为本发明方法的一个典型实施例，其中步骤B得到多个相似出行轨迹数据样本的具体个数为20000。

C、采用多变量的动态时间弯曲距离算法，计算测试数据集中出行轨迹数据和步骤B中多个相似出行轨迹数据样本之间的动态时间弯曲距离，从而得到多个最近似的出行轨迹数据样本；

作为本发明方法的一个典型实施例，其中步骤C得到多个最相似出行轨迹数据样本的具体个数为10。

测试数据集中出行轨迹数据由一系列经纬度数据构成，呈现时间序列的特点，在度量时间序列的相似性时，采用动态时间弯曲算法。动态时间弯曲是一种针对时变数据序列的匹配方法，通过计算时序数据之间的最短弯曲路径进行序列匹配，能有效缩短特征量的搜索比对时间，克服测试序列与参考序列尺度不能完全一致的问题，结合上述基于球面模型的半正矢公式，具有概念简单和算法鲁棒性好的特点。

D、对步骤C中得到的多个最近似的出行轨迹数据样本进行特征工程处理；

进一步作为优选的实施方式，所述步骤D中的特征工程处理具体为：对特征间的相关性计算和特征对标签的敏感度计算，选取对标签的敏感度大、特征间的相关性小的特征；作为本发明方法的一个典型实施例，其计算得到最终选取的特征如下表1所示：

表1：特征表

E、根据步骤D所得结果，对测试数据集中出行轨迹数据的终点及行程时间进行计算。

进一步作为优选的实施方式，所述步骤E中测试数据集中出行轨迹数据的终点的计算方法为采用统计学的方法：对多个最近似的出行轨迹数据样本的终点经纬度求几何平均值。

进一步作为优选的实施方式，所述步骤E中测试数据集中出行轨迹数据的行程时间通过机器学习计算得到。

由于上述步骤D中进行特征工程处理，使用了高性能、适合模型的特征集，结合支持向量回归算法能实现更准确的预测；此外，步骤E中对行程时间还可采用最近邻算法、决策树模型、随机森林算法等进行计算。

以上是对本发明的较佳实施进行了具体说明，但本发明创造并不限于所述实施例，熟悉本领域的技术人员在不违背本发明精神的前提下还可以作出种种的等同变换或替换，这些等同的变形或替换均包含在本申请权利要求所限定的范围内。