基于图论的高速公路联网收费车道建模计算费额的方法

摘要

本发明一种基于图论的高速公路联网收费车道建模计算费额的方法，涉及图论技术领域。包括由联网收费结算中心(1)，路公司收费中心(2)，收费站(3)及车道(4)组成的高速公路联网收费系统构架；包括由车道(41)、收费站(31)、路公司收费中心(21)、联网收费结算中心(11)构成的联网收费系统数据传输构架；还包括车道基于图论建模计算费额工作流程：A.基础信息的加载；B.车道基于图论建模；C.车道利用模型计算费额等。比较传统方法，该方法大大减少了费额表的数据量，提高了费额数据下载、核对的效率和准确性，且能满足路公司的各种优惠需求，解决了联网收费系统中费额表下载数据量大，下载时间长的难题，具有推广意义。

说明书

技术领域

本发明涉及图论技术领域，具体指一种基于图论的高速公路联网收费车道建模计算费额的方法。

背景技术

随着高速公路路网的扩大，尤其是环线高速公路的形成，二义性路径问题越来越突出。传统的费额表在结算中心预先算好，从结算中心下发到各个车道，车道通过查表法获得任意两个站点之间的费额。该方法带来以下问题：(1)客车费额是由入口、出口、所经过的标识站组合、车型来确定的，随着路网规模的扩大，二义性路径的增加，若要实现精确计费、精确清分，则标识站的数量将增加。随着标识站数量的增加，标识站的组合数目将呈指数形式增加，从而导致费额表也是呈指数形式增加，很难实现精确计费、精确清分。(2)为满足路公司实行分时优惠、区间优惠要求，必须对全路网费额数据重新计算和启用。这种方法随着路网规模扩大，大数据量的费额计算与下发、核对需要一段时间，无法满足路公司和高发司提出的费额实时变化的需求。因此，现有技术在“最小费额收费，最短路径清分”的规则下，“路网费额表”的生成、校对、下发变得极其困难。

发明内容

本发明的目的在于克服现有技术存在的缺失和不足，而提出一种基于图论的高速公路联网收费车道建模计算费额的方法。

基于图论的高速公路联网收费车道建模计算费额的方法包括：

一、高速公路联网收费系统构架构建

高速公路联网收费系统构架包括：联网收费结算中心，路公司收费中心，收费站，车道等几级构架系统构架(如附图1所示)。

二、联网收费系统数据传输构架联结

高速公路联网收费系统数据传输按层次主要分为车道、收费站、路公司收费中心、联网收费结算中心四层。高速公路联网收费系统软件的数据传输构架(如附图2所示)，其中还包括：

(一)车道：

车道从收费站下载基础信息，包括路段内费额、里程表，立交桥信息表，优惠路段表，优惠卡表等。

车道原始收费记录数据分为两路上传，一路上传收费站、路公司收费中心，一路上传联网收费结算中心。

(二)收费站：

收费站从联网收费结算中心获取基础信息并向路公司收费中心上传特殊处理流水、图像信息、缴款信息、统计数据以及其他需要的数据。

(三)路公司收费中心：

路公司收费中心从联网收费结算中心获取基础信息并向联网收费结算中心上传路段汇总统计信息；

(四)联网收费结算中心：

联网收费结算中心分别向路公司收费中心和收费站下发基础信息。

三、车道基于图论建模计算费额工作流程：

A：基础信息的加载：

车道信息传输软件将计算费额所需的基础信息(路段内费额、里程表，立交桥表，优惠路段表，优惠卡表等)，从结算中心下载到车道数据库，车道软件将数据库中的基础信息读入到内存中；

B：车道基于图论建模：

B1：将各条高速公路的各个收费站作为图的顶点V，连接两个收费站的路径作为边E，连接两个路段之间的边作为立交桥，将具有环路的部分作为有环部分(实线部分，内环外移后，收费的只有两个环)，将不构成环路的部分作为射线部分(虚线部分)，构造出高速公路建模图G＝(V，E)，如附图4所示。

B2：车道软件加载基础信息后，将整个路网信息按照上述模型，使用邻接表的表示方法存入内存，形成路网模型。

C：车道利用模型计算费额：

任意两个收费站之间的通行费计算原则：客车费额按照“最小费额”原则计算，货车费额按照“最短路径”原则计算。

C1：客车费额计算规则：

(1)对于射线部分无二义性路径的两个站点之间的费额计算采用精确路径计算。

(2)对于有环部分存在有二义性路径的两个站点之间的费额计算，将最小费额作为通行费额。

(3)对于有环部分，通过各种标识路径法，对于能精确标识的路径部分采用精确路径计费；对于不能精确标识的路径部分采用最小费额计费。

(4)对于区间优惠路段，或优惠卡优惠路段，按照优惠率计算优惠后的最小费额。

