基于历史行车轨迹的公交路线推荐方法及系统

摘要

本发明提出了一种基于历史行车轨迹的公交路线推荐方法，其中，该方法包括：获取多组历史行车轨迹数据；采用道格拉斯算法对每组历史行车轨迹数据进行抽稀处理，并将每组历史行车轨迹数据中带站点信息的轨迹点依次补充到对应的抽稀后的历史行车轨迹数据中，以得到处理后的每组行车轨迹数据；获取路网数据，将处理后的每组行车轨迹数据中的每个轨迹点与路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段；对匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段；取校正后的每组行驶轨迹路段中的众数，并将其作为最终的公交行驶轨迹推荐路线进行推荐，从而高效、准确地确定出公交车在路网上的行驶轨迹。

说明书

技术领域

本发明涉及交通技术领域，特别涉及一种基于历史行车轨迹的公交路线推荐方法、一种计算机可读存储介质、一种计算机设备以及一种基于历史行车轨迹的公交路线推荐系统。

背景技术

相关技术中，现有公交GPS轨迹数据匹配到电子地图时，由于未考虑到采集数据的复杂度，所述难以高效、准确地确定出公交车在路网上的行驶轨迹，从而出现轨迹与实际道路偏离的情况，大大降低了用户体验。

发明内容

本发明旨在至少在一定程度上解决上述技术中的技术问题之一。为此，本发明的一个目的在于提出一种基于历史行车轨迹的公交路线推荐方法，通过采用道格拉斯抽稀及站点轨迹点补充，能够保证在不丢失重要GPS轨迹点数据的基础上减少GPS轨迹点的数量，以便后续路段匹配时减少计算量，从而高效、准确地确定出公交车在路网上的行驶轨迹。

本发明的第二个目的在于提出一种计算机可读存储介质。

本发明的第三个目的在于提出一种计算机设备。

为达到上述目的，本发明第一方面实施例提出了一种基于历史行车轨迹的公交路线推荐方法，包括以下步骤：获取多组历史行车轨迹数据；采用道格拉斯算法对每组历史行车轨迹数据进行抽稀处理，并将每组历史行车轨迹数据中带站点信息的轨迹点依次补充到对应的抽稀后的历史行车轨迹数据中，以得到处理后的每组行车轨迹数据；获取路网数据，将所述处理后的每组行车轨迹数据中的每个轨迹点与所述路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段；对所述匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段；取所述校正后的每组行驶轨迹路段中的众数，并将其作为最终的公交行驶轨迹推荐路线进行推荐。

根据本发明实施例的基于历史行车轨迹的公交路线推荐方法，首先获取多组历史行车轨迹数据；然后采用道格拉斯算法对每组历史行车轨迹数据进行抽稀处理，并将每组历史行车轨迹数据中带站点信息的轨迹点依次补充到对应的抽稀后的历史行车轨迹数据中，以得到处理后的每组行车轨迹数据；接着获取路网数据，将处理后的每组行车轨迹数据中的每个轨迹点与路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段；再接着对匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段；最后取校正后的每组行驶轨迹路段中的众数，并将其作为最终的公交行驶轨迹推荐路线进行推荐；由此，通过采用道格拉斯抽稀及站点轨迹点补充，能够保证在不丢失重要GPS轨迹点数据的基础上减少GPS轨迹点的数量，以便后续路段匹配时减少计算量，从而高效、准确地确定出公交车在路网上的行驶轨迹。

另外，根据本发明上述实施例提出的基于历史行车轨迹的公交路线推荐方法还可以具有如下附加的技术特征：

可选地，将所述处理后的每组行车轨迹数据中的每个轨迹点与所述路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段，包括：从处理后的每组行车轨迹数据中的每个轨迹点的起始轨迹点开始与所述路网数据中的每个路段进行匹配，以得到所述起始轨迹点对应的匹配路段；将所述起始轨迹点的下一个轨迹点与所述匹配路段相连通的路段进行依次匹配，如果匹配成功则采用dijkstra最短路径算法寻找路径进行拼接，如果匹配不成功则将所述起始轨迹点的下一个轨迹点与剩余未连通的路段进行依次匹配，并记录匹配成功路段的前后路段ID；以此类推，直至所述处理后的每组行车轨迹数据中的每个轨迹点都匹配完毕。

