高速公路交易的路径拟合方法和装置

摘要

本发明公开了一种高速公路交易的路径拟合方法和装置，该方法包括：将一条高速交易对应的高速交易数据中携带的入口收费站、ETC门架和出口收费站作为途经点按照交易时间依次排序；基于预定的业务规则对各高速交易数据进行校验；按照途经点的排序对高速交易数据中各个途经点进行查询，通过基于预建立的高速路网拓扑有向图模型计算当前查询的途经点与相隔设定步长的、不直接连通的途经点之间是否存在最短路径，来确定当前途经点是否为异常途经点，确定漏收费点和错收费点，基于漏收费点和错收费点确定结果来进行路径拟合；有向图中边的权重为边所指向的ETC门架对应的费用，本发明补全了不完整的收费记录，避免了因为漏收造成的高速企业的收入损失。

权利要求

1.一种高速公路交易的路径拟合方法，其特征在于，该方法包括以下步骤：

对高速交易数据进行数据预处理，所述数据预处理包括：

将一条高速交易对应的高速交易数据中携带的入口收费站、ETC门架和出口收费站作为途经点按照交易时间依次排序；

基于预定的业务规则对各高速交易数据进行校验；

对校验后的高速交易数据进行路径拟合计算，所述进行路径拟合计算的步骤包括：

按照途经点的排序，通过基于预先建立的高速路网拓扑有向图模型计算当前查询的途经点与相隔设定步长的、不直接连通的途经点之间是否存在最短路径，来确定当前途经点是否为异常途经点，确定当前途经点与所述相隔设定步长的、不直接连通的途经点之间是否存在漏收费点和错收费点，并基于漏收费点和错收费点确定结果来进行路径拟合；

其中，所述通过基于预先建立的高速路网拓扑有向图模型计算当前查询的途经点与相隔设定步长的、不直接连通的途经点之间是否存在最短路径，来确定当前途经点是否为异常途经点，并确定当前途经点与所述相隔设定步长的、不直接连通的途经点之间是否存在漏收费点和错收费点，包括：通过基于预先建立的高速路网拓扑有向图模型采用迪杰斯特拉算法计算当前查询的第一途经点与后面的相隔设定步长的、不直接连通的第二途经点之间是否存在最短路径；

如果存在最短路径，确定在第一途经点与第二途经点之间存在漏收费途经点；在所述设定的步长等于1的情况下将第一途经点和第一途经点与第二途经点之间的应有途经点放入拟合点列表，标记出第一途经点为正常点，并将第一途经点与第二途经点之间的应有途经点标记为漏收费途经点；在所述设定的步长大于1的情况下确认还存在错收费途经点，将第一途经点和第一途经点与第二途经点之间的应有途经点放入拟合点列表，并标记出漏收费途经点和错收费途经点以及作为正常点的第一途经点；

其中，所述高速路网拓扑有向图中边的权重为边所指向的ETC门架对应的费用。

2.如权利要求1所述的路径拟合方法，其特征在于,所述数据预处理包括还包括：

对高速路网进行建模，构建基于高速入口收费站点、出口收费站点及ETC门架的所述高速路网拓扑有向图模型，构建所述高速路网拓扑有向图模型的步骤包括：将高速入口收费站点、出口收费站点与ETC门架抽象为若干给定的点；

根据站点与ETC门架间的连通关系，将所有连通的点之间衔接成有向边；

基于点和边构成高速路网拓扑有向图模型。

3.如权利要求1所述的路径拟合方法，其特征在于,所述高速交易数据包括：入口收费站、入口时间、出口收费站、出口时间、总交易金额、ETC门架、每个ETC门架的交易时间及单个ETC门架交易金额，所述基于预定的业务规则对各高速交易数据进行校验的步骤包括：对高速交易数据中的第一部分数据中的至少部分数据进行校验，对第一部分数据进行校验的步骤包括：确定入口收费站、出口收费站是否能够连通，若连通则校验通过；其中，所述第一部分数据包括：入口收费站、入口时间、出口收费站、出口时间及总交易金额；

对高速交易数据中的第二部分数据中的至少部分数据进行校验，对第二部分数据进行校验的步骤包括：根据预定的业务规则对ETC门架交易时间、ETC门架交易金额和ETC门架编号进行正则校验，其中，所述第二部分数据包括：ETC门架信息、ETC门架的交易时间及单个ETC门架交易金额；所述预定的业务规则包括：ETC门架的交易时间不早于所述入口时间；以及ETC门架的交易时间不晚于所述出口时间；

所述第一部分数据和第二部分数据均带有字段passID作为交易标识。

4.如权利要求1所述的路径拟合方法，其特征在于,所述通过基于预先建立的高速路网拓扑有向图模型计算当前查询的途经点与相隔设定步长的、不直接连通的途经点之间是否存在最短路径，来确定当前途经点是否为异常途经点，并确定当前途经点与所述相隔设定步长的、不直接连通的途经点之间是否存在漏收费点和错收费点，还包括：如果不存在最短路径，则在所述第二途经点为终点的情况下，将所述第一途经点放入异常点列表，并按照途经点的排序以1为步长从头查询途经点；在所述第二途经点不是终点的情况下，将所述第一途经点放入异常点列表，并将步长增加1从当前第一途经点重新进行查询。

