车辆位置数据处理及动态出行路径诱导技术

《车辆位置数据处理及动态出行路径诱导技术》论文发表期刊：《信息技术》；发表周期：2020年12期

《车辆位置数据处理及动态出行路径诱导技术》论文作者信息：张春辉(1986－) ，男，硕士，工程师，研究方向为智能交通。

　　摘要：车辆路径诱导技术的发展，为公众的日常出行提供了极大的便利。为了提高车辆诱导技术的诱导精度，研究对Djkstra最短路径算法进行了改进，提出了动态最短路径诱导技术。通过在S市路网中的仿真分析，验证改进算法的有效性。研究结果显示，车辆的路径诱导结果符合实际交通状况，且在两个时段的预测行驶时长仅相差26.3s，这说明动态最短路径诱导技术具有可行性，并且能够较好地满足公众日常出行需要。此次研究所提出的动态最短路径算法表现出良好的可行性和适用性，并对于提高车辆出行效率、改善城市交通堵塞等问题具有借鉴性意义。

　　关键词：车辆位置：数据;出行;路径;算法

　　Abstract: The development of vehicle route guidance technology provides great convenience for the public' s daily travel. In order to improve the guidance accuracy of vehicle guidance technology, Dijkstra shortest path algorithm is improved, dynamic shortest path guidance technology is proposed. Through the simulation analysis in S city road network, the effectiveness of the improved algorithm is verified. The research results show that the results of vehicle route guidance are in line with the actual traffic conditions, and the predicted driving time difference between the two periods is only 26. 3s, which shows that the dynamic shortest route guidance technology is feasible and can better meet the needs of public daily travel The dvnamic shortest route algorithm proposed in this study shows good feasibility and applicability, and has reference significance for improving vehicle travel efficiency and improving urban traffic congestion.

　　Key words: vehicle location; data; travel; route; algorithm

　　0 引言

　　车辆的交通信息是交通管控的基础，它实时地反映了车辆位置的变化情况。目前被广泛应用的交通信息采集方式有两种，分别是路基型和车基型检测器。路基型检测器主要是利用电磁波、声波、红外光波等进行车辆信息的检测和采集，车基型检测器的代表是浮动车技术。但是在实际应用中，这两种检测技术都有其局限之处，路基检测器的实时性和准确性较差，浮动车技术无法保证检测精度2。随着城市交通网的形成，车辆的路径导航技术逐渐成为民众出行的日常需求。在这一背景下，交通信息的准确性直接影响到路径导航技术的有效性，对采集数据进行评价和误差控制是车辆路径导航的基础1。除此之外，数据的实时动态性已经逐渐成为车辆导航技术的发展趋势，导航路径的行驶时间和准确率直接体现了车辆导航技术的性能。这次研究考虑到交通实时路况的影响，提出了动态最短路径算法，以期能提高车辆动态出行路径诱导的有效性和准确性。

　　1车辆位置数据的预处理及误差控制

　　车辆导航技术需要以车辆的位置信息为基础，结合数据处理技术，得到速度、交通流状态等多层面信息。由于车辆检测器的局限性，原始的车辆位置数据存在数据缺失、数据突变等问题。为了保证后续系统分析的有效性，在这里将原始的车辆位置数据进行预处理，并对处理后的数据进行误差控制。

　　在车辆位置数据的预处理中，主要从三个方面提高位置数据集的质量。一方面，当车流检测数据中存在某一时间段无车辆行驶的情况时，需要将这种情况确认为位置数据缺失，并将其从可用数据集中删除。另一方面，当突发交通事故时，路基车辆检测器的车辆位置数据会产生突变。这种突变数据无法体现出数据的趋势变化，会影响车辆导航系统的道路预测效果。但是当突变数据样本数量增加时，它可以反映出道路的拥挤程度。在车辆位置数据的预处理中，可以通过下述公式评价数据的突变性。

　　用p表示数据的突变性阈值：用D(t)表示车辆位置信息的实测数据值：n，为车辆位置信息的历史数据数量，通过式(3)可以得到数据的历史趋势值D，(r)。根据式(1)-(2)可知，将实测数据与历史趋势值相比，若在连续两个时间间隔后，其偏离幅度超过突变性阈值，则认定实测数据为突变性数据：若在连续两个时间间隔后，其偏离幅度小于突变性阈值，则认为数据突变结束。

　　此外，城市交通系统庞大且复杂，交通信息难免受到各种因素的影响，进而造成车辆位置数据的错误。在车辆位置信息的预处理中，需要将错误数据识别出来，并进行修复或删除，以免错误数据影响后续分析的精度。在进行错误数据的识别判断时，需要先设定正确数据的范围，当超过这个范围时，则将实测数据视为错误数据。式(4)、(5)分别表示正确数据的上限和下限。其中，o(r)表示历史位置数据的标准差。