可选地，如果所述当前待匹配轨迹点的候选匹配路段集合为空集，则以所述当前待匹配轨迹点为中心，将一定半径范围内的所有与所述当前待匹配轨迹点的角度差小于第一阈值的路段作为所述当前待匹配轨迹点的候选匹配路段集合。

可选地，每个轨迹点与所述路网数据中的每个路段进行匹配，包括：计算轨迹点与路段之间的距离值，其中，如果轨迹点的垂足落在路段内则取点到直线的距离作为轨迹点与路段的距离，如果轨迹点的垂足落在路网路段的延长线上，则连接轨迹点与路段两个端点，并取最小值作为轨迹点与路段之间的距离；将所述距离值与预设距离阈值进行比较，如果所述距离值小于所述预设距离阈值，则将路段添加到候选路段中；计算轨迹点与路段之间的夹角，如果夹角大于等于0度且小于等于90度，则认为公交行驶方向与路段的方向一致，将路段添加到候选路段中；根据轨迹点中的速度大小给候选路段赋予权重值，将最小权重值对应的候选路段作为最终的匹配路段。

可选地，对所述匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段，包括：根据记录的匹配成功路段的前后路段ID进行快速排斥及跨立判断检查，如果前后路段之间存在相交，则计算交点位置，并根据交点位置进行校正，以得到校正后的每组行驶轨迹路段。

为达到上述目的，本发明第二方面实施例提出了一种计算机可读存储介质，其上存储有基于历史行车轨迹的公交路线推荐程序，该基于历史行车轨迹的公交路线推荐程序被处理器执行时实现如上述的基于历史行车轨迹的公交路线推荐方法。

根据本发明实施例的计算机可读存储介质，通过存储基于历史行车轨迹的公交路线推荐程序，这样基于历史行车轨迹的公交路线推荐程序被处理器执行时实现如上述的基于历史行车轨迹的公交路线推荐方法，由此，通过采用道格拉斯抽稀及站点轨迹点补充，能够保证在不丢失重要GPS轨迹点数据的基础上减少GPS轨迹点的数量，以便后续路段匹配时减少计算量，从而高效、准确地确定出公交车在路网上的行驶轨迹。

为达到上述目的，本发明第三方面实施例提出了一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时，实现如上述的基于历史行车轨迹的公交路线推荐方法。

根据本发明实施例的计算机设备，通过存储器存储基于历史行车轨迹的公交路线推荐程序，这样基于历史行车轨迹的公交路线推荐程序被处理器执行时实现上述的基于历史行车轨迹的公交路线推荐方法，由此，通过采用道格拉斯抽稀及站点轨迹点补充，能够保证在不丢失重要GPS轨迹点数据的基础上减少GPS轨迹点的数量，以便后续路段匹配时减少计算量，从而高效、准确地确定出公交车在路网上的行驶轨迹。

为达到上述目的，本发明第四方面实施例提出了一种基于历史行车轨迹的公交路线推荐系统，包括：获取模块，用于获取多组历史行车轨迹数据；预处理模块，用于采用道格拉斯算法对每组历史行车轨迹数据进行抽稀处理，并将每组历史行车轨迹数据中带站点信息的轨迹点依次补充到对应的抽稀后的历史行车轨迹数据中，以得到处理后的每组行车轨迹数据；匹配模块，用于获取路网数据，将所述处理后的每组行车轨迹数据中的每个轨迹点与所述路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段；校正模块，用于对所述匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段；推荐模块，用于取所述校正后的每组行驶轨迹路段中的众数，并将其作为最终的公交行驶轨迹推荐路线进行推荐。