5.如权利要求1所述的路径拟合方法，其特征在于,所述方法还包括：

确定当前查询的第一途经点是否在异常点列表中，如果在异常点列表中，则从下一途经点开始步长不变，重新进行查询；

如果确定当前查询的第一途经点不在异常点列表中，则进一步确定相隔设定步长的第二途经点是否在异常点列表中，如果第二途经点在异常点列表中，则将步长增加1从当前第一途经点开始进行查询；如果第二途经点不在异常点列表中，则以第一途经点作为当前途经点进行所述进行路径拟合计算的步骤；

所述进行路径拟合计算的步骤还包括：在当前途经点与相隔设定步长的途经点直接连通的情况下，将当前途经点放入拟合途径点列表并标记为正常点。

6.如权利要求4所述的路径拟合方法，其特征在于,所述方法还包括：

对历史拟合路径进行统计和/或路径还原，以基于统计结果获得车辆的个性化规律和ETC门架特征规律，基于路径还原结果获得高速公路上的流量规律。

7.如权利要求1所述的路径拟合方法，其特征在于,所述数据预处理还包括：对高速交易数据进行去重操作，所述去重操作包括：以ETC门架编号及交易时间为联合条件，对同一个passID的高速交易数据携带的多个ETC门架交易信息进行去重。

8.一种高速公路交易的路径拟合装置，该装置包括存储器和处理器，其特征在于，所述存储器中存储有计算机指令，所述处理器用于执行所述存储器中存储的计算机指令，当所述计算机指令被处理器执行时该装置实现如权利要求1至7中任一项所述方法的步骤。

9.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现如权利要求1至7中任一项所述方法的步骤。

说明书

高速公路交易的路径拟合方法和装置

技术领域

[0001] 本发明属于交通技术领域，更具体地涉及高速路径拟合技术领域，尤其涉及一种高速公路交易的路径拟合方法和装置。

背景技术

[0002] 2020年1月1日0时起，全国高速公路联网收费系统完成并网切换，487个高速公路省界收费站全部取消，高速公路由封闭式收费改为开放式断面自由流收费模式。新的收费模式通过在高速收费路段架设带有可进行自动扣费的车载单元的ETC门架来实现；

[0003] 然而，目前的ETC通行交易存在错收、漏收门架等情况，给高速企业造成严重的损失，导致高速计费的收费计算能力差以及计算准确性低，收费效能差，同时，现有技术无法排查异常记录，无法排除交易中存在的干扰数据，难以识别错收门架，导致故障ETC 门架排查困难，对恶意逃费的可疑车辆难以做到排查和预警，而且现有技术难以对高速公路上的流量规律进行分析，导致高速公路的运行效率低，养护作业的精准性和经济效益差。

发明内容

[0004] 有鉴于此，本发明的目的在于提供一种高速公路交易的路径拟合方法和装置，克服现有技术中存在的一个或更多个的缺陷。

[0005] 为实现上述目的，本发明采用了如下技术方案：

[0006] 一种高速公路交易的路径拟合方法，包括以下步骤：

[0007] 对高速交易数据进行数据预处理，所述数据预处理包括：

[0008] 将一条高速交易对应的高速交易数据中携带的入口收费站、ETC门架和出口收费站作为途经点按照交易时间依次排序；

[0009] 基于预定的业务规则对各高速交易数据进行校验；

[0010] 对校验后的高速交易数据进行路径拟合计算，所述进行路径拟合计算的步骤包括：

[0011] 按照途经点的排序，通过基于预先建立的高速路网拓扑有向图模型计算当前查询的途经点与相隔设定步长的、不直接连通的途经点之间是否存在最短路径，来确定当前途经点是否为异常途经点，并确定当前途经点与所述相隔设定步长的、不直接连通的途经点之间是否存在漏收费点和错收费点，并基于漏收费点和错收费点确定结果来进行路径拟合；

[0012] 其中，所述高速路网拓扑有向图中边的权重为边所指向的ETC门架对应的费用。

[0013] 在一些实施例中，所述数据预处理包括还包括：

[0014] 对高速路网进行建模，构建基于高速入口收费站点、出口收费站点及ETC门架的所述高速路网拓扑有向图模型，构建所述高速路网拓扑有向图模型的步骤包括：

[0015] 将高速入口收费站点、出口收费站点与ETC门架抽象为若干给定的点；

[0016] 根据站点与ETC门架间的连通关系，将所有连通的点之间衔接成有向边；

[0017] 基于点和边构成高速路网拓扑有向图模型。

[0018] 在一些实施例中，所述高速交易数据包括：入口收费站、入口时间、出口收费站、出口时间、总交易金额、ETC门架、每个ETC门架的交易时间及单个ETC门架交易金额，所述基于预定的业务规则对各高速交易数据进行校验的步骤包括：

[0019] 对高速交易数据中的第一部分数据中的至少部分数据进行校验，对第一部分数据进行校验的步骤包括：确定入口收费站、出口收费站是否能够连通，若连通则校验通过；其中，所述第一部分数据包括：入口收费站、入口时间、出口收费站、出口时间及总交易金额；