　　有研究表明，影响车辆位置数据精度的因素主要有三个方面，分别是GPS定位误差、GIS地图匹配误差、GPS/DR融合误差0-]。表1为GPS误差分类。根据GPS系统的信号传输过程，可以将GPS定位误差分为卫星部分、信号部分、信号接收部分和其他影响。前三种情况会导致1.5m~10.0m的测量误差，最后一种情况所导的测量i差为1.0m.

　　由于车辆位置信息匹配到GIS电子地图中，会经过数据传输等一系列过程，因此GIS电子地图存在一定程度的误差。有研究表明，GIS地图的比例尺与匹配误差存在定量关系，且匹配误差随着比例的增加而增加-10。如表2所示，当比例尺为1：5000时，电子地图的匹配误差为1.0m：当比例尺为1：10000时，电子地图的匹配误差为2.0m：当比例尺为1：25000时，电子地图的匹配误差为5.0m.

　　组合定位技术是目前新兴的车辆定位技术，以GPS/DR组合定位为例，这种方式使得GPS和DR的定位信息能够相互校正补偿，从而改善单一定位技术的定位精度和可靠性。但是在GPS/DR的融合过程中，存在状态估计误差和传播误差。目前的解决方案是通过引入智能算法，降低数据融合的误差，进而得到高精度的定位数据，如利用卡尔曼滤波器修正状态估计误差、利用小波分析进行信号降噪等。

　　2基于改进Dijkstra算法的车辆动态路径诱导技术

　　2.1基于行程时间短时预测的动态简化路网模型

　　在进行城市路径诱导研究中，需要先建立城市路网模型。传统的路网模型由两个部分组成，分别是表示路段的有向弧和表示道路交叉口的节点，这种路网模型又称有向图。随着路网研究的深入，传统的路网模型已经不能满足实际工作的需要，对真实路网进行简化得到的路网模型，更能展现实际路网中的限制信息[2-1]。由于城市每天的交通状况呈现出潮汐性变化规律，因此车辆导航系统需要参考城市交通的动态变化规律，进行合理的路径诱导。在这里将建立动态简化路网模型，如图1所示，并在此基础上进行后续的路径诱导研究。

　　图1(a)为传统的路网模型，其中A表示道路交叉口节点，B.C、D、E表示有向路段：图1(b)为动态简化路网模型，在这里用G表示：用V表示路网交叉点，即模型的节点：用01表示交叉口的出口道数量：用E表示路网中的有向路段集合：用T表示时间序列，AT为时段间隔：用W表示路段行程时间的权值集合。下述表达式为动态简化路网模型的数学表达式。

　　根据城市交通规律，动态路网模型可以根据时段划分进行构建，也可以根据行程时间短时预测进行构建。在时段间隔极小的情况下，根据时段划分的动态路网模型可以实时更新当前的路况情况，但是这种方法无法反映出未来的交通状态。在根据行程时间短时预测构建的路网模型中，将交通参数的短时预测考虑到动态最短路径规划中，这种方式的诱导精度更好。假设短时预测的路网模型考虑到未来s时段的路况变化，且S= 1，2，..，M;用，表示预测的路段行程时间：用w，表示与当前交通状况相似的历史行程时间数据。根据行程时间短期预测所构建的动态简化路网模型，需要在式(6)的基础上，增加下述的数学表达式。

　　2.2 基于Dijkstra算法的静态最短路径诱导技术车辆的路径诱导技术的关键在于最短路径的计算。在简化的路网模型中，通过智能算法使得每一路段的行程时间达到最短，可以得到车辆导航的最短路径。根据交通信息的状态，可以将最短路径问题分为两种类型：静态最短路径和动态最短路径。静态最短路径问题是在静态的交通信息中进行最短路径研究，动态最短路径问题是将交通信息的参数变化考虑到最短路径研究中。经典的最短路径算法有Floyd算法、A*算法、分层搜索法、遗传算法、Dijkstra算法等，其中Djkstra算法是目前应用发展最完善的算法。因此这次研究将采用Djkstra算法进行最短路径的算法研究。Dijkstra算法从源点出发，按照路径长度逐点增长的方式，构建一颗路径树。它采用的是一种贪心策略，以源点为中心向外层层扩散，从而求出源点到其它顶点的最短路径。在这一算法中，需要引入集合S和U，集合s用于记录已求出最短路径的顶点和相应的最短距离，集合U用于记录还未求出最短路径的顶点及其到源点的距离。

　　Dijkstra 算法仅适用于边权为非负的情况，在路网结点很多时，这种算法的搜索效率会降低，且它的搜索速度受限于地图的存储结构。对于动态最短路径问题，这里将在经典Dijkstra算法的基础上进行改进，使其能适用于真实路网状态下的最短路径搜索。