根据本发明实施例的基于历史行车轨迹的公交路线推荐系统，通过获取模块，用于获取多组历史行车轨迹数据；预处理模块，用于采用道格拉斯算法对每组历史行车轨迹数据进行抽稀处理，并将每组历史行车轨迹数据中带站点信息的轨迹点依次补充到对应的抽稀后的历史行车轨迹数据中，以得到处理后的每组行车轨迹数据；匹配模块，用于获取路网数据，将处理后的每组行车轨迹数据中的每个轨迹点与路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段；校正模块，用于对匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段；推荐模块，用于取校正后的每组行驶轨迹路段中的众数，并将其作为最终的公交行驶轨迹推荐路线进行推荐；由此，通过采用道格拉斯抽稀及站点轨迹点补充，能够保证在不丢失重要GPS轨迹点数据的基础上减少GPS轨迹点的数量，以便后续路段匹配时减少计算量，从而高效、准确地确定出公交车在路网上的行驶轨迹。

另外，根据本发明上述实施例提出的基于历史行车轨迹的公交路线推荐系统还可以具有如下附加的技术特征：

可选地，所述匹配模块还用于，从处理后的每组行车轨迹数据中的每个轨迹点的起始轨迹点开始与所述路网数据中的每个路段进行匹配，以得到所述起始轨迹点对应的匹配路段；将所述起始轨迹点的下一个轨迹点与所述匹配路段相连通的路段进行依次匹配，如果匹配成功则采用dijkstra最短路径算法寻找路径进行拼接，如果匹配不成功则将所述起始轨迹点的下一个轨迹点与剩余未连通的路段进行依次匹配，并记录匹配成功路段的前后路段ID；以此类推，直至所述处理后的每组行车轨迹数据中的每个轨迹点都匹配完毕。

可选地，所述匹配模块还用于，计算轨迹点与路段之间的距离值，其中，如果轨迹点的垂足落在路段内则取点到直线的距离作为轨迹点与路段的距离，如果轨迹点的垂足落在路网路段的延长线上，则连接轨迹点与路段两个端点，并取最小值作为轨迹点与路段之间的距离；将所述距离值与预设距离阈值进行比较，如果所述距离值小于所述预设距离阈值，则将路段添加到候选路段中；计算轨迹点与路段之间的夹角，如果夹角大于等于0度且小于等于90度，则认为公交行驶方向与路段的方向一致，将路段添加到候选路段中；根据轨迹点中的速度大小给候选路段赋予权重值，将最小权重值对应的候选路段作为最终的匹配路段。

可选地，所述校正模块还用于，根据记录的匹配成功路段的前后路段ID进行快速排斥及跨立判断检查，如果前后路段之间存在相交，则计算交点位置，并根据交点位置进行校正，以得到校正后的每组行驶轨迹路段。

附图说明

图1为根据本发明实施例的基于历史行车轨迹的公交路线推荐方法的流程示意图；

图2为根据本发明一个实施例的基于历史行车轨迹的公交路线推荐方法的流程示意图；

图3为根据本发明一个实施例的基于历史行车轨迹的公交路线推荐方法的路径校正示例图；

图4为根据本发明一个实施例的基于历史行车轨迹的公交路线推荐系统的方框示意图。

具体实施方式

下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不能理解为对本发明的限制。

相关技术中，基于历史数据的公交车行驶路线推荐中涉及到的核心为GPS轨迹点数据与路网之间的匹配方法；目前针对GPS轨迹数据地图匹配算法的研究大致可分为以下几类：1、几何分析法主要是通过GPS数据点与道路之间的距离、角度等为依据，将轨迹点匹配到最合适的路段，但是基于几何信息的匹配算法忽略了GPS轨迹数据点之间的联系、道路的拓扑信息，容易导致匹配准确率下降，且出现匹配错误时，难以及时修正；2、拓扑算法主要是利用GPS数据点之间的拓扑关系进行路段匹配，即使用弗雷歇距离计算一段轨迹和一条道路的距离，如果距离小于设定的阈值，则进行匹配，但是基于拓扑信息的匹配算法容易受到采集噪声及数据稀疏性的影响，难以保证高稳定性下对轨迹点进行准确匹配；3、概率算法则是为了解决轨迹噪声点和低采样率问题，且该算法对GPS噪声点做了明确的规定，并通过道路网考虑多种可能路径以找到最佳的路径，但是基于概率信息的匹配方法涉及较多的公式推导，实现难度较大，且计算开销较高。