[0020] 对高速交易数据中的第二部分数据中的至少部分数据进行校验，对第二部分数据进行校验的步骤包括：根据预定的业务规则对ETC门架交易时间、ETC门架交易金额和ETC 门架编号进行正则校验，其中，所述第二部分数据包括：ETC门架信息、ETC门架的交易时间及单个ETC门架交易金额；所述预定的业务规则包括：ETC门架的交易时间不早于所述入口时间；以及ETC门架的交易时间不晚于所述出口时间；

[0021] 所述第一部分数据和第二部分数据均带有字段passID作为交易标识。

[0022] 在一些实施例中，所述通过基于预先建立的高速路网拓扑有向图模型计算当前查询的途经点与相隔设定步长的、不直接连通的途经点之间是否存在最短路径，来确定当前途经点是否为异常途经点，并确定当前途经点与所述相隔设定步长的、不直接连通的途经点之间是否存在漏收费点和错收费点，包括：

[0023] 通过基于预先建立的高速路网拓扑有向图模型采用迪杰斯特拉算法计算当前查询的第一途经点与后面的相隔设定步长的、不直接连通的第二途经点之间是否存在最短路径；

[0024] 如果存在最短路径，确定在第一途经点与第二途经点之间存在漏收费途经点，在所述设定的步长等于1的情况下将第一途经点和第一途经点与第二途经点之间的应有途经点放入拟合点列表，标记出第一途经点为正常点，并将第一途经点与第二途经点之间的应有途经点标记为漏收费途经点；

[0025] 如果存在最短路径，确定在第一途经点与第二途经点之间存在漏收费途经点，在所述设定的步长大于于1的情况下确认还存在错收费途经点，将第一途经点和第一途经点与第二途经点之间的应有途经点放入拟合点列表，并标记出漏收费途经点和错收费途经点以及作为正常点的第一途经点。

[0026] 在一些实施例中，所述通过基于预先建立的高速路网拓扑有向图模型计算当前查询的途经点与相隔设定步长的、不直接连通的途经点之间是否存在最短路径，来确定当前途经点是否为异常途经点，并确定当前途经点与所述相隔设定步长的、不直接连通的途经点之间是否存在漏收费点和错收费点，包括：

[0027] 如果不存在最短路径，则在所述第二途经点为终点的情况下，将所述第一途经点放入异常点列表，并按照途经点的排序以1为步长从头查询途经点；在所述第二途经点不是终点的情况下，将所述第一途经点放入异常点列表，并将步长增加1从当前第一途经点重新进行查询。

[0028] 在一些实施例中，所述方法还包括：

[0029] 确定当前查询的第一途经点是否在异常点列表中，如果在异常点列表中，则从下一途经点开始步长不变，重新进行查询；

[0030] 如果确定当前查询的第一途经点不在异常点列表中，则进一步确定相隔设定步长的第二途经点是否在异常点列表中，如果第二途经点在异常点列表中，则将步长增加1从当前第一途经点开始进行查询；如果第二途经点不在异常点列表中，则以第一途经点作为当前途经点进行所述进行路径拟合计算的步骤；

[0031] 所述进行路径拟合计算的步骤还包括：在当前途经点与相隔设定步长的途经点直接连通的情况下，将当前途经点放入拟合途径点列表并标记为正常点。

[0032] 在一些实施例中，所述方法还包括：

[0033] 对历史拟合路径进行统计和/或路径还原，以基于统计结果获得车辆的个性化规律和ETC门架特征规律，基于路径还原结果获得高速公路上的流量规律。

[0034] 在一些实施例中，所述数据预处理还包括：对高速交易数据进行去重操作，所述去重操作包括：以ETC门架编号及交易时间为联合条件，对同一个passID的高速交易数据携带的多个ETC门架交易信息进行去重。

[0035] 根据本发明的另一方面，还提供了一种高速公路交易的路径拟合装置，该装置包括存储器和处理器，所述存储器中存储有计算机指令，所述处理器用于执行所述存储器中存储的计算机指令，当所述计算机指令被处理器执行时该装置实现如前所述方法的步骤。

[0036] 根据本发明的另一方面，还提供了一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现如前所述方法的步骤。

[0037] 综上所述，由于采用了上述技术方案，本发明的有益效果是：

[0038] 1.本发明通过路径拟合，补全了不完整的收费记录，避免了因为漏收造成的高速企业的收入损失，提高高速计费的收费计算能力和计算准确性，提高收费效能；

[0039] 2.本发明通过对历史拟合路径进行统计归档，可进行ETC门架设备故障及可疑车辆的识别与预警，根据记录对应的ETC门架、入出口站点、车辆等信息进行统计分析可获取整体的行为规律、车辆的个性化规律和信用档案、ETC门架特征规律，这样可进一步排查定位ETC门架设备故障，排查可疑车辆，对于故意拔卡，漏算的行为进行定位区分；

