第一章 绪论
1.1 研究背景
1.1.1 背景
任务党中央、国务院高度重视交通物流运输效率问题，多次作出重要指示。2015 年 12月，习近平总书记提出要推进流通行业的体制改革，研究如何进一步提高流通运输效率、有效平衡各种运输方式、降低各种物流费用。2018 年再次要求，要大力提升综合交通运输网络效率，降低高速公路、空中运输、海上运输、铁路运输等费用，降低物流成本。2018 年 5 月 16 日，国务院常务会议上明确提出：“推动取消高速公路省界收费站”，确定进一步降低实体经济物流成本的措施，进一步促进物流降本增效，高速公路要着重研究措施在服务能力和服务水平上进行大力提升，要进一步在保障经济社会发展和服务百姓安全便捷出行上提高水平和效率。
为将党中央、国务院的决策部署落到实处，交通运输部作出统一安排，成立专项工作组，按照“试点先行、稳妥有序”的原则，研究制定了总体工作方案、建设实施和系统测试方案，明确了关键技术要求等，并在确定的试点省份开展了大量基础性技术调试以及工程系统建设改造等工作。在部省两级密切协同及全力推进下，专项工作组按照时间节点推进阶段性任务，并积累了大量经验。2018 年 12 月 28 日，江苏省、山东省、四川省和重庆市作为高速公路相互连通的试点省市，全部取消了相互之间的高速公路省界收费站，以往车辆积聚在省界收费站缴费造成的交通拥堵现象得以解决，大大提升实体经济物流效率，试点情况获得了社会多方的好评[1]。
2019 年 3 月 5 日召开的十三届全国人大二次会议上政府工作报告提出：“两年内基本取消全国高速公路省界收费站，实现不停车快捷收费，减少拥堵、便利群众。”3 月 15 日上午十三届全国人大二次会议的答记者问中，再次提及：“政府工作报告提出，两年内要基本取消省界高速公路收费站，大家都很赞成。这样做有利于解决拥堵问题，也有利于相关产业发展。这个目标我们要确保完成，同时我们要求有关部门力争提前实现。”
...........................
1.2 取消省界收费站总体技术方案分析
为坚决贯彻落实上级关于“两年内基本取消全国高速公路省界收费站，实现不停车快捷收费，减少拥堵、便利群众”的决策部署和克强总理提出的“力争提前实现”、“有利于相关产业发展”的重要指示精神，交通部 2019 年在总结取消高速公路省界收费站试点工作经验的基础上，根据本国高速公路路网发展建设、运营和收费技术现状，明确出台“实现电子不停车快捷收费（ETC）、辅以车牌图像识别、多种支付手段融合应用”的技术路线[8]。
1.2.1 总体技术路线
撤销高速公路省界收费站工作主要技术路线具体如下：
（1） 取消高速公路省边界收费站，布局建设 ETC 门架系统，并通过该系统对所有行驶车辆（包括 ETC 和 MTC 车辆）进行计费和收费。
（2） ETC 车辆使用 OBU（车载单元）进行信息交互，采用后台记账形式实施费用自动扣除，将来逐步实施“预约通行”的出行和收费体系。
（3） MTC 车辆将 CPC 卡（5.8GHz 复合通行卡）作为车辆高速公路交通介质，实施“分段计费、出口收费”的收费方式。
4） 保留入/出口匝道收费站。根据车流量科学规划 ETC 车道数目，确保各车道车辆不用停车排队缴费实现快捷通行；MTC 车道的主要功能逐渐转变为对未安装 OBU车辆及其他特殊情况车辆进行查询收费。
（5）货车由计重收款逐步调整为按车型收款，安装车载单元 OBU 不用停车排队缴费实现快捷通行。在入口收费站同步对超载超高等行为的车辆实施检查，在收费广场划分合适位置规划新建车辆称重检测设施（设备），在入口收费站检测的称重等数据需与车辆收费、检查等工作统一协同。
.............................
第二章 高速公路收费网络模型和数据结构
2.1 收费网络的图模型
将高速公路与图论内容结合，高速公路收费网络可抽象为数学上的“图”的概念。图(Graph)： 指有序三元组( V( G)， E( G)，ψ)，简记为( V， E，ψ)，这里 V 非空集，称 V 是图 G 的顶点集( vertex-set)，它的元素称为图 G 的顶点(vertex)(或点(point))，而称 E 是图 G 的边集(edge-set)，它的元素称为图 G 中的边(edge)。而 Ψ 是关联函数，指集合 E 到集合 V 中的元素有序对或无序对簇 V×V 的关联关系。Ψ 主要是描述顶点和边之间的联系。若 V×V 中全是有序对，则称( V， E，ψ)为有向图（digraph）， 记为D=( V( D)， E( D)，Ψ D)。相反，若 V×V 中元素全是无序对，则( V， E，ψ)称为无向图（ undirected graph 或 graph），记为 G=（ V( G)， E（（ G），Ψ G）。
在高速公路网络中，所有路段都是有方向性的，因此研究的图是有向图。
在高速公路网络中，收费站、互通立交、ETC 门架都抽象为顶点。
环（loop）：两端点相同的边，大部分高速公路路段都属于这种情况。
平行边(parallel edges)：指两条边有相同的起点同时又有相同的终点，又称为重边(multi-edges)，在实际的高速公路规划中，严格定义上的平行边没有意义，一般不会出现。
简单图(simple graph)：无环并且无平行边的图。对于高速公路总里程较少的地方来说可以看作简单图，但研究意义不大。
...........................
2.2 路网生成模型
2.2.1 路网各要素的编码
假设路段 L1、L2、L3，收费站 S1、S2…S6，互通枢纽 N1、N2、N3，ETC 门架F1、F2，构成如下路网图：
一个高速公路路网由多条高速公路构成，主要要素有：
1）点：包括收费站点、互通枢纽、ETC 门架；
2）路段（边）：各路段，以站点间构成一个路段；
3）路线：相邻的连接部分被分段地连接以形成路线，即行驶路径。
多个高速公路通过立交点和起点相互连接以形成道路网络。 为了实现车辆行驶路径识别，需要在可能出现歧义路径的路段上建立车辆路径识别点（ETC 门架）。
.............................
第三章 基于异构并行计算的最短路径算法研究.............................36
3.1 经典的最短路径算法................................... 36
3.2 GPU 并行计算和 CUDA 平台简介............................ 39
第四章 基于异构计算的大规模高速路网通行费率实时计算方案.....................48
4.1 总体技术路径............................... 48
4.2 优化的经典最短路径算法....................... 48
第五章 实际通行费用的仿真分析.....................60
5.1 实际通行费用计算原理............................ 60
5.2 实际通行费用计算流程..................... 62
第五章 实际通行费用的仿真分析
5.1实际通行费用计算流程
根据前述的实际通行费用计算原理，我们建立通行费用计算流程如图 5.2 所示。如果车辆全程路径信息完整，利用公式（5-1）可以直接计算出实际的总通行费用。如果车辆有部分路径信息缺失，在路径信息不完整的区间，本课题基于最短路径原则，利用最短路径算法寻找路径信息丢失的节点之间的最短路径，即使用公式（5-2）计算出缺失区间通行费用，同时通过公式（5-1）直接计算出未缺失路径信息区间的通行费用，两者相加即可得出车辆通行总费用。
由图中可看到，核心的计算过程就是前述的最短路径计算问题，也是本课题的最长耗时环节。图中，参与路径信息缺失路段计算的路网数据库、路网权重数据库（图中虚框所示），是事先已生成好的数据，可直接参与计算，不会增加计算时间。
........................
总结与展望
总结
本课题针对取消省界收费章后高速公路路径信息不完整车辆的通行费用计算问题，提出基于异构并行计算最短路径的高速公路通行费用实时计算方案，提高了收费终端的计算速度和计算效率，使每个终端利用商品化的桌面级计算机都能具备实时计算任意两个站点间的最短路径的能力，以满足高速公路路网日益复杂条件下，特情收费的实时性要求，进一步优化高速公路取消省界收费站后的收费工作。论文总结如下：
1.对高速公路路径信息缺失车辆收费问题进行研究。首先是目前实施的“分段计费”技术方案，该方案主要是实行车辆行驶路径精确识别的技术路线，但由于恶意偷逃费、CPC 卡等无线通行计费设备容易被屏蔽、ETC 门架等设备对路径的识别存在遗漏情况、网络安全风险等因素，仍有相当一部分车辆存在路径信息缺失及多义性路径的情况，目前对此采取一系列的查询对比方式环节较多耗时过长，难以达成车辆通过收费站不停车收费的目标。
其次对高速公路多义性路径研究现状和各地的实施情况进行分析。在路径识别技术发展的情况下对于车辆路径信息缺失并存在多义性路径的情况，目前主流仍是按照最短路径原则进行收费，即在路径信息缺失的区间，对车辆按照“最短路径”或“最小收费额”收取通行费用。传统的最短路径算法其算法复杂度为 O（V2）或者是 O(ElogV)，基本上和站点数量二次方成正比。传统的最短路径算法是串行处理的搜索算法，在取消省界收费站前对于大规模复杂路网已经很难实现 50ms-100ms 内的车道计算时间要求，也就一直没有在大规模复杂路网的收费系统中得到实际应用。
参考文献（略）