(5)路段内的两个站点之间的费额采用路段内审批费额。

(6)跨路段两个站点之间的费额按照立交桥规则计算：两个路段的路段内审批费额加这两个路段的立交桥审批费额；

立交桥计费规则(如附图5所示)：

图中A-E为路段1，E-D为路段2，E为两个路段的交汇点，A，B为路段1的两个收费站，C，D为路段2的两个收费站，B，C段为立交桥。则A-D的费额：F(AD)＝F(AB)+F(BC)+F(CD)。其中F(AB)为路段1中A，B两个收费站的审批费额，F(CD)为路段2中C，D两个收费站的审批费额，F(BC)为两个路段立交桥审批费额。

C2：货车费额计算规则：

(1)对于射线部分无二义性路径的两个站点之间的费额计算采用精确路径计算。

(2)对于有环部分存在有二义性的路径中能精确标识的路径部分，采用精确路径计费；对于不能精确标识的路径部分采用最短路径计费。

(3)对于最短路径上有区间优惠路段，优惠卡优惠路段，则按照优惠率计算优惠后的收费金额。

(4)货车按照计重公式计算最短路径上的通行费额。

C3：两个站点之间客车货车费额计算方法：

(1)首先计算出这两个站点之间的所有路径。

(2)客车，对每条路径计算该路径的费额，取最小费额。

(3)货车，取最短路径，按照计重公式计算通行费额。

C4：利用回溯法计算两个站点之间的所有路径：

利用回溯法可以计算两个站点之间的所有路径。

回溯法简介如下：

回溯法也称为试探法，该方法首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解，不满足问题规模要求，但满足所有其他要求时，继续扩大当前候选解的规模，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。在回溯法中，放弃当前候选解，寻找下一个候选解的过程称为回溯。

利用回朔算法搜索两个站点之间的所有路径，可以分成如下5种情况：

(1)射线上道射线下道，如附图4中的C-D，该路径唯一。

(2)射线上道环线下道，如附图4中的C-B，C到V3的路径唯一，只要搜索V3到B的所有路径。

(3)射线上道经过环线从射线下道，如附图4中的C-F，C-V3，F-V1路径唯一，只要搜索V3-V1的路径。

(4)环线上道射线下道，如附图4中的A-F，F-V1的路径唯一，只要搜索A-V1的路径。

(5)环线上道环线下道，如附图4中的A-B，搜素A-B的路径。

由上述方法可见，由于射线部分路径唯一，搜素两个站点之间的路径归结为搜索这两个站点在有环部分的路径。这样可以减少回朔的搜索条数，对回朔进行剪枝，从而加快路径搜索效率。

求得两个站点之间的所有路径，对包含标识站的路径进行标记，从而解决了获得两个站点之间经过指定标识站的路径问题。

C5：两个站点之间的货车费额计算：

用回溯法求得两个站点之间的所有路径后，取其中里程最小的路径，就是最短路径，按照货车计重公式可以求得这两个站点之间最短路径上的货车费额。

C6：两个站点之间客车费额计算：

用回溯法求得两个站点之间的所有路径后，对每一条路径，按照客车立交桥费额规则计算该路径的客车费额，取其中最小的费额作为这两个站点之间的客车费额。

C7：两个站点之间的优惠费额计算：

C7.1：客车优惠费额计算：

用回溯法求得两个站点之间的所有路径后，对每一条路径，若路径中包含优惠区间，则将路段内收费金额×优惠折扣率作为该区间的收费金额；按照立交桥费额规则计算出该路径的收费金额，取所有路径中最小收费金额作为这两个站点之间的客车费额。

C7.2：货车优惠费额计算：

用回溯法求得两个站点之间的所有路径后，取最短路径，若最短路径中包含优惠区间，则将路段内里程×优惠折扣率作为该区间的收费里程，按照货车计重公式计算出该路径的货车费额。

C8：两个站点之间经过标识站费额计算：

C8.1：客车标识路径费额计算：

用回溯法求得两个站点之间的所有路径后，即可获得两个站点之间所有包含指定标识站点的路径。对于每条包含指定标识站的路径，按照客车立交桥费额规则计算该路径的客车费额，取其中最小的费额作为这两个站点之间经过指定标识站的客车费额。

C8.2：货车标识路径费额计算：

用回溯法求得两个站点之间的所有路径后，即可获得两个站点之间所有包含指定标识站点的路径。从所有包含指定标识站的路径中取最短路径，按照货车计重公式计算该路径的货车费额，作为这两个站点之间经过指定标识站的货车费额。

车道建模计算费额方法较传统方法的优点

传统方法：将路网中所有两个站点之间的费额信息事先计算好，下发到车道，车道进行查表。整个路网的费额表数据量巨大，且随路段与标识站的增加呈指数级增长，该方法导致车道下载数据量大，核对困难，且费额信息固定，无法满足路公司的灵活优惠需求。