[0040] 3.本发明通过对完整通行路径还原，可分析高速公路上的流量规律，为进一步诱导车流、提高运行效率、合理安排养护任务等提供数据支撑，提高高速公路的运行效率和养护作业的精准性和经济效益。

[0041] 本领域技术人员将会理解的是，能够用本发明实现的目的和优点不限于以上具体所述，并且根据以下详细说明将更清楚地理解本发明能够实现的上述和其他目的。

附图说明

[0042] 此处所说明的附图用来提供对本发明的进一步理解，构成本申请的一部分，并不构成对本发明的限定。在附图中：

[0043] 图1为简要的高速公路路网示意图。

[0044] 图2为基于高速公路路网获得的高速公路有向图模型示意图。

[0045] 图3为是本发明一实施例中路径拟合方法的流程示意图。

[0046] 图4为本发明路另一实施例中路径拟合方法的流程示意图。

具体实施方式

[0047] 为使本发明的目的、技术方案和优点更加清楚明白，下面结合实施方式和附图，对本发明做进一步详细说明。在此，本发明的示意性实施方式及其说明用于解释本发明，但并不作为对本发明的限定。

[0048] 在此，还需要说明的是，为了避免因不必要的细节而模糊了本发明，在附图中仅仅示出了与根据本发明的方案密切相关的结构和/或处理步骤，而省略了与本发明关系不大的其他细节。

[0049] 应该强调，术语“包括/包含/具有”在本文使用时指特征、要素、步骤或组件的存在，但并不排除一个或更多个其它特征、要素、步骤或组件的存在或附加。

[0050] 以下结合附图，进一步说明本发明提供的路径拟合方法和装置的具体实施方式。本发明路径拟合方法并不限于以下实施例的描述。

[0051] 实施例：

[0052] 本实施例给出路径拟合方法的具体流程步骤，该路径拟合方法可以由位于高速路交易管理后台的路径拟合系统来实现，但本发明并不限于此，如图3所示，该路径拟合方法包括以下步骤S110和S120：

[0053] 步骤S110，进行数据预处理。

[0054] 在一示例中，该数据预处理的步骤可包括：

[0055] 步骤S112，预先对高速路网进行建模，构建基于高速入口收费站点、出口收费站点及ETC门架的高速路网拓扑的有向图模型。

[0056] 在本发明一实施例中，构建高速路网拓扑的有向图模型的步骤可包括：

[0057] (1)将高速入口收费站点、出口收费站点与ETC门架抽象为若干给定的点；

[0058] (2)根据站点与ETC门架间的连通关系，将所有连通的点之间衔接成有向边；

[0059] (3)基于点和边构成高速路网拓扑的有向图模型。

[0060] 可以用以下方式进行高速公路网拓扑有向图模型的建模：高速公路的收费门架和收费站入口和收费站出口作为有向图中的点，收费门架之间以及收费门架与收费站入口/ 出口之间的直接连接关系作为有向图的边，车辆经过收费门架的费用作为所有以该门架为终点的边的权值，终点为收费站出口的边的权值为0。

[0061] 例如，如图1所示，门架0标记为点0，门架1标记为点1，门架2标记为点2，门架3标记为点3，门架4标记为点4，门架5标记为点5，门架6标记为点6，门架7 标记为点7，收费站0入口标记为点8，收费站0出口标记为点9，收费站1入口标记为点10，收费站1出口标记为点11，收费站2入口标记为点12，收费站2出口标记为点13，收费站3入口标记为点14，收费站3出口标记为点15。下面，将公路路网和公路有向图中的各个点称为节点。

[0062] 对高速路网进行建模后，形成如图2所示的公路有向图模型，在构建的公路有向[0063] 图中：

[0064] 节点0与节点4直接连接，记为边0‑4，值为2；

[0065] 节点1与节点0直接相连，记为边1‑0，值为2；

[0066] 节点1与节点9直接相连，记为1‑9，值为0；

[0067] 节点2与节点1直接相连，记为边2‑1，值为3；

[0068] 节点2与节点11直接相连，记为边2‑11，值为0；

[0069] 节点3与节点2直接相连，记为边3‑2，值为2；

[0070] 节点3与节点13直接相连，记为边3‑13，值为0；

[0071] 节点4与节点5直接相连，记为边4‑5，值为3；

[0072] 节点4与节点9直接相连，记为边4‑9，值为0；

[0073] 节点5和节点6直接相连，记为边5‑6，值为2；

[0074] 节点5和节点11直接相连，记为边5‑11，值为0；

[0075] 节点6与节点2直接相连，记为边6‑2，值为2；

[0076] 节点6与节点7直接相连，记为边6‑7，值为2；

[0077] 节点6与节点13直接相连，记为边6‑13，值为0；

[0078] 节点7与节点15直接相连，记为边7‑15，值为0；

[0079] 节点8与节点0直接相连，记为边8‑0，值为2；

[0080] 节点8与节点5直接相连，记为边8‑5，值为3；

[0081] 节点10与节点1直接相连，记为边10‑1，值为3；

[0082] 节点10与节点6直接相连，记为边10‑6，值为2；

[0083] 节点12与节点2直接相连，记为边12‑2，值为2；

[0084] 节点12与节点7直接相连，记为边12‑7，值为2；