为此，本发明实施例提出的基于历史行车轨迹的公交路线推荐方法，在GPS轨迹点数据预处理阶段，采用道格拉斯抽稀及站点轨迹点补充能够保证在不丢失重要GPS轨迹点数据的基础上减少GPS轨迹点的数量，以便后续路段匹配时减少计算量；在路段匹配阶段，采用基于距离、速度及角度为参考因素及广度优先搜索确定出公交车在路网上的行驶轨迹，能够将GPS轨迹点数据与路段进行快速匹配；行驶轨迹校正阶段采用了快速排斥及跨立判断能够解决前后路段之间首尾不连接的情况；最后采用众数的方式高效、准确的确定出公交车推荐行驶路线。

为了更好的理解上述技术方案，下面将参照附图更详细地描述本发明的示例性实施例。虽然附图中显示了本发明的示例性实施例，然而应当理解，可以以各种形式实现本发明而不应被这里阐述的实施例所限制。相反，提供这些实施例是为了能够更透彻地理解本发明，并且能够将本发明的范围完整的传达给本领域的技术人员。

为了更好的理解上述技术方案，下面将结合说明书附图以及具体的实施方式对上述技术方案进行详细的说明。

图1为根据本发明实施例的基于历史行车轨迹的公交路线推荐方法的流程示意图。如图1所示，本发明实施例的基于历史行车轨迹的公交路线推荐方法包括以下步骤：

步骤101，获取多组历史行车轨迹数据。

作为一个实施例，采集某一线路20辆车一周的GPS轨迹数据作为多组历史行车轨迹数据，其中每组GPS轨迹数据包括时间、经纬度坐标、公交车行驶方向和速度以及固定站点位置信息，根据经纬度值能够确定出一个轨迹点，按时间先后顺序将轨迹点进行排序便形成一条完整的行车轨迹。

步骤102，采用道格拉斯算法对每组历史行车轨迹数据进行抽稀处理，并将每组历史行车轨迹数据中带站点信息的轨迹点依次补充到对应的抽稀后的历史行车轨迹数据中，以得到处理后的每组行车轨迹数据。

需要说明的是，由于历史行车轨迹数据采集采用的是高频率的采集方式，因此获取到的数据量较大，轨迹相对完整，故需要通过道格拉斯数据抽稀算法及补充关键GPS轨迹点对数据进行预处理，以保证在不丢失重要信息的基础上减少GPS轨迹点数据。

作为一个具体实施例，如图2所示，采用道格拉斯算法对原始GPS轨迹点数据进行抽稀，其具体步骤如下：

a、在起始轨迹点与终止轨迹点之间连接一条直线，该直线为原始路径的弦；

b、计算原始轨迹点上离弦距离最大的点记为C，距离大小记为D；

c、比较D与预先设定的阈值的大小关系，若D小于阈值，则弦可作为曲线的近似；若D大于阈值，则以C点位置为中点将路段分隔开，并对两路段进行a-c处理；

d、当所有路段都处理完毕后，依次将起终点及各个分割点连接起来，作为原始路径的近似。

原始GPS轨迹数据抽稀完毕后，将带站点信息的轨迹点依次补充到抽稀结果中，固定站点信息为重要信息，避免在抽稀过程中出现将其过滤掉的情况。

步骤103，获取路网数据，将处理后的每组行车轨迹数据中的每个轨迹点与路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段。

需要说明的是，路网数据包括多个路段，每个路段包括路段唯一id、路段起点的经度、路段起点的纬度、路段终点的经度、路段终点的纬度、路段的航向角和与该路段相连通的前后路段的唯一id。

作为一个实施例，将处理后的每组行车轨迹数据中的每个轨迹点与路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段，包括：

从处理后的每组行车轨迹数据中的每个轨迹点的起始轨迹点开始与路网数据中的每个路段进行匹配，以得到起始轨迹点对应的匹配路段；将起始轨迹点的下一个轨迹点与匹配路段相连通的路段进行依次匹配，如果匹配成功则采用dijkstra最短路径算法寻找路径进行拼接，如果匹配不成功则将起始轨迹点的下一个轨迹点与剩余未连通的路段进行依次匹配，并记录匹配成功路段的前后路段ID；以此类推，直至处理后的每组行车轨迹数据中的每个轨迹点都匹配完毕。