建模方法：将路网中涉及费额计算的基础信息下发到车道，车道根据基础信息，基于图论建模，按照费额计算规则计算出两个站点之间的费额。建模所需的基础信息数据量小，随路段和标识站的增加呈线性增长，该方法使得车道下载数据量小，核对容易，优惠费额可以根据优惠信息参数实时计算，能够满足路公司的灵活优惠需求。

附图说明

图1为本发明的一种高速公路联网收费系统统构架框图；

图2为本发明的高速公路联网收费系统数据传输构架框图；

图3为本发明实施例的高速公路路网图；

图4为本发明的高速公路费额计算建模图；

图5为本发明一个实施例的高速公路立交桥规则计费示意图。

具体实施方式

以下结合附图和实施例对本发明作进一步的描述

某省高速公路联网收费系统，目前采用本发明的方法实施的路段包括水武高速公路，武黔高速公路，绕城高速东北段，江合高速公路。

利用基于图论的高速公路联网收费车道建模计算费额的方法可以有效的解决上述难题。该方法介绍如下：

一种基于图论的高速公路联网收费车道建模计算费额的方法(如附图1、2所示)，其特点是，包括由联网收费结算中心1，路公司收费中心2，收费站3及车道4组成的高速公路联网收费系统构架；包含由车道41、收费站31、路公司收费中心21、联网收费结算中心11构成的联网收费系统数据传输构架。

所述的车道41从收费站下载基础信息，包括路段内费额、里程表，立交桥信息表，优惠路段表，优惠卡表等；车道41原始收费记录数据分为两路上传，一路上传收费站31、路公司收费中心21，一路上传联网收费结算中心11；

所述的收费站31从联网收费结算中心11获取基础信息并向路公司收费中心21上传特殊处理流水、图像信息、缴款信息、统计数据以及其他需要的数据。

所述的路公司收费中心21从联网收费结算中心11获取基础信息并向联网收费结算中心11上传路段汇总统计信息；

所述的联网收费结算中心11分别向路公司收费中心21、收费站31下发基础信息。

本发明的一种基于图论的高速公路联网收费车道建模计算费额的方法，还包括如下工作流程：

A：基础信息的加载

车道信息传输软件将计算费额所需的基础信息：路段内费额、里程表，立交桥表，优惠路段表，优惠卡表，从结算中心下载到车道数据库，车道软件将数据库中的基础信息读入到内存中；

B：车道基于图论建模(如附图4所示)

B1：将各条高速公路的各个收费站作为图的顶点V，连接两个收费站的路径作为边E，连接两个路段之间的边作为立交桥，将具有环路的部分作为有环部分(实线部分)，将不构成环路的部分作为射线部分(虚线部分)，构造出高速公路建模图G＝(V，E)；

立交桥计费规则(如附图5所示)：

图中A-E为路段1，E-D为路段2，E为两个路段的交汇点，A，B为路段1的两个收费站，C，D为路段2的两个收费站，B，C段为立交桥；则A-D的费额：F(AD)＝F(AB)+F(BC)+F(CD)；其中F(AB)为路段1中A，B两个收费站的审批费额，F(CD)为路段2中C，D两个收费站的审批费额，F(BC)为两个路段立交桥审批费额；

B2：车道软件加载基础信息后，将整个路网信息按照上述模型，使用邻接表的表示方法存入内存，形成路网模型；

C：车道利用模型计算费额：

任意两个收费站之间的通行费计算原则：客车费额按照“最小费额”原则计算，货车费额按照“最短路径”原则计算；

C1：客车费额计算规则：

(1)对于射线部分无二义性路径的两个站点之间的费额计算采用精确路径计算；

(2)对于有环部分存在有二义性路径的两个站点之间的费额计算，将最小费额作为通行费额；

(3)对于有环部分，通过各种标识路径法，对于能精确标识的路径部分采用精确路径计费；对于不能精确标识的路径部分采用最小费额计费；

(4)对于区间优惠路段，优惠卡优惠路段，按照优惠率计算优惠后的最小费额；

(5)路段内的两个站点之间的费额采用路段内审批费额；

(6)跨路段两个站点之间的费额按照立交桥规则计算：两个路段的路段内审批费额加这两个路段的立交桥审批费额；

C2：货车费额计算规则：

(1)对于射线部分无二义性路径的两个站点之间的费额计算采用精确路径计算；

(2)对于有环部分存在有二义性的路径中能精确标识的路径部分，采用精确路径计费；对于不能精确标识的路径部分采用最短路径计费；

(3)对于最短路径上有区间优惠路段，优惠卡优惠路段，则按照优惠率计算优惠后的收费金额；

