GPS物流车辆导航系统中地图匹配算法的实现

滕威

(陕西交通职业技术学院 经济管理学院， 陕西 西安 710014)

0 引言

目前车辆监控系统主要通过结合使用GPS定位及计算机数据处理等技术手段实现车辆监控过程，物流行业随着电子商务的快速发展而得以快速成长和完善，在社会经济中起到非常重要的作用，行业内的竞争也愈发激烈，科学高效的物流信息系统有助于物流企业提升竞争力，而作为物流信息系统的关键环节之一，定位系统对物流信息系统产生直接影响，因此提升物流信息系统的质量需最大程度减小定位误差，将更加稳定可靠的服务提供给用户，目前多种车辆定位技术在资源等原因的限制下存在不同程度的误差，本文完成了物流车辆运输定位监控系统的设计，系统基于GPS的地图匹配技术，具有较高的实际应用价值。

1 物流行业需求分析

物流管理的主要目的在于降低成本的同时提升服务水平，对车辆的详细信息能够做到及时准确掌握和获取十分重要的作用，信息技术的使用为物流运输管理提供了有利支撑，在物流企业的发展过程中，4G (GPS/GIS/GSM/GPRS)起到了积极的促进作用，物流车的GPS监控和管理功能的有效实现对物流行业具有重要意义。物流行业的实际发展过程中所表现出的主要需求特点在于：物流业务范围及覆盖地域极为广泛，运输车辆较多，涵盖了大量的数据信息；用户大多要求及时掌握位置服务信息，在运输过程中需对不同的区域和线路进行严格准确的监控，并同货运单据有效对接起来；要求具有较高的安全性，运输监控系统响应需灵活、及时；要求车辆定位监控系统中的数据具有较高的共享程度。车辆管理信息有待进一步完善，本文主要对物流车辆运输定位监控系统进行了设计[1]。

2 车辆运输定位监控系统设计

2.1 GPS车辆管理系统功能

本文所设计的系统基于GPS的地图匹配技术，具备动态、实时、精确、双向等优势，核心在于能够进行远程指挥和监控的管理平台，通过将GPS监控设备安装在运输车辆上，通过设备上的GPS模块即可将运输车辆的地理位置信息传输至监控中心(通过无线网络)，通过电子地图即可查看车辆所在的具体地理位置，实现远程监控，同时可对常用功能进行设置(上传间隔、车辆信息记录等)，远程控制设备通过发放指令实现对启动状态等的限制。

完整的监控系统由GPS终端、传输网络及监控平台3个要素构成，GPS/GSM/CDMA车载终端与中心间的通讯连接以网络为载体实现，具有较高的数据传输能力，查询监控的时效性更高，误码率比较低，可有效实现较大范围稳定可靠的监控过程。将GPS终端安装在不同的车辆上，通过GPRS/CDMA无线通信网络或短信的方式完成数据传输，GSM网络主要负责将GPS定位和收集到的信息传递至信息调度中心，及时掌握入网移动目标的地理位置，再将调度中心的信息传输给不同的车载设备，实现不同车辆具体地理位置信息的检测及确定(显示在电子地图上)，在此基础上可实现安全有效的监控和调度。此外还可实现导航的过程，具体如图1所示。

图1 导航处理过程

在地图上寻找起始和终点间的最优路线，使穿越耗时最少[2]。

2.2 地图匹配算法

指通过载体上的GPS接收机设备完成地理位置的确定，在复杂的交通网中完成车辆的精确定位并实时更新，不断更正地理位置。地图匹配过程的顺序为：首先通过使用GPS系统确定车辆行驶路线，在将其同电子地图中的行驶路线比对，找出最优路线，所使用的电子地图匹配算法会对车辆定位的准确度产生直接影响，该算法的重点在于找到校正点，具体的算法流程为：(1) 首先以车辆所在的位置为圆心，根据实际需要恰当选取半径后画圆，判断公路图层中对象同圆间的位置关系(相交则计算相交对象的个数)，对于一个以上的对象需缩小圆的半径，无对象则扩大圆的半径直至找到符合条件的对象(圆的半径大于限定值时表示车辆进入了停车场类的位置，则以圆心为校正点跳至第四步)。(2) 根据不同判断时间存在循环中公路对象名称不一致的情况，若相同则表明两点位于同一公路，可直接跳至第四步；若不一致，则可能存在车拐弯情况，无法判断车辆点同时保存记录(包括车辆点和最近路线)，若需取下一个点则返回步骤(1)重新开始。(3) 对公路对象的全部拐点进行读取，找出车辆点到相邻两拐点连线的垂足，计算出车辆点同垂足的距离，有垂足且距离最小时垂足即为校正点。(4) 标记所获取的校正点，取下一车辆点进行判断[3]。

2.3 基于曲线拟合的地图匹配算法

矢量电子地图由图元组成道路，各元位置精确，电子地图中的道路通常由直线或折线表示，能够用直线来模拟历史行车轨迹(在一定行驶距离内)，本文拟合用直线，选取5个观测点作为一次模拟曲线，即用直线来拟合，具体原理如下。

