取消省界收费站后的高速公路通行费用实时计算方案优化研究
发布时间：2022-01-23 17:35
为实现取消全国高速公路省界收费站,车辆通过省界不停车收费的工作目标,交通部提出以电子快捷收费为主、以车牌图像识别为辅、多种识别和支付手段融合应用的技术路径,对高速公路上所有车辆（包括ETC车辆和MTC车辆）实施分段计费。然而,各类型设备识别精度不够、恶意屏蔽通信、偷逃费行为增多及网络安全风险等种种原因导致部分车辆仍然存在路径信息缺失的情况。现行的查询对比方法环节较多耗时过长,难以达成车辆通过收费站不停车收费的目标。目前在路径信息缺失情况下使用的实时计算方案主要为费率表查询法,在省界收费站拆除后路网结构的叠加导致费率表计算复杂度呈几何级增长,同时高速公路仍在不断建设联网接入系统,费率表更新频繁,采用费率表法枚举的全部路径会有十分庞大的数据量,参数的生成、存储、传输、运算和特殊情况处理都将成为问题。本文通过分析对比现行各种方案的技术路线、适用范围及存在不足后,提出将基于异构并行计算的最短路径算法应用到高速公路多义性路径收费中,使车道收费站利用商品化的桌面级计算机即可具备实时计算大规模路网中任意两个节点间最短路径的能力。论文主要工作如下:（1）按照图论建立高速公路的路网模型,提出取消省界收费...
【文章来源】：华南理工大学广东省 211工程院校 985工程院校 教育部直属院校
【文章页数】：88 页
【学位级别】：硕士
【部分图文】：
取消省界收费站收费方案总体技术路线
华南理工大学硕士学位论文32图2-5有向图在GPU上的表达方式本文是研究基于异构计算的图算法，在异构计算中存储图数据需要考虑主机端和设备端的计算任务区别和协同，主要有以下三个因素：一是设备段的显存容量与主机端的系统内存容量比较相对有限；二是主机端和设备端需要来回传输数据；三是主机端和设备端使用不同的内存空间，造成不易操作图形中的指针数据，因此一般采用存取效率最高的图形数组形式数据结构。2.3.2路网数据结构本文主要使用英伟达公司的开源平台CUDA实现最短路径的通行费率实时计算。CUDA的图函数nvGRAPH将图的拓扑(连接)从值中分离出来。为了简化拓扑的指定，CUDA的图函数支持三种拓扑类型，每种拓扑类型都定义了自己的存储格式，每种格式都各有优劣，分别为NVGRAPH_CSR_32、NVGRAPH_CSC_32、NVGRAPH_COO_32。表2-3CUDA图函数的三种拓扑类型NVGRAPH_CSR_32压缩稀疏行格式(行主格式)。用于SrSPMV算法。对于这种格式使用nvgraphCSRTopology32I_t拓扑结构。NVGRAPH_CSC_32压缩稀疏列格式(列主格式)。用于SSSP,WidestPath和Pagerank算法。对于这种格式使用nvgraphCSCTopology32I_t拓扑结构。NVGRAPH_COO_32与源或目标专业协调列表格式。不用于任何算法，只提供数据存储。此格式使用nvgraphCOOTopology32I_t拓扑结构。
第三章基于异构并行计算的最短路径算法研究37组合属性是Dijkstra算法及其变种的基础，用于弧上包含正值和空值权重的图。算法维护数组dist来保存从源点s到目标顶点v的距离；对于没有找到任何s-v路径的目组合属性是Dijkstra算法及其变种的基础，用于弧上包含正值和空值权重的图。算法维护数组dist来保存从源点s到目标顶点v的距离；对于没有找到任何s-v路径的目标顶点v，保存+∞。因此，图的顶点被分成三组。黑色顶点是从源点出发的已知最短路径顶点，灰色顶点是黑色顶点的直接相邻顶点，白色顶点是还没有找到任何路径的顶点。图3-1最短路径网络图刚开始，只有源点s是黑色的，其dist[s]=0。s的直接相邻顶点都是灰色的，dist[v]是弧(s,v)的权重。其他顶点都是白色的。然后，算法循环标注一个顶点的颜色为黑色或灰色，并把其相邻白色顶点标注为灰色，其他维持不变。最终，所有从源点可到达的顶点都会被标注为黑色，而其他顶点会是白色。在每次遍历过程中，我们都要寻找一个灰色顶点v使得dist[v]最小，所以使用一个优先级序列来存储顶点v的候选者是合理的，dist的值成了优先级的值。这就是Dijkstra算法选择的实现方式，其时间复杂度为O(V2)。
本文编号：3604845
【文章来源】：华南理工大学广东省 211工程院校 985工程院校 教育部直属院校
【文章页数】：88 页
【学位级别】：硕士
【部分图文】：
取消省界收费站收费方案总体技术路线
华南理工大学硕士学位论文32图2-5有向图在GPU上的表达方式本文是研究基于异构计算的图算法，在异构计算中存储图数据需要考虑主机端和设备端的计算任务区别和协同，主要有以下三个因素：一是设备段的显存容量与主机端的系统内存容量比较相对有限；二是主机端和设备端需要来回传输数据；三是主机端和设备端使用不同的内存空间，造成不易操作图形中的指针数据，因此一般采用存取效率最高的图形数组形式数据结构。2.3.2路网数据结构本文主要使用英伟达公司的开源平台CUDA实现最短路径的通行费率实时计算。CUDA的图函数nvGRAPH将图的拓扑(连接)从值中分离出来。为了简化拓扑的指定，CUDA的图函数支持三种拓扑类型，每种拓扑类型都定义了自己的存储格式，每种格式都各有优劣，分别为NVGRAPH_CSR_32、NVGRAPH_CSC_32、NVGRAPH_COO_32。表2-3CUDA图函数的三种拓扑类型NVGRAPH_CSR_32压缩稀疏行格式(行主格式)。用于SrSPMV算法。对于这种格式使用nvgraphCSRTopology32I_t拓扑结构。NVGRAPH_CSC_32压缩稀疏列格式(列主格式)。用于SSSP,WidestPath和Pagerank算法。对于这种格式使用nvgraphCSCTopology32I_t拓扑结构。NVGRAPH_COO_32与源或目标专业协调列表格式。不用于任何算法，只提供数据存储。此格式使用nvgraphCOOTopology32I_t拓扑结构。
第三章基于异构并行计算的最短路径算法研究37组合属性是Dijkstra算法及其变种的基础，用于弧上包含正值和空值权重的图。算法维护数组dist来保存从源点s到目标顶点v的距离；对于没有找到任何s-v路径的目组合属性是Dijkstra算法及其变种的基础，用于弧上包含正值和空值权重的图。算法维护数组dist来保存从源点s到目标顶点v的距离；对于没有找到任何s-v路径的目标顶点v，保存+∞。因此，图的顶点被分成三组。黑色顶点是从源点出发的已知最短路径顶点，灰色顶点是黑色顶点的直接相邻顶点，白色顶点是还没有找到任何路径的顶点。图3-1最短路径网络图刚开始，只有源点s是黑色的，其dist[s]=0。s的直接相邻顶点都是灰色的，dist[v]是弧(s,v)的权重。其他顶点都是白色的。然后，算法循环标注一个顶点的颜色为黑色或灰色，并把其相邻白色顶点标注为灰色，其他维持不变。最终，所有从源点可到达的顶点都会被标注为黑色，而其他顶点会是白色。在每次遍历过程中，我们都要寻找一个灰色顶点v使得dist[v]最小，所以使用一个优先级序列来存储顶点v的候选者是合理的，dist的值成了优先级的值。这就是Dijkstra算法选择的实现方式，其时间复杂度为O(V2)。
本文编号：3604845
本文链接：https://www.wllwen.com/jingjilunwen/jtysjj/3604845.html
