摘 要：针对路网拓扑结构的复杂和轨迹信息利用不充分问题，文章提出了一种改进的HMM，该方法考虑了真实路网的拓扑信息，轨迹的位置、方向和速度信息。在计算发射概率时用二维正态分布将轨迹的位置信息和方向信息融合，转移概率计算时考虑到候选道路的限制速度和距离的非线性关联，并在实验中得到验证，改进后的匹配成功率比传统HMM 提高了7%。
关键词：拓扑结构；HMM；观测概率；转移概率
中图分类号：TP301.6 文献标识码：A 文章编号：2096-4706（2020）21-0084-04
The Map Matching Algorithm Based on Improved HMM
ZHANG Hao ，LIU Daming
（School of Computer Science and Technology，Shanghai University of Electric Power，Shanghai 200090，China）
Abstract：In view of the complexity of road network topology and inadequate utilization of track information，an improved HMM method is proposed in this paper，which considers the topology information，track position，direction and velocity information of the real road network. In the calculation of the emission probability，the location information and direction information of the trajectory are fused together with the two-dimensional normal distribution. In the calculation of the transition probability，the nonlinear relation between the limit speed and distance of the candidate road is taken into account，which is verified in the experiment. The improved matching success rate is 7% higher than the traditional HMM.
Keywords：topology；HMM；observation probability；transition probability
参考文献：
[1] YUAN J，ZHENG Y，XIE X，et al. Driving with knowledgefrom the physical world [C]//Proceedings of the 17th ACM SIGKDDinternational conference on Knowledge discovery and data mining.NewYork：Association for Computing Machinery，2011：316-324.
[2] CHEN C，ZHANG D Q，CASTRO P S，et al. iBOAT：Isolation-based online anomalous trajectory detection [J].IEEE Transactionson Intelligent Transportation Systems，2013，14（2）：806-818.
[3] LI X L，HAN J W，LEE J G，et al. Traffic density-based discovery of hot routes in road networks [C]//Proceedings of the 10th international conference on Advances in spatial and temporal databases.Berlin：Springer-Verlag，2007：441-459.
[4] ZHENG Y，LIU Y C，YUAN J，et al. Urban Computing withTaxicabs [C]//Proceedings of the 13th ACM International Conferenceon Ubiquitous Computing.New York：Association for ComputingMachinery，2011：89-98.
[5] ZHANG J T. Smarter outlier detection and deeper understandingof large-scale taxi trip records：a case study of NYC [C]//Proceedings ofthe ACM SIGKDD International Workshop on Urban Computing.NewYork：Association for Computing Machinery，2012：157-162.
[6] QUDDUS M A，OCHIENG W Y，NOLAND R B. Currentmap-matching algorithms for transport applications：State-of-the art andfuture research directions [J].Transportation Research Part C：EmergingTechnologies，2007，15（5）：312-328.
[7] KIM S，KIM J H. Adaptive fuzzy-network-based C-measuremap-matching algorithm for car navigation system [J].IEEE Transactionson Industrial Electronics，2001，48（2）：432-441.
[8] 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-6）：91-108.
[9] PHUYAL A，BISHNU P. Adaptive trajectory segmentationmethod and its application in in-car navigation system [D].Ohio：TheOhio State University，2001.
[10] 张小国，王庆，万德钧. 基于路网拓扑特性及先验知识的地图匹配算法 [J]. 东南大学学报（自然科学版），2006（4）：625-629.
[11] 盛彩英，席唱白，钱天陆，等. 浮动车轨迹点地图匹配及插值算法 [J]. 测绘科学，2019，44（8）：106-112.
[12] QUDDUS M A，OCHIENG W Y，ZHAO L，et al. Ageneral map matching algorithm for transport telematics applications [J].GPS Solutions，2003，7（3）：157-167.
[13] HASHEMI M，KARIMI H A. A weight-based map-matchingalgorithm for vehicle navigation in complex urban networks [J].Journalof Intelligent Transportation Systems，2016，20（6）：573-590.
[14] 高文超，李国良，塔娜. 路网匹配算法综述 [J]. 软件学报，2018，29（2）：225-250.
[15] 田甜，吕芳，王秀玲. 一种基于浮动车优化地图匹配方法 [J]. 现代电子技术，2015，38（11）：159-162.
[16] LI H Q，WU G. Map Matching for Taxi GPS Data withExtreme Learning Machine [C]//International Conference on AdvancedData Mining and Applications，2014：447-460.
[17] XU H，LIU H C，TAN C W，et al. Development andApplication of an Enhanced Kalman Filter and Global PositioningSystem Error-Correction Approach for Improved Map-Matching [J].Journal of Intelligent Transportation Systems，2010，14（1）：27-36.
[18] SMAILI C，NAJJAR M E B E，CHARPILLET F. A HybridBayesian Framework for Map Matching：Formulation Using SwitchingKalman Filter [J].Journal of Intelligent & Robotic Systems，2014，74（3-4）：725-743.
[19] 王科，李鹏，金瑜，等. 基于三证据DS 理论的双模式地图匹配算法 [J]. 计算机工程，2018，44（5）：316-321.
[20] 曾嘉郦，孙立双，王晓明. 北京出租车GPS 轨迹数据地图匹配算法研究 [J]. 北京测绘，2019，33（3）：255-260.
作者简介：
张浩（1996—），男，汉族，安徽蚌埠人，硕士研究生，主要研究方向：轨迹预测、物联网技术、嵌入式系统开发；
刘大明（1971—），男，汉族，上海人，副教授，博士，主要研究方向：物联网技术、嵌入式系统与设计、智能工业机器人。