基于隐马尔可夫模型和遗传算法的地图匹配算法

doi:10.12068/j.issn.1005-3026.2017.04.004

东北大学学报:自然科学版 ›› 2017, Vol. 38 ›› Issue (4): 472-475.DOI: 10.12068/j.issn.1005-3026.2017.04.004

基于隐马尔可夫模型和遗传算法的地图匹配算法

吴刚，邱煜晶，王国仁

(东北大学信息科学与工程学院，辽宁沈阳110819)

收稿日期:2015-12-07 修回日期:2015-12-07 出版日期:2017-04-15 发布日期:2017-04-11
通讯作者: 吴刚
作者简介:吴刚(1978-)，男，辽宁沈阳人，东北大学副教授；王国仁(1966-)，男，辽宁沈阳人，东北大学教授，博士生导师.
基金资助:
国家自然科学基金资助项目(61332006， 61370154); 中央高校基本科研业务费专项资金资助项目(N140404009).

Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm

WU Gang， QIU Yu-jing， WANG Guo-ren

School of Information Science & Engineering， Northeastern University， Shenyang 110819， China.

Received:2015-12-07 Revised:2015-12-07 Online:2017-04-15 Published:2017-04-11
Contact: QIU Yu-jing
About author:-
Supported by:
-

摘要/Abstract

摘要： 综合采用隐马尔可夫模型(HMM)和遗传算法，提出了一种新的地图匹配算法.首先初始化HMM概率矩阵，然后使用前向后向算法进行参数学习，用Viterbi算法预测一组路段序列，最后将路段序列作为种群，通过遗传算法得到最优的路段序列.采用北京市2012年出租车GPS定位数据分别对传统的基于隐马尔可夫模型的算法和新算法进行测试，实验结果表明，传统的基于隐马尔可夫模型的算法的匹配精确度低于90%，新算法的匹配精确度高达90%以上.

关键词: 地图匹配, 隐马尔可夫模型, 遗传算法, 匹配精确度, 路网数据

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 matching, hidden Markov model, genetic algorithm, matching accuracy, road network data

中图分类号:

TP399

吴刚，邱煜晶，王国仁. 基于隐马尔可夫模型和遗传算法的地图匹配算法[J]. 东北大学学报:自然科学版, 2017, 38(4): 472-475.

WU Gang， QIU Yu-jing， WANG Guo-ren. Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm[J]. Journal of Northeastern University Natural Science, 2017, 38(4): 472-475.

参考文献

[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.
[8]Gather U，Schultze V.Robust estimation of scale of an exponential distribution［J］.Statistica Neerlandica，1999，53(3):327-341.
[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 (IV).Barcelona，2015:1088-1093.

[1]	丁山，臧仕义，曹殿明，佘黎煌. 基于动态ID跳变的CAN总线安全调度算法[J]. 东北大学学报（自然科学版）, 2022, 43(3): 350-358.
[2]	叶翠丽，王娜，庞硕，闫航. 基于改进遗传算法的秸秆还田机刀片功耗优化[J]. 东北大学学报（自然科学版）, 2021, 42(9): 1290-1298.
[3]	丁山，暴林慧，高梦宁，佘黎煌. 一种基于安全性的CAN-FD信号打包方法[J]. 东北大学学报（自然科学版）, 2021, 42(6): 775-781.
[4]	刘军，杨青文，王金涛，刘华伟. 基于改进遗传算法的空间信息网恢复策略[J]. 东北大学学报（自然科学版）, 2021, 42(4): 524-530.
[5]	裴玉龙，杨世军，潘恒彦. 考虑车内拥挤状态的公交弹性发车间隔优化[J]. 东北大学学报（自然科学版）, 2021, 42(11): 1663-1672.
[6]	李壮年，储满生，柳政根，李宝峰. 基于机器学习和遗传算法的高炉参数预测与优化[J]. 东北大学学报:自然科学版, 2020, 41(9): 1262-1267.
[7]	黄川，胡平，连静. 一种基于车载信号还原机动车道3D地图的大数据方法[J]. 东北大学学报:自然科学版, 2020, 41(6): 771-777.
[8]	刘芳，刘欣怡，苏卫星，林辉. 电动汽车动力电池健康状态在线估算方法[J]. 东北大学学报:自然科学版, 2020, 41(4): 492-498.
[9]	王新刚，徐馷悉，李尚杰，马瑞敏. 不确定结构的区间可靠性优化设计[J]. 东北大学学报:自然科学版, 2020, 41(4): 521-527.
[10]	张华伟，郑晓涛. 基于遗传算法优化神经网络的拼焊板压边力预测[J]. 东北大学学报:自然科学版, 2020, 41(2): 241-245.
[11]	刘芳，马杰，苏卫星，何茂伟. 基于模型参数在线辨识技术的SOC估算方法[J]. 东北大学学报:自然科学版, 2020, 41(11): 1543-1549.
[12]	茹敬雨，贾子熙，吴成东. 一种基于阳光的运动轨迹简化算法[J]. 东北大学学报:自然科学版, 2019, 40(8): 1070-1075.
[13]	李海朋，李晶皎，金硕巍，杨丹. 多宇宙并行量子遗传神经网络人脸识别算法研究[J]. 东北大学学报:自然科学版, 2019, 40(5): 614-618.
[14]	翟莹莹，厉英，敖志广. 基于改进多目标遗传算法的连铸二冷过程优化[J]. 东北大学学报:自然科学版, 2019, 40(5): 658-662.
[15]	马小刚，陈良玉，李杨. 基于响应面法炉腹异型管铜冷却壁的长寿技术优化[J]. 东北大学学报:自然科学版, 2019, 40(5): 710-715.

基于隐马尔可夫模型和遗传算法的地图匹配算法

Map Matching Algorithm Based On Hidden Markov Model and Genetic Algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价