[0085] 节点14与节点3直接相连，记为边12‑3，值为2。

[0086] 该构建好的公路有向图可以存储在路径拟合系统的存储单元中。以上构建的有向图模型仅为示例，发明并不限于此，且以上示例的构建高速公路网拓扑有向图模型的步骤属于现有技术，在此不再赘述。

[0087] 在本发明实施例中，本发明的方法也可以不包括步骤S112，在这种情况下，本发明中所采用的高速公路网拓扑有向图模型为预先建立好的模型。

[0088] 在获取高速路网拓扑的有向图之后，为了保证路径拟合结果的准确性，该数据预处理步骤还可以进一步包括：

[0089] 步骤S113，按照业务规则对获取到的高速原始交易数据进行校验。其中，所述高速原始交易数据可以是从用于管理高速公路交易信息的服务器获得的交易数据，其可包括：入口收费站En、入口时间、出口收费站Ex、出口时间、总交易金额、各交易路径经过的ETC门架、每个ETC门架的交易时间及单个ETC门架交易金额等信息。该用于管理高速公路交易信息的服务器可以从各个门架的路侧单元来获得各段交易数据，并基于各段交易数据来获得完整的高速原始交易数据。

[0090] 在本发明实施例中，对高速原始交易数据进行校验的目的是为了进行数据清理，去掉错误的数据，并将数据格式变为后面的路径拟合算法所需的格式。

[0091] 本发明一实施例中，按照业务规则对高速原始交易数据进行校验的步骤包括步骤 S1131和步骤S1132：

[0092] 在步骤S1131，路径拟合系统对接收到的高速原始交易数据中包含交易的入口收费站En、入口时间、出口收费站Ex、出口时间及总交易金额的第一部分数据进行校验。该第一部分数据相当于一条交易信息的概总数据。

[0093] 在步骤S1132，路径拟合系统对接收到的包含相应交易路径经过的ETC门架、每个 ETC门架的交易时间及单个ETC门架交易金额的第二部分数据，通过算法对第二部分数据进行校验。该第二部分数据相当于一条交易信息的明细数据。

[0094] 所述第一部分数据和第二部分数据中可均带有passID(途经标识)，作为交易标识。该交易标识代表其属于高速交易的途经点交易信息。

[0095] 在对高速原始交易数据进行校验之前，可以先执行以下预处理操作：

[0096] 步骤S111，以passID为检索条件，先将高速原始交易数据中携带的入口收费站En、 ETC门架以及出口收费站Ex按照交易时间依次排序；

[0097] 排序后，可对第一部分数据进行校验，该步骤可包括：

[0098] 将一条高速交易数据携带的其他数据通过预定的业务规范进行检查，确保其能够进行路径验证与拟合。该业务规范包括：入口收费站En和出口收费站Ex能够连通。

[0099] 也即，在步骤S1131中，检查入口收费站En、出口收费站Ex是否能够连通，若连通则校验通过；若不连通则判错，该路径将不被拟合。如果校验不通过，将对相应交易数据进行标记，以指示该数据为有问题的数据，路径将不进行拟合操作。

[0100] 对第二部分数据进行校验的步骤S1132可包括：

[0101] 对每条高速交易携带的第二部分数据(门架交易时间、门架交易金额和门架编号) 进行正则校验，例如根据预定的业务规则进行校验，若符合业务规则则校验通过；若校验不通过则判错，该路径将不被拟合。作为示例，该业务规则包含：

[0102] 所有ETC门架的交易时间不早于入口收费站En携带的入口时间；

[0103] 所有ETC门架的交易时间不晚于出口收费站Ex携带的出口时间。

[0104] 在此，所列举的业务规则仅为示例，但本发明并不限于此。

[0105] 进一步地，本发明实施例的数据预处理步骤还可包括对高速原始交易数据进行去重操作，更具体地，该对高速原始交易数据进行去重操作的步骤可包括：

[0106] 以ETC门架编号及交易时间为联合条件，对同一个passID的高速交易数据携带的n 个ETC门架交易信息进行去重。例如，同一个passID的高速交易数据携带的n个ETC 门架交易信息中，可能包含门架编号或交易时间重合的两条交易信息，此时将删除其中一条交易信息。该步骤同样起到数据清洗的作用，可去掉交易信息中的冗余数据。

[0107] 在获得了高速路网拓扑的有向图并对高速原始交易数据进行数据清洗后，便可以基于高速路网拓扑的有向图对获得的对数据清洗后的交易数据进行拟合计算。

[0108] 步骤S120，对预处理后的交易数据进行路径拟合计算。

[0109] 该进行路径拟合计算的步骤可包括：按照途经点的排序，通过基于预先建立的高速路网拓扑有向图模型计算当前查询的途经点与相隔设定步长的、不直接连通的途经点之间是否存在最短路径，来确定当前途经点是否为异常途经点，确定当前途经点与所述相隔设定步长的、不直接连通的途经点之间是否存在漏收费点和错收费点，并基于漏收费点和错收费点确定结果来进行路径拟合；其中，所述高速路网拓扑有向图中边的权重为边所指向的ETC门架对应的费用。