作为一个实施例，在单点GPS轨迹数据与路段之间的匹配中，包括：

计算轨迹点与路段之间的距离值，其中，如果轨迹点的垂足落在路段内则取点到直线的距离作为轨迹点与路段的距离，如果轨迹点的垂足落在路网路段的延长线上，则连接轨迹点与路段两个端点，并取最小值作为轨迹点与路段之间的距离；将距离值与预设距离阈值进行比较，如果距离值小于预设距离阈值，则将路段添加到候选路段中；计算轨迹点与路段之间的夹角，如果夹角大于等于0度且小于等于90度，则认为公交行驶方向与路段的方向一致，将路段添加到候选路段中；根据轨迹点中的速度大小给候选路段赋予权重值，将最小权重值对应的候选路段作为最终的匹配路段。

也就是说，首先基于距离的候选路段确定：计算GPS轨迹点数据与路网路段之间的距离大小记为D，若D小于预先设定的阈值大小则将该路网路段添加到候选路段中，本发明中将阈值设定为100m；接着基于夹角的候选路段确定：计算GPS轨迹点数据与路网路段之间的夹角大小记为ψ，若0<＝ψ<＝90度，则认为公交车行驶方向与路网路段的方向一致，该路网路段可作为候选路段，反之则排除；最后基于权重大小的匹配路段选择：根据GPS轨迹数据点中的速度大小给候选路网路段赋予权重值，最后根据每个候选匹配路段所计算出的权值大小取最小值的方式确定出最终的匹配路段。

其中，GPS轨迹点数据与路网路段之间的夹角计算方式如下表所示：

其中，根据轨迹点中的速度大小给候选路段赋予权重值，将最小权重值对应的候选路段作为最终的匹配路段，具体计算方式如下：

W

W＝(distance/0.00046*39.3)*W

其中，distance为路段的长度；angle为公交车的行驶方向与道路方向的夹角；α为角度的经验修正系数取值为1.5；T为速度阈值取值为3.6；A

也就是说，基于广度优先搜索的方式确定公交车在路网上的行驶轨迹，按轨迹点的时间先后顺序分别与路段进行匹配，首先从行车轨迹起始点开始出发，令起始点GPS数据与全部路网进行匹配；之后从已匹配的路段出发，按与已匹配路段相连通的路网优先匹配方法依次匹配剩余轨迹点；若匹配成功，则采用Dijkstra最短路径算法寻找路径进行拼接，若不成功则将轨迹点与剩余未连通的路网路段进行匹配，并记录下前后路段的ID；直至所有轨迹点都匹配完毕。

步骤104，对匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段。

作为一个实施例，对匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段，包括：

根据记录的匹配成功路段的前后路段ID进行快速排斥及跨立判断检查，如果前后路段之间存在相交，则计算交点位置，并根据交点位置进行校正，以得到校正后的每组行驶轨迹路段；其中，路径校正示例图如图3所示。

也就是说，基于快速排斥及跨立判断的轨迹校正，根据步骤103中所记录下的前后路段ID进行快速排斥及跨立判断检查，若前后两路网路段之间存在相交，则计算交点位置，校正最终行驶轨迹。

需要说明的是，基于距离、速度及方向的轨迹点匹配方法及基于快速排斥及跨立判断的轨迹校正能够快速、准确地将GPS轨迹点数据与路网进行匹配。

步骤105，取校正后的每组行驶轨迹路段中的众数，并将其作为最终的公交行驶轨迹推荐路线进行推荐。

