, 王国仁东北大学 信息科学与工程学院，辽宁 沈阳 110819
收稿日期：2015-12-07
基金项目：国家自然科学基金资助项目 (61332006, 61370154);中央高校基本科研业务费专项资金资助项目 (N140404009)。
作者简介：吴刚 (1978-)，男，辽宁沈阳人，东北大学副教授;
王国仁 (1966-)，男，辽宁沈阳人，东北大学教授, 博士生导师。
摘要：综合采用隐马尔可夫模型 (HMM) 和遗传算法，提出了一种新的地图匹配算法.首先初始化HMM概率矩阵，然后使用前向后向算法进行参数学习，用Viterbi算法预测一组路段序列，最后将路段序列作为种群，通过遗传算法得到最优的路段序列.采用北京市2012年出租车GPS定位数据分别对传统的基于隐马尔可夫模型的算法和新算法进行测试，实验结果表明，传统的基于隐马尔可夫模型的算法的匹配精确度低于90%，新算法的匹配精确度高达90%以上.
关键词：地图匹配隐马尔可夫模型遗传算法匹配精确度路网数据
Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm
WU Gang, QIU Yu-jing
, WANG Guo-renSchool of Information Science & Engineering, Northeastern University, Shenyang 110819, China
Corresponding author: QIU Yu-jing, E-mail: 724734215@qq.com
Abstract: A new map matching algorithm was proposed on the basis of the hidden Markov model and the genetic algorithm. Firstly, the HMM probability matrix was initialized. Then, the parameters were learned by using the forward-backward algorithm, and a set of road sections was predicted by using the Viterbi algorithm. Finally, taking section sequence as population, the optimal section sequence was obtained by using the genetic algorithm. By using the taxi GPS data from Beijing in 2012 to test the traditional algorithm based on hidden Markov model and the proposed algorithm, the results showed that the traditional algorithm based on hidden Markov model has a matching accuracy below 90% and the proposed algorithm has a matching accuracy above 90%.
Key Words: map matchinghidden Markov modelgenetic algorithmmatching accuracyroad network data
随着车载导航系统的应用越来越广泛，人们对导航系统的定位精确度提出了更高的要求.由于存在多种不可避免的影响因素，利用全球定位系统 (global positioning system，GPS) 技术进行车辆定位的方法存在较大误差.因此，需要将GPS定位技术和电子地图信息融合来提高车辆的定位精确度.然而，目前已有的基于车辆历史轨迹信息的地图匹配算法存在着匹配精度低[1]、匹配效率差[2]等缺点，因此研究低复杂度、低成本、高精度、高效率的地图匹配算法具有重要的现实意义.
地图匹配技术[3]是一种定位纠错技术，其基本思想是结合车辆的定位轨迹和电子地图中的路网信息，将GPS定位的车辆信息与电子地图数据按照一定的逻辑进行比较和匹配，找到车辆所在路段，根据一定的方法计算出车辆在路段上的准确位置，将车辆定位的点投影到路段上，从而矫正定位误差，提高车辆定位的精度.
本文设计了一种将隐马尔可夫模型 (hidden Markov model, HMM) 和遗传算法 (genetic algorithm) 相结合的新型地图匹配算法，即HMM-genetic (HG) 地图匹配算法.该算法包括4个主要过程：初始化HMM概率矩阵 (状态转移矩阵、观察概率矩阵、初始状态矩阵)；参数学习；寻找一组匹配度较高的路段序列；最后把这组路段序列作为种群，通过遗传算法寻找最优的路段序列.实验结果表明，新算法在基于车辆历史轨迹的地图匹配问题上的匹配精确度高达90%以上.
1 HG地图匹配算法本文首先参考了Newson等[4]提出的地图匹配算法，使用传统的HMM模型编写地图匹配算法，得出的实验结果显示匹配精确度不高，预测出来的最优路径序列存在较大的偏差，而遗传算法可以对已有的结果进行优化，所以本文使用HMM算法得到一组概率较大的路径序列，然后使用遗传算法对这组路径序列进行优化，得到最优路径序列.
1.1 初始化HMM概率矩阵观察概率矩阵的初始化[5]：观察概率矩阵是观察值在某个状态下的近似值.对于地图匹配算法来说，给定一个定位点zt, t=1, 2, 3…，该定位点zt对于每个路段ri, i=1, 2, 3…，会有一个似然概率p(zt|ri).这个概率表示假设车辆在该路段ri上能被观察到的概率.对于一个给定的定位点zt和路段ri，将路段上距离给定点最近的点记为xt, i，定位点和候选匹配点在地球表面上的距离表示为‖zt-xi, j‖greatcircle .可以将GPS噪音建模成一个零均值的高斯过程，那么，观察概率矩阵中元素初值的计算式为
 | (1) |
 | (2) |