5个观测点的平面坐标由(x,y)表示，据此计算轨迹拟合直线的斜率为式(1)。

(1)

判断车辆可能的行驶方向k，在路段误差范围内(轨迹夹角小于30度)，需对车辆位置信息进行再次确认，考虑到GPS自身存在的误差，候选路段需在被测位置点方圆60 m内，k0表示候选路段的斜率，k表示拟合直线的斜率；对于候选路段同测位置点，d表示其垂直投影距离；P1表示夹角；P2表示距离的权值，地图匹配算法的评价函数s表达式如式(2)。

(2)

最小值即为最优匹配路段[4]。

2.4 基于权重的地图匹配算法

车辆当前行驶道路以根据道路交通网络的弧确定的权重为依据，然后确定车辆在当前道路中的位置(即在当前道路上车辆定位点的投影点)，以定位点和道路交通网的弧间的关系为依据确定权重的计算模型[5]，如图2所示。

图2 定位点和道路交通网的关系

取n个GPS定位点，各候选道路施加的权重为平均值，以消除偶然误差的影响，C表示权重为正值的常数值；i表示候选道路的编号;kd表示GPS定位点同道路间的投影距离;ko表示行驶方向同道路间的夹角θi的权值系数，则对各候选道路施加的权重[5]表示如式(3)。

ωi=C-(kd×di+kθ×θi)

(3)

3 地图匹配算法的实现

3.1 运输导航的最短路径算法

物流运输需从当前位置到达指定位置，最短路径在于花费最低的代价到达目的地，最佳路径即为综合代价最低的路径，电子地图导航的搜索最佳路径功能可有效满足用户需求，通过使用某种特定准则的算法实现最优路径搜索功能，在道路交通拓扑网络中，以节点—弧线拓扑关系和算法为依据，完成最佳路线的获取，公路交通网络中适合使用Dijkstra算法，具体流程如图3所示。

图3 Dijkstra算法流程

该算法基于现实情况，寻找节点间的最短路线，算法结束时即为找到了最短路线[6]。

3.2 道路搜索的实现

无法确定车辆初始定位、车辆行驶道路时需进行道路搜索，具体流程如下。

(1) 获取特定时刻的具体定位后，根据行驶速度值m-speed及PDOP值进行预估，通常在PDOP>6，m-speed>200时表明GPS接收机定位异常，但在道路搜索状态下需结合下一个定位点信息通过再次搜索进行判断；PDOP<6、0

(2) 对(1)中的路线进行区域再次筛选，以定位点为圆心、半径为GPS实时水平的HPE值的二倍，可进一步缩小待匹配路段范围，直接确定车辆具体所处路段，将相关筛选结果信息保存至指定的结构数组中。若直线数量为m=0，则车辆在该定位点所处的圆域中，若不待匹配路段存在，则继续道路搜索；若m=1，则该路段可作为车辆目前行驶的道路，道路搜索结束。

(3) 当定位点周围的道路集中且密度大时，则需展开第三次筛选，有效筛选余下的待匹配路段，需使用精确度较高的筛选方法，在m-speed<8的情况下，GPS接收机给出的方向可信度不高，需根据实际行驶速度进行二次筛选，具体处理方法为：0

筛选结束后选择范围仅包括某一线段的道路，即作为该车辆的行驶道路，并传输至“正常行驶”的匹配过程。若经过多次道路搜索后仍未完成最优匹配路线的确定，则最终定位结果以原始的定位数据为准，无需误差校正[6]。

3.3 道路转换

(1) 将正常行驶时存储的所有节点编号提出来，再将同该节点相关的所有道路信息通过使用GPS导航中的拓扑关系提取出来，若只有1条道路相连，则该节点只对车辆刚途径的路段进行显示，无后续路段，不符合地图匹配的假设条件，需重新进行道路搜索。

(2) 若与该节点连接道路大于1条，则需将车辆刚途径的道路信息从所提取的道路信息中删除，此时剩余道路为1条则代表其属于下一匹配的路段，结束道路转换；如果此时剩余道路大于1条则需进行第二次筛选，处理过程同道路搜索的第三次筛选相同，在计算和处理各候选道路权重时，只需适当提高角度权值系数，在此基础上完成最优匹配道路的确定并保存，向正常行驶匹配阶段转换[7]。

4 总结

随着GPS导航定位系统和电子狗的普及应用，GPS数据量随之逐渐增加，海量数据的地图匹配亟待解决，处理的关键在于具备较高的计算效率及匹配精度，以满足数据实时性匹配需求。地图匹配的发展趋势呈现出多种匹配算法的融合，高级的地图匹配算法比较复杂、精准度较高，适合复杂的道路，以当前的交通拥堵状况为依据并综合多种因素得出最优路线，本文在对物流行业需求进行分析的基础上，完成了物流车辆运输定位监控系统的设计，详细阐述了地图匹配算法及流程，并介绍了物流运输导航的最短路径算法，实现了地图匹配算法，使物流车辆运输定位监控能力得以显著提升，对海量数据的处理速度及匹配精度的进一步提高将是下一步研究的重点。