综上所述，根据本发明实施例的基于历史行车轨迹的公交路线推荐方法，首先获取多组历史行车轨迹数据；然后采用道格拉斯算法对每组历史行车轨迹数据进行抽稀处理，并将每组历史行车轨迹数据中带站点信息的轨迹点依次补充到对应的抽稀后的历史行车轨迹数据中，以得到处理后的每组行车轨迹数据；接着获取路网数据，将处理后的每组行车轨迹数据中的每个轨迹点与路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段；再接着对匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段；最后取校正后的每组行驶轨迹路段中的众数，并将其作为最终的公交行驶轨迹推荐路线进行推荐；由此，通过采用道格拉斯抽稀及站点轨迹点补充，能够保证在不丢失重要GPS轨迹点数据的基础上减少GPS轨迹点的数量，以便后续路段匹配时减少计算量，从而高效、准确地确定出公交车在路网上的行驶轨迹。

另外，本发明实施例还提出了一种计算机可读存储介质，其上存储有基于历史行车轨迹的公交路线推荐程序，该基于历史行车轨迹的公交路线推荐程序被处理器执行时实现如上述的基于历史行车轨迹的公交路线推荐方法。

根据本发明实施例的计算机可读存储介质，通过存储基于历史行车轨迹的公交路线推荐程序，这样基于历史行车轨迹的公交路线推荐程序被处理器执行时实现如上述的基于历史行车轨迹的公交路线推荐方法，由此，通过采用道格拉斯抽稀及站点轨迹点补充，能够保证在不丢失重要GPS轨迹点数据的基础上减少GPS轨迹点的数量，以便后续路段匹配时减少计算量，从而高效、准确地确定出公交车在路网上的行驶轨迹。

另外，本发明实施例还提出了一种计算机设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时，实现如上述的基于历史行车轨迹的公交路线推荐方法。

根据本发明实施例的计算机设备，通过存储器存储基于历史行车轨迹的公交路线推荐程序，这样基于历史行车轨迹的公交路线推荐程序被处理器执行时实现上述的基于历史行车轨迹的公交路线推荐方法，由此，通过采用道格拉斯抽稀及站点轨迹点补充，能够保证在不丢失重要GPS轨迹点数据的基础上减少GPS轨迹点的数量，以便后续路段匹配时减少计算量，从而高效、准确地确定出公交车在路网上的行驶轨迹。

图4为根据本发明一个实施例的基于历史行车轨迹的公交路线推荐系统的方框示意图，该基于历史行车轨迹的公交路线推荐系统包括：获取模块10、预处理模块20、匹配模块30、校正模块40和推荐模块50。

其中，获取模块10，用于获取多组历史行车轨迹数据；预处理模块20，用于采用道格拉斯算法对每组历史行车轨迹数据进行抽稀处理，并将每组历史行车轨迹数据中带站点信息的轨迹点依次补充到对应的抽稀后的历史行车轨迹数据中，以得到处理后的每组行车轨迹数据；匹配模块30，用于获取路网数据，将处理后的每组行车轨迹数据中的每个轨迹点与路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段；校正模块40，用于对匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段；推荐模块50，用于取校正后的每组行驶轨迹路段中的众数，并将其作为最终的公交行驶轨迹推荐路线进行推荐。

作为一个实施例，匹配模块30还用于，从处理后的每组行车轨迹数据中的每个轨迹点的起始轨迹点开始与路网数据中的每个路段进行匹配，以得到起始轨迹点对应的匹配路段；将起始轨迹点的下一个轨迹点与匹配路段相连通的路段进行依次匹配，如果匹配成功则采用dijkstra最短路径算法寻找路径进行拼接，如果匹配不成功则将起始轨迹点的下一个轨迹点与剩余未连通的路段进行依次匹配，并记录匹配成功路段的前后路段ID；以此类推，直至处理后的每组行车轨迹数据中的每个轨迹点都匹配完毕。

作为一个实施例，匹配模块30还用于，计算轨迹点与路段之间的距离值，其中，如果轨迹点的垂足落在路段内则取点到直线的距离作为轨迹点与路段的距离，如果轨迹点的垂足落在路网路段的延长线上，则连接轨迹点与路段两个端点，并取最小值作为轨迹点与路段之间的距离；将距离值与预设距离阈值进行比较，如果距离值小于预设距离阈值，则将路段添加到候选路段中；计算轨迹点与路段之间的夹角，如果夹角大于等于0度且小于等于90度，则认为公交行驶方向与路段的方向一致，将路段添加到候选路段中；根据轨迹点中的速度大小给候选路段赋予权重值，将最小权重值对应的候选路段作为最终的匹配路段。