状态转移概率矩阵的初始化[7]：每个定位点有一系列可能的匹配路段.状态转移概率矩阵给出了车辆在候选匹配路段之间转移的概率.对于一个定位点zt和候选路段ri，在该路段上离定位点最近的点是xt, i.对于下一个定位点zt+1和候选路段rj，对应的点是xt+1, j.行驶距离记为‖xt, i－xt+1, j‖route，两个测量点间地球表面上的距离记为‖zt-zt+1‖greatcircle，见图 1.正确匹配的地球表面距离和行驶距离的绝对值的差值满足
图 1(Fig. 1)
 | 图 1 行驶距离和地球表面距离示意图Fig.1 Schematic diagram of route distance and great circle distance on surface of the earth |
 | (3) |
 | (4) |
 | (5) |
1.3 预测路段序列用Viterbi算法[10]对输入的测试数据预测出一组路段序列.Viterbi算法的原理是：如果最优路径在时刻t通过结点vt，那么这一路径从节点vt到终点vT的部分路径对于从vt到vT的所有可能的部分路径来说，必须是最优的.
考虑到以上情况，本文在此不直接得到最优路径，而是利用Viterbi算法找出一组候选路径序列，然后使用遗传算法继续寻找最优路径.
1.4 利用遗传算法优化路径由于隐马尔可夫模型的分值计算方法的差异会影响序列预测结果，所以采用遗传算法[11]来解决这一问题.本文采用遗传算法对预测出的路径组进行处理[12]，从而得到与真实路径更匹配的路径.
本算法中的基因编码是路段的标号，用适度函数评估基因.车辆行驶往往会寻找一条最短的路径，所以本文采取的适度函数是以路段序列的距离的可信度与路段序列在HMM参数系统下的概率为基准，即f(x)=w1×Droute+w2×Proute.其中：Droute指所选路段序列的距离的可信度，此可信度是以车辆行驶起点和终点在路网上的最短路径R为期望的高斯分布上的概率值；Proute指所选序列在HMM参数系统下的概率值；w1，w2是Droute和Proute的权重.经过多次实验，当w1=0.5，w2=0.12时，算法匹配精确度最高.
进化过程主要包含两个步骤:一个是交叉；另一个是突变.本算法中的交叉采用遗传算法中的部分交叉.首先从种群中随机选取两个基因序列作为母基因，分别从两个母基因中抽选出一段基因序列进行交换产生两个子基因，然后根据适度函数对母基因和子基因进行估值.若子基因中的估值较高者比母基因中的估值较低者高，则上述子基因替换上述母基因；若子基因的估值比母基因都低，则种群不变.本算法中的突变采用的是位突变，首先随机选取一个基因序列，随机挑选出序列中的一位，将该位数据随机变更成路段范围中的其他数值.最后，根据适度函数挑选出种群中适度值最大的序列.
2 实验2.1 仿真实验环境设计本实验采用了北京市六环以内的道路网络作为路网数据，选取北京市部分出租车在2012年1月到5月的GPS定位数据作为样本对本算法进行测试.
在测试前分别对路网数据和GPS定位点数据[13]进行了处理.路网数据以路段作为数据基本单元.每个路段主要包括路段的标识信息 (街道名称等) 及路段的拐点定位数据.
由于六环以内的路网数据非常庞大，寻找路网上的路段和拐点比较耗时，所以采用哈希技术对路网数据进行处理.首先根据经纬度范围将路网均等分成10行×10列的100块区域，再根据经纬度将每块区域等分成10行×10列的100块路段哈希块和拐点哈希块.读取每块区域里的路段，根据路段的经纬度放置相应的路段哈希块；再顺序读取路段中的拐点，根据经纬度及路段单双向属性保存同一路段拐点间的关系并放置到相应的拐点哈希块.
GPS定位点的处理使用如下方法：首先读取车辆轨迹的所有定位点，获取每一个定位点附近的路段集合，并计算每个路段到该定位点的最短距离；然后为了减少不合理候选路段，剔除最短距离比平均值大两倍标准差的路段.
2.2 实验结果本实验随机选择了几组GPS定位点数据，测试了它们的匹配效果.图 2是其中一组数据的匹配结果.从测试结果可以看出，经过算法处理，原本不在道路上的点，都能匹配到道路上.
图 2(Fig. 2)
 | 图 2 GPS定位点的匹配结果Fig.2 Map-matching results of GPS data (a)—匹配前；(b)—匹配后. |