[0110] 更具体地，路径拟合计算可以以途经点i为游标，特定步长(step)为核心设计，可以逐一标记一条高速交易数据包含的所有N个途经点中正确的途经点、错收的ETC门架，同时可以补全漏收费的途经点(漏收的ETC门架)，并将以上所有信息存入数据库中，一条高速交易包含的所有途经点包括：入口收费站En、在入口收费站和出口收费站之间的所有ETC门架途径点(途经点P1、P2、…、Pn，n＝N‑2)以及出口收费站Ex。

[0111] 如图4所示，该路径拟合步骤包括：

[0112] 步骤S1，输入路径列表(pathList)，该路径列表为基于预处理后的交易数据得到的记录有一条交易的所有途径点的列表，该路径列表中共含有N个途径点。在路径拟合计算开始时，i和step的初始值分别为：i＝0，step＝1。

[0113] 步骤S2，判断第i个点是否是终点(即判断是否i＝N‑1)，如果i不等于N‑1，则继续进入步骤S3。如果i＝N‑1，则确定i是终点，由于终点Ex是默认正确且不可修改的途经点，因此该点i一定是正确的，于是执行步骤S17，将该点加至拟合点列表 (FixList)中，并跳出循环，结束运算。

[0114] 步骤S3，判断step是否大于等于指定值与异常点总数之和，其中，指定值是预先设定的值，例如可以设为5(但本发明并不限于此)，异常点总数为异常点列表中的异常点数，也即异常点列表的长度LenEx。指定值与异常点总数之和可以认为是一个容忍度值，若step大于等于指定值与异常点总数之和，则说明当前i点与后面太多点(超过容忍度值的点数)都不连通，计算结果不可信，于是执行步骤S12，将所有列表清空，从i＝0，step＝1回到步骤S2重新开始计算。若step小于指定值与异常点总数之和，则还可以继续执行以下步骤S4。

[0115] 该步骤中，指定值为5仅为示例，本发明并不限于此。

[0116] 步骤S4，判断第i个点是否在异常点列表(ExcepList)中，若第i个点在异常点列表(ExcepList)中，则跳过该点的运算，游标i加1，步长step仍然置为1，转至步骤S2继续运算判断下一个途经点；若第i个点不在异常点列表(ExcepList)中，说明第i个点是正常途经点，于是进一步执行步骤S5。在本发明实施例中，异常点列表为用于记录异常途经点的表。在路径拟合运算开始时，该异常点列表为空，在本发明的方法执行过程中，在确定途经点为异常途经点时才将其放入异常点列表中。

[0117] 步骤S5，确定第i+step个点是否在异常列表(ExcepList)中，若在异常列表中，则跳过对第i+step个点的运算，游标i不变，步长step加1，转至步骤S2继续运算；

[0118] 在第i个点(可称为第一途经点)和第i+step个点(可称为第二途经点)均尚未经过运算且不在异常列表中的情况下，本发明可进一步执行步骤S6，根据已建立的有向图模型，判断第i个途经点和第i+step个途经点是否可以直接连通，若直接连通，则执行步骤S13，将第i个途经点加至拟合点列表(FixList)中，并将加入到拟合点列表中的点标识为0，代表其是正常途经点，并进一步将游标i加1，步长step值为1，转至步骤S2继续运算。

[0119] 若第i个途经点和第i+step个途经点不直接连通，则本发明执行步骤S7，采用迪杰斯特拉算法计算两者之间的最短路径；若两点间存在最短路径，则说明这两点间存在漏收的ETC门架。迪杰斯特拉算法是目前高速公路的最小费用路径计算经常使用的算法，迪杰斯特拉算法是计算从一个顶点到其余各顶点的最短费用路径算法，解决的是有权图中最短费用路径问题，由于迪杰斯特拉算法计算有向图中两点之间最短距离的方法为现有算法，在此不再赘述。

[0120] 进一步地，判断step是否为1(步骤S8)，若step不大于1(即等于1)，则说明i和i+step这两点间仅存在漏收的ETC门架，则执行步骤S9，将第i个途经点和其与第i+step个点之间的应有途经点放入拟合点列表，并标记出第i个点为正常点，第i 和第i+step个点之间的应有途经点为漏收点；若step大于1，说明这两点间还存在错收的ETC门架；于是本发明在步骤S10将迪杰斯特拉算法计算的最短路径对应的第i个途经点和其与第i+step个途经点之间的所有应有途经点均加至拟合点列表(FixList) 中，其中并标记处漏收点(漏收的ETC门架)和错收点(错收的ETC门架)，其中漏收的ETC门架可被标记为1，代表其为漏收门架；原有路径中错收的ETC门架可被标记为 2，代表其为错收门架；原有路径中的正确途经点被标记为0，代表其为正常途经点，同时，在步骤S11，将所有错收途经点全部加至错收门架列表(ErrList)中，并将游标i 加1，步长step仍然置为1，转至步骤S2继续运算判断下一个途经点；若第i个点途经点和第i+step个途经点之间算不出最短路径，即不存在最短路径，则执行步骤S14，进一步判断第i+step个途经点是否为终点；若其为终点，则执行步骤S15，将第i个途经点放入异常点列表，将除异常点列表之外的其他所有列表清空，并从i＝0，step＝1转至第一步继续计算，以进一步保证路径拟合的准确性；若第i+step个途经点不为终点，则执行步骤S16，将第i+step个途经点加入异常列表ExList中，i不变，step加1，转至步骤S2继续运算。