　　2.3 基于改进Dijkstra算法的动态最短路径诱导技术

　　在动态的路网中，每一个路段的行程时间都是动态变化的。由于交通规则等节点属性的限制，使得行程时间具有可预测性。车辆进入路段的时刻决定了这一路段的行程时间，但只有在搜索过程中才能确定车辆进入路段的时刻。假设AT为一个时段的长度，用1表示不同时刻：用k表示行程中的不同路段，且路段是时刻具有连续性：当车辆经过路段k时，时间范围为r4]：用7，表示车辆经过整个路段的用时。图3为动态行程时间的计算模型。其中，横坐标表示时间，纵坐标表示速度，横、纵坐标的区域面积为在7，时段内的行驶距离。因此，这一模型的唯一约束条件为阴影部分面积等于1分析图3的计算模型，可以得到下述方程。其中，x表示车辆到达路段 时的时段起点序号：T.表示路段k在时段(X，+i-1)的行程时间。

　　根据上述的路段行程时间权值公式，结合实时的交通信息计算出路段权值T，以此对Dijkstra算法进行改进。在改进算法中，需要根据路段行程时间预测表更新权值，以此实现最短路径搜索的动态化。

　　3基于动态最短路径诱导算法的仿真

　　分析

　　为了验证改进Dijkstra算法在路径诱导上的有效性，在这里选取s市的真实路网进行仿真实验，实验路段的简化路网模型如图4所示。在实验中，采用1：20的比例尺对路段长度进行缩放，将车辆位置数据加载到Mapx 5.0平台，采用Visual C++6.0进行改进Dijkstra算法的编译工作。

　　图4为S市实验路网的简化模型，根据路网结构可以发现，以A点为起始点，以J点为目的地，路网中共有15个交叉口。在实验开始前对各个交叉口的主要路口进行编号，例如，交叉口A有三个主要路口，分别是A1，A2、A3。将各个交叉口的交通规则作为路网简化模型的节点属性，进行仿真实验。根据图4的简化路网模型，建立路网节点邻接表，如表3所示。

　　考虑到城市交通的潮汐性变化规律，分别选取了工作日的高峰期和平峰期两个时段进行实验，并设置实验的周期长度为15min，时段间隔为180s，路段的行程时间来源于对10辆汽车行驶实测数据的平均值，并假设第一时段的起始时刻为系统接受响应的时刻。表4为高峰时段和平峰时段的路网动态行程时间，由于篇幅限制，这里仅展示部分数据统计结果。

　　根据改进Djkstra算法搜索动态行程时间最短路径，表5为仿真实验的统计结果。通过统计结果可以发现，在改进Dijkstra算法的路径诱导中，平峰时段和高峰时段的最短路径诱导结果是不同的：在平峰时段车辆经过6个路网节点，在高峰时段车辆经过10个路网节点：平峰时段的诱导路径行驶时间为274.4s，高峰时段的诱导路径行驶时间为300.7s.

　　结合实际的交通状态进行分析，在平峰时段，起点和目的地之间的道路处于畅通状态，因此最短路径处于主干道上：在高峰时段，主干道的交通拥挤，此时需要避开拥挤路段，选择车流量较少的路段。

　　在改进Dijkstra算法下，车辆在平峰时段和高峰时段的路径诱导时长仅相差26.3s，这说明动态最短路径诱导技术具有可行性，路径诱导结果符合实际交通状况，可以满足实际出行的需要。

　　4结束语

　　传统的路径诱导技术是根据当前车辆位置数据进行路径诱导，这种方式无法应对突发交通事故的影响。为了提高路径诱导技术的灵活性和实用性，这次研究在经典的Dijkstra最短路径算法基础上，考虑到路段行程时间权值的动态变化，以此提出了车辆的动态最短路径诱导算法。此外，为了提高路径诱导的精度，这里提出对车辆位置数据进行预处理和误差控制。通过对s市的实验路网进行仿真分析得出，这次研究所提出的动态路径诱导算法具有良好的适用性，希望此次研究能在车辆路径诱导的研究和应用中提供一些参考。此外，这次研究尚且存在不足之处，如未能将算法的诱导结果与实际行驶结果进行对比，这将在以后的研究中作出改进。

　　参考文献：

　　[1]丁宏飞，秦政，刘博，等，基于AFSVR的城市快速路多源交通信息融研t机1程与用，2017，53(5)：266-270.

　　[2]辛燕，冯霞，李婷婷.VANET中位置相关的轻量级Sybil攻击检测方法[1].通信学报，2017，38(4)：110-119

　　[3]李祎承，胡钊政，胡月志，等·基于GPS与图像融合的智能车辆高精度定位算法[].交通运输系统工程与信息，2017，17(3)：112-119.