2.3 实验结果对比本实验利用多组GPS定位点数据对只利用基于隐马尔可夫模型的地图匹配算法和结合后的新算法分别进行了测试，根据定位点匹配的路段与真实路段匹配比例分别计算了它们的匹配精确度，并进行了对比.表 1是利用真实数据匹配出的部分实验结果，表 2是改进前的算法和改进后的算法匹配精度对比，其中，020564.xls，083406.xls，211254.xls，431050.xls是包含GPS定位数据的四个Excel表，该数据主要包括采集时间、经度、纬度三个特征.
表 1(Table 1)
 表 1 改进前和改进后算法对同一组GPS定位点匹配后的经纬度对比Table 1 Comparison of GPS data of same set before and after improved algorithm
| 表 1 改进前和改进后算法对同一组GPS定位点匹配后的经纬度对比 Table 1 Comparison of GPS data of same set before and after improved algorithm |
表 2(Table 2)
表 2 改进前和改进后的算法对四组GPS定位点的匹配精确度的对比Table 2 Comparison of GPS data of four groups before and after improving algorithm
| 表 2 改进前和改进后的算法对四组GPS定位点的匹配精确度的对比 Table 2 Comparison of GPS data of four groups before and after improving algorithm |
从上述实验结果可以发现，先使用基于隐马尔可夫模型的地图匹配算法对车辆历史轨迹进行匹配处理，再使用遗传算法进行改进，匹配精确度有所提高.
3 结语本文使用遗传算法对基于隐马尔科夫模型的地图匹配算法进行了改进.将隐马尔科夫模型预测出来的一组路径序列，利用遗传算法进一步优化，提高了地图匹配的匹配精确度.实验结果显示，本文提出的新算法在提高匹配精确度方面具有较好的效果.
参考文献
| [1] | Bernstein D, Kornhauser A. An introduction to map matching for personal navigation assistants[J].Geometric Distributions, 1998, 122(7): 1082–1083. |
| [2] | White C E, Bernstein D, Kornhauser A L. Some map matching algorithms for personal navigation assistants[J].Transportation Research Part C:Emerging Technologies, 2000, 8(1): 91–108. |
| [3] | Srivatsa M, Ganti R, Wang J, et al.Map matching:facts and myths[C]//ACM Sigspatial International Conference on Advances in Geographic Information Systems.Orlando, 2013:484-487. |
| [4] | Newson P, Krumm J.Hidden Markov map matching through noise and sparseness[C]//International Conference on Advances in Geographic Information Systems.New York:ACM, 2009:336-343. |
| [5] | Krumm J.A Markov model for driver turn prediction[C]//SAE 2008 World Congress.Detroit, 2008:1-25. |
| [6] | Szwed P, Pekala K.An incremental map matching algorithm based on hidden Markov model[C]//International Conference on Artificial Intelligence and Soft Computing.Zakopane, Poland, 2014:579-590. |
| [7] | Chen B Y, Yuan H, Li Q, et al. Map-matching algorithm for large-scale low-frequency floating car data[J].International Journal of Geographical Information Science, 2014, 28(1): 22–38.DOI:10.1080/13658816.2013.816427 |
| [8] | Gather U, Schultze V. Robust estimation of scale of an exponential distribution[J].Statistica Neerlandica, 1999, 53(3): 327–341.DOI:10.1111/stan.1999.53.issue-3 |
| [9] | Welch H, Lloyd R. Hidden Markov models and the Baum-Welch algorithm[J].IEEE Information Theory Society Newsletter, 2003, 53(2): 194–211. |
| [10] | Forney G D. The Viterbi algorithm[J].Proceedings of the IEEE, 2015, 61(5): 268–278. |
| [11] | Reeves C R, Rowe J E. Genetic algorithms principles and perspectives[J].Operations Research/Computer Science Interfaces, 2014, 20(2): 354–355. |
| [12] | Brakatsoulas S, Pfoser D, Salas R, et al.On map-matching vehicle tracking data[C]//International Conference on Very Large Data Bases.Trondheim, 2005:853-864. |
| [13] | Kubicka M, Cela A, Moulin P, et al.Dataset for testing and training of map-matching algorithms[C]//Intelligent Vehicles Symposium (Ⅳ).Barcelona, 2015:1088-1093. |