[0121] 重复执行以上步骤直至第i个点为终点。在确定i点是终点的情况下，系统将该点 i加至拟合点列表(FixList)中，并在step＞1时(步骤S18)，执行步骤S19，将第 i和第i+step个点之间的所有途经点放入拟合点列表和异常点列表中。

[0122] 至此，本发明的路径拟合方法已经计算出拟合点列表(FixList)列表。图4中所示的步骤和步骤的执行顺序仅为示例，但本发明并不限于此，在实际应用中，可以按照实施例中提及的顺序执行步骤，也可以不同于实施例中的顺序，或者若干步骤同时执行。甚至有的步骤可以省略。

[0123] 基于已经计算出拟合点列表(FixList)列表，再根据业务规则，可判断出拟合点列表(FixList)中的错收ETC架的错收原因或漏收ETC架的漏收原因。

[0124] 作为示例，判断FixList中的错收ETC架的错收原因的步骤可包括：

[0125] 检查该ETC门架的前序门架(前一门架)对应的收费单元，若两者相同，则该门架为重复收费；

[0126] 若两者对应的收费单元不同，则根据ETC门架的编码规则，检查两者编码中指定位数的编码是否相同，若不同，则为反向收费；例如，若当前ETC门架和前序ETC门架的门架编码中标识收费方向的字段的编码不相同，则为反向收费。

[0127] 若该ETC门架的前序门架也是错收门架，则往前寻找与之最近的正确的前序ETC门架，再进行上述判断。

[0128] 本发明实施例中，以步长step为核心设计的缘由为：根据业务规则，若第i个途经点与第i+step个途经点仍无法连通，则将第i个途经点放入异常列表中，不再以它为正常途经点继续计算，以节约计算成本。

[0129] 以北京市为例，本发明涉及的北京市高速路网拓扑关系包含高速入口/出口收费站点名称及编码、ETC门架名称及编码、ETC门架收费额度等信息，本发明将入口/出口收费站点与ETC门架抽象为若干给定的点，根据站点与ETC门架间的连通关系，将所有连通的点之间衔接成有向边，最终构成一个有向的高速路网拓扑图；

[0130] 基于已知的高速路网拓扑图和车辆行驶的有序途经点，高速路径拟合问题就可以转化为计算所有生成经过有序途经点的路径集合；本发明将根据最小费用补全策略，针对北京高速路网拓扑图，将ETC门架费用转化为有向图中边的权重，结合原始交易数据中的有序途经点和最短路径原则，在指定起终点的前提下，生成经过指定途经点的高速路径；

[0131] 本实施例的路径拟合方法以passID为检索条件，先将交易信息中携带的入口收费站En、ETC门架、出口收费站Ex按照交易时间依次排序。其中En与Ex是默认正确且不可修改的起止途经点，ETC门架交易是算法需要验证与拟合的对象。

[0132] 排序后，一条高速交易数据携带的其他数据还需要通过以下业务规范检查，确保其能够进行路径验证与拟合：检查入口收费站En、出口收费站Ex是否能够连通，若不连通则判错，该路径将不被拟合。

[0133] 对每条高速交易携带的交易时间、交易金额、门架编号进行正则校验，例如根据预定业务规则进行校验，若符合业务规则则校验通过；若校验不通过则判错，该路径将不被拟合数据；该业务规则可包括：1)所有ETC门架的交易时间不得早于入口收费站En 携带的入口时间；以及2)所有ETC门架的交易时间不得晚于出口收费站Ex携带的出口时间。

[0134] 至此，数据预处理过程结束。

[0135] 预处理后，本发明将采用本算法对原始交易进行验证与拟合补全，用于验证高速交易中是否需要补全缺失的ETC门架、是否存在错收的ETC门架，包括重复收费及反向收费的ETC门架；

[0136] 然后通过以下步骤进行数据拟合计算：

[0137] (1)输入路径列表(pathList)，初始途经点值i＝0，步长step＝1。

[0138] (2)判断step是否大于容忍度值(指定值与异常点总数之和，如5+LenEX)，若大于该值，说明第i个途经点和与它之后连续的(5+LenEX)个途经点均不连通，则本发明认为第i个途经点是一个错收门架，则将所有列表清空，从i＝0，step＝1重新从步骤(1)开始计算。

[0139] (3)判断第i个点是否是终点，如果是终点，则该点一定是正确的，将该点加至拟合点列表(FixList)中，并跳出循环，结束运算；如果不是重点，则继续后面的步骤。

[0140] (4)判断第i个点是否在异常点列表ExcepList中，若存在于异常点列表ExcepList 中，则跳过该点的运算，游标i加1，步长step置为1，转至第(2)步继续运算。