作为一个实施例，校正模块40还用于，根据记录的匹配成功路段的前后路段ID进行快速排斥及跨立判断检查，如果前后路段之间存在相交，则计算交点位置，并根据交点位置进行校正，以得到校正后的每组行驶轨迹路段。

需要说明的是，前述对于基于历史行车轨迹的公交路线推荐方法的实施例的解释说明同样适用于本实施例的基于历史行车轨迹的公交路线推荐系统，此处不再赘述。

根据本发明实施例的基于历史行车轨迹的公交路线推荐系统，通过获取模块，用于获取多组历史行车轨迹数据；预处理模块，用于采用道格拉斯算法对每组历史行车轨迹数据进行抽稀处理，并将每组历史行车轨迹数据中带站点信息的轨迹点依次补充到对应的抽稀后的历史行车轨迹数据中，以得到处理后的每组行车轨迹数据；匹配模块，用于获取路网数据，将处理后的每组行车轨迹数据中的每个轨迹点与路网数据中的每个路段进行匹配，以得到匹配后的每组行驶轨迹路段；校正模块，用于对匹配后的每组行驶轨迹路段进行轨迹校正，以得到校正后的每组行驶轨迹路段；推荐模块，用于取校正后的每组行驶轨迹路段中的众数，并将其作为最终的公交行驶轨迹推荐路线进行推荐；由此，通过采用道格拉斯抽稀及站点轨迹点补充，能够保证在不丢失重要GPS轨迹点数据的基础上减少GPS轨迹点的数量，以便后续路段匹配时减少计算量，从而高效、准确地确定出公交车在路网上的行驶轨迹。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

应当注意的是，在权利要求中，不应将位于括号之间的任何参考符号构造成对权利要求的限制。单词“包含”不排除存在未列在权利要求中的部件或步骤。位于部件之前的单词“一”或“一个”不排除存在多个这样的部件。本发明可以借助于包括有若干不同部件的硬件以及借助于适当编程的计算机来实现。在列举了若干装置的单元权利要求中，这些装置中的若干个可以是通过同一个硬件项来具体体现。单词第一、第二、以及第三等的使用不表示任何顺序。可将这些单词解释为名称。

尽管已描述了本发明的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本发明范围的所有变更和修改。

显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

在本发明的描述中，需要理解的是，术语“第一”、“第二”仅用于描述目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量。由此，限定有“第一”、“第二”的特征可以明示或者隐含地包括一个或者更多个该特征。在本发明的描述中，“多个”的含义是两个或两个以上，除非另有明确具体的限定。

在本发明中，除非另有明确的规定和限定，术语“安装”、“相连”、“连接”、“固定”等术语应做广义理解，例如，可以是固定连接，也可以是可拆卸连接，或成一体；可以是机械连接，也可以是电连接；可以是直接相连，也可以通过中间媒介间接相连，可以是两个元件内部的连通或两个元件的相互作用关系。对于本领域的普通技术人员而言，可以根据具体情况理解上述术语在本发明中的具体含义。

在本发明中，除非另有明确的规定和限定，第一特征在第二特征“上”或“下”可以是第一和第二特征直接接触，或第一和第二特征通过中间媒介间接接触。而且，第一特征在第二特征“之上”、“上方”和“上面”可是第一特征在第二特征正上方或斜上方，或仅仅表示第一特征水平高度高于第二特征。第一特征在第二特征“之下”、“下方”和“下面”可以是第一特征在第二特征正下方或斜下方，或仅仅表示第一特征水平高度小于第二特征。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不应理解为必须针对的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任一个或多个实施例或示例中以合适的方式结合。此外，在不相互矛盾的情况下，本领域的技术人员可以将本说明书中描述的不同实施例或示例以及不同实施例或示例的特征进行结合和组合。

尽管上面已经示出和描述了本发明的实施例，可以理解的是，上述实施例是示例性的，不能理解为对本发明的限制，本领域的普通技术人员在本发明的范围内可以对上述实施例进行变化、修改、替换和变型。