(4)货车按照计重公式计算最短路径上的通行费额；

C3：两个站点之间客车货车费额计算方法：

(1)首先计算出这两个站点之间的所有路径；

(2)客车，对每条路径计算该路径的费额，取最小费额；

(3)货车，取最短路径，按照计重公式计算通行费额；

C4：利用回溯法计算两个站点之间的所有路径：

首先暂时放弃关于问题规模大小的限制，并将问题的候选解按某种顺序逐一枚举和检验；当发现当前候选解不可能是解时，就选择下一个候选解；倘若当前候选解，不满足问题规模要求，但满足所有其他要求时，继续扩大当前候选解的规模，并继续试探；如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解；

C5：两个站点之间的货车费额计算：

用回溯法求得两个站点之间的所有路径后，取其中里程最小的路径，就是最短路径，按照货车计重公式可以求得这两个站点之间最短路径上的货车费额；

C6：两个站点之间客车费额计算：

用回溯法求得两个站点之间的所有路径后，对每一条路径，按照客车立交桥费额规则计算该路径的客车费额，取其中最小的费额作为这两个站点之间的客车费额；

C7：两个站点之间的优惠费额计算：

C7.1：客车优惠费额计算：

用回溯法求得两个站点之间的所有路径后，对每一条路径，若路径中包含优惠区间，则将路段内收费金额×优惠折扣率作为该区间的收费金额；按照立交桥费额规则计算出该路径的收费金额，取所有路径中最小收费金额作为这两个站点之间的客车费额。

C7.2：货车优惠费额计算：

用回溯法求得两个站点之间的所有路径后，取最短路径，若最短路径中包含优惠区间，则将路段内里程×优惠折扣率作为该区间的收费里程，按照货车计重公式计算出该路径的货车费额；

C8：两个站点之间经过标识站的费额计算：

C8.1：客车标识路径费额计算：

用回溯法求得两个站点之间的所有路径后，获得两个站点之间所有包含指定标识站点的路径；对于每条包含指定标识站的路径，按照客车立交桥费额规则计算该路径的客车费额，取其中最小的费额作为这两个站点之间经过指定标识站的客车费额；

C8.2：货车标识路径费额计算：

用回溯法求得两个站点之间的所有路径后，获得两个站点之间所有包含指定标识站点的路径；从所有包含指定标识站的路径中取最短路径，按照货车计重公式计算该路径的货车费额，作为这两个站点之间经过指定标识站的货车费额。

其中，利用回朔算法搜索两个站点之间的所有路径，可以分成如下5种情况：

(1)射线上道射线下道的C-D，该路径唯一；

(2)射线上道环线下道的C-B，C到V3的路径唯一，只要搜索V3到B的所有路径；

(3)射线上道经过环线从射线下道的C-F。C-V3，F-V1路径唯一，只要搜索V3-V1的路径；

(4)环线上道射线下道的A-F，F-V1的路径唯一，只要搜索A-V1的路径；

(5)环线上道环线下道的A-B，搜素A-B的路径；

由此可见，由于射线部分路径唯一，搜素两个站点之间的路径归结为搜索这两个站点在有环部分的路径，这样可以减少回朔的搜索条数，对回朔进行剪枝，从而加快路径搜索效率；求得两个站点之间的所有路径，对包括标识站的路径进行标记，从而解决了获得两个站点之间经过指定标识站的路径问题。

所述的路网基础信息，包含路段内费额、里程表，立交桥表，该类信息随着路段的增加呈线性增加。实施例某一条路段包含10个收费站，则路段内费额、里程表增加的数据量为10×9×5＝450条，立交桥数量约为1-4条。

所述的优惠路段信息，包含年票路段信息，分时优惠路段信息等，该类信息较为固定，且数据量较少，约为20条。

所述的优惠卡信息，该类信息较为固定，约为4000条。

收费车道加载上述信息，通过建模，按照费额计算规则，计算出任意两个收费站之间的通行费额。

如某省路网(如附图3所示)，包括22个路段，120个收费站规模的基础信息总量为：5495(路段内费额、里程信息)+215(立交桥信息)+20(优惠路段信息)+4000(优惠卡信息)＝9730条，仅为传统费额表(30万条)的1/30。

在这些路段中，车道从结算中心下载的基础信息量约为10000条，下载时间约为1分钟，而传统方法路段，车道费额表下载量达到30多万条，下载时间约为30分钟。

综上所述，本发明采用基于图论的高速公路联网收费车道建模计算费额方法，解决了联网收费系统中费额表下载数据量大，下载时间长的难题。比较传统方法，该方法大大减少了费额表的数据量，提高了费额数据下载、核对的效率和准确性，且能满足路公司的各种优惠需求，在全国高速公路联网收费系统中具有推广意义。