[0141] (5)通过以上判断后，说明第i个点是正常途经点，继续判断第i+step个点是否在异常列表中，若存在，则跳过第i+step个点的运算，游标i不变，步长step加1，转至第(2)步继续运算。

[0142] 通过以上步骤后，说明第i个点和第i+step个点均尚未经过运算且不在异常列表中，本发明进一步根据已有有向高速路网拓扑图判断第i个途经点和第i+step个途经点是否可以直接连通，若直接连通，则将第i个途经点加至FixList中，并标识为0，代表其是正常途经点，游标i加1，步长step值为1，转至第(2)步继续运算；

[0143] 若第i个途经点和第i+step个途经点不直接连通，则本发明采用迪杰斯特拉算法计算两者之间的最短路径；若两点间存在最短路径，则说明这两点间存在漏收的ETC门架；进一步地，判断step是否为1，若step不为1，说明这两点间还存在错收的ETC 门架；本发明先将第i个途经点和其与第i+step个途经点之间的所有点均加至FixList 中，其中漏收的ETC门架被标记为1，代表其为漏收门架；原有路径中错收的ETC门架被标记为2，代表其为错收门架；原有路径中的正确途经点被标记为0，代表其为正常途经点，同时，将所有错收途经点全部加至ErrList错收门架列表中；若第i个点途经点和第i+step个途经点之间算不出最短路径，则将第i个途经点加至FixList中，并标记为0，并判断第i+step个途经点是否为终点；若其为终点，则将第i个途经点放入异常点列表，将所有列表清空，从i＝0，step＝1转至第(2)步继续计算；若其不为终点，则将第i+step个途经点加入异常列表ExList中，i不变，step加1，转至第一步继续运算；

[0144] 重复执行以上步骤直至第i个点为终点；

[0145] 至此，算法已经计算出FixList列表，再根据业务规则，可判断FixList中的错收 ETC架的错收原因；

[0146] 至此，路径拟合计算过程结束。

[0147] 本发明中涉及的所有列表包括：输入的原始交易列表、计算过程中所需的中间列表与计算后的输出列表；其中，中间列表包括异常点列表、错收点列表、拟合点列表。计算后的输出列表例如可以包括：拟合点列表，或者拟合点列表和错收点列表。

[0148] 本发明通过路径拟合，补全了不完整的收费记录，避免了因为漏收造成的高速企业的收入损失，提高高速计费的收费计算能力和计算准确性，提高了收费效能。

[0149] 进一步地，本发明通过对历史拟合路径进行统计归档，可进行ETC门架设备故障及可疑车辆的识别与预警，根据记录对应的ETC门架、入出口站点、车辆等信息进行统计分析可获取整体的行为规律、车辆的个性化规律和信用档案、ETC门架特征规律，这样可进一步排查定位ETC门架设备故障，排查可疑车辆，对于故意拔卡，漏算的行为进行定位区分。

[0150] 本发明通过对完整通行路径还原，可分析高速公路上的流量规律，为进一步诱导车流、提高运行效率、合理安排养护任务等提供数据支撑，提高高速公路的运行效率和养护作业的精准性和经济效益。

[0151] 与上述路径拟合方法相应地，本发明还提供了一种路径拟合装置，该装置包括处理器和存储器，所述存储器中存储有计算机指令，所述处理器用于执行所述存储器中存储的计算机指令，当所述计算机指令被处理器执行时该装置实现如前所述方法的步骤。

[0152] 此外，本发明还提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如前所述方法的步骤。

[0153] 以上内容是结合具体的优选实施方式对本发明所作的进一步详细说明，不能认定本发明的具体实施只局限于这些说明。对于本发明所属技术领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干简单推演或替换，都应当视为属于本发明的保护范围。

[0154] 本领域普通技术人员应该可以明白，结合本文中所公开的实施方式描述的各示例性的组成部分、系统和方法，能够以硬件、软件或者二者的结合来实现。具体究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。当以硬件方式实现时，其可以例如是电子电路、专用集成电路(ASIC)、适当的固件、插件、功能卡等等。当以软件方式实现时，本发明的元素是被用于执行所需任务的程序或者代码段。程序或者代码段可以存储在机器可读介质中，或者通过载波中携带的数据信号在传输介质或者通信链路上传送。“机器可读介质”可以包括能够存储或传输信息的任何介质。机器可读介质的例子包括电子电路、半导体存储器设备、ROM、闪存、可擦除ROM(EROM)、软盘、CD‑ROM、光盘、硬盘、光纤介质、射频(RF) 链路，等等。代码段可以经由诸如因特网、内联网等的计算机网络被下载。

[0155] 还需要说明的是，本发明中提及的示例性实施例，基于一系列的步骤或者装置描述一些方法或系统。但是，本发明不局限于上述步骤的顺序，也就是说，可以按照实施例中提及的顺序执行步骤，也可以不同于实施例中的顺序，或者若干步骤同时执行。

[0156] 本发明中，针对一个实施方式描述和/或例示的特征，可以在一个或更多个其它实施方式中以相同方式或以类似方式使用，和/或与其他实施方式的特征相结合或代替其他实施方式的特征。

[0157] 以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明实施例可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。