针对复杂道路网络的车辆轨迹地图匹配算法
|
摘要
针对高度城市化地区存在的复杂道路网络环境下,如何高效地进行车辆轨迹数据的地图匹配问题,该文提出了一种针对复杂道路网络的车辆轨迹数据地图匹配算法。该算法以车辆轨迹序列为匹配对象,通过环形轨迹的识别把车辆轨迹序列划分为无环路轨迹段,并用道路拓扑关系来计算轨迹序列的最优匹配路线,实现在复杂道路网络中的车辆轨迹数据地图匹配。为了验证本算法的性能,以上海市道路网络为实验区,以约1.3万辆出租车在2015年4月的轨迹数据为数据源,进行实证研究。实验结果显示,该文提出的地图匹配算法在复杂的道路网络中有较高的匹配成功率和匹配效率。
Aiming at the problem of how to make map-matching of vehicle trajectory data efficient in complex road network environment in highly urbanized area,this paper proposed a novel map-matching approach based on road topology to deal with massive vehicle trajectory data accurately and efficiently.This approach separated vehicle trajectory to loop-free trajectory segments and recognized its optimal matching route based on road topology.In order to evaluate the performance of the proposed method,a massive trajectory data set from about 13 thousand taxis in Shanghai in April,2015 was employed.The experimental results showed that the map matching algorithm proposed in this paper had higher matching success rate and matching efficiency in complex road networks.
Aiming at the problem of how to make map-matching of vehicle trajectory data efficient in complex road network environment in highly urbanized area,this paper proposed a novel map-matching approach based on road topology to deal with massive vehicle trajectory data accurately and efficiently.This approach separated vehicle trajectory to loop-free trajectory segments and recognized its optimal matching route based on road topology.In order to evaluate the performance of the proposed method,a massive trajectory data set from about 13 thousand taxis in Shanghai in April,2015 was employed.The experimental results showed that the map matching algorithm proposed in this paper had higher matching success rate and matching efficiency in complex road networks.
引文
[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,2000,8(1):91-108.
[3]XU T,LI X,CLARAMUNT C.Trip-oriented travel time prediction(TOTTP)with historical vehicle trajectories[J].Frontiers of Earth Science,2017(1):1-11.
[4]XU T,XU X,HU Y,et al.An entropy-based approach for evaluating travel time predictability based on vehicle trajectory data[J].Entropy,2017,19(4):165.
[5]任慧君,许涛,李响.利用车载GPS轨迹数据实现公交车驾驶安全性分析[J].武汉大学学报(信息科学版),2014,39(6):739-744.(REN Huijun,XU Tao,LI Xiang.Driving behavior analysis based on trajectory data collected with vehicle-mounted GPS receivers[J].Geomatics and Information Science of Wuhan University,2014,39(6):739-744.)
[6]李响,林珲,沈大勇.新一代协作式智能交通系统(CITS)初探[J].交通信息与安全,2004,22(4):6-9.(LI Xiang,LIN Hui,SHEN Dayong.A new generation of collaborative intelligent transportation system(CITS)[J].Journal of Transport Information and Safety,2004,22(4):6-9.)
[7]KRAKIWSKY E J,HARRIS C B,WONG R V C.A Kalman filter for integrating dead reckoning,map matching and GPS positioning[C]∥Proceedings of IEEE Symposium on Position Location and Navigation.[S.l.]:[s.n.],1988.
[8]SCOTT C A.Improved GPS positioning for motor vehicles through map matching[C]∥Proceedings of International Technical Meeting of the Satellite Division of the Institute of Navigation.[S.l.]:[s.n.],1994.
[9]QUDDUS M A.High integrity map matching algorithms for advanced transport telematics applications[D].London:Imperial College London,2006.
[10]BOUJU A,STOCKUS A,BERTRAND F,et al.Location-based spatial data management in navigation systems[C]∥IEEE Symposium on Intelligent Vehicle.[S.l.]:[s.n.],2002.
[11]LI X,LIN H,ZHAO Y.A connectivity-based map matching algorithm[J].Asian Journal of Geoinformatics,2005,5(3):69-76.
[12]LI X,ZHANG X,LIN H.Deriving network-constrained trajectories from sporadic tracking points collected in location-based services[J].Geo-spatial Information Science,2009,12(2):85-94.
[13]VELAGA N R,QUDDUS M A,BRISTOW A L.Developing an enhanced weight-based topological mapmatching algorithm for intelligent transport systems[J].Transportation Research Part C,2009,17(6):672-683.
[14]XU X,LI X,HU Y,et al.A novel algorithm to identifying vehicle travel path in elevated road area based on GPS trajectory data[J].Frontiers of Earth Science,2012,6(4):354-363.
[15]刘张,王心迪,闫小勇.面向复杂城市道路网络的GPS轨迹匹配算法[J].电子科技大学学报,2016,46(6):1008-1013.(LIU Zhang,WANG Xindi,YAN Xiaoyong.Map-matching algorithm for GPS trajectories in complex urban road networks[J].Journal of University of Electronic Science and Technology of China,2016,46(6):1008-1013.)
[16]KIM W,JEE G,LEE J.Efficient use of digital road map in various positioning for ITS[C]∥IEEE Symposium on Position Location and Navigation.SanDeigo:[s.n.],2000.
[17]QUDDUS M A,OCHIENG W Y,NOLAND R B.A high accuracy fuzzy logic-based map matching algorithm for road transport[J].Journal of Intelligent Transportation Systems,2006,10(3):103-115.
[18]GOH C Y,DAUWELS J,MITROVIC N,et al.Online map-matching based on hidden Markov model for realtime traffic sensing applications[C]∥Proceedings of15th International IEEE Conference on ITSC.Anchorage:[s.n.],2012.
[19]LOU Y,ZHANG C Y,ZHENG Y,et al.Map-matching for low-sampling-rate GPS trajectories[C]∥Proceedings of the 17th ACM SIGSPATIAL.Seattle,WA:ACM,2009:352-361.
[20]PYO J,SHIN D,SUNG T.Development of a map matching method using the multiple hypothesis technique[J/OL]∥Intelligent Transportation Systems,2001:23-27[2018-01-17].http:∥xueshu.baidu.com/s?wd=Development+of+a+map+matching+method+using+the+multiple+hypothesis+technique&tn=SE_baiduxueshu_c1gjeupa&cl=3&ie=utf-8&bs=Online+map-matching+based+on+hidden+markov+model+for+real-time+traffic+sensing+applications&f=8&rsv_bp=1&rsv_sug2=1&sc_f_para=sc_tasktype%3D%7BfirstSimpleSearch%7D.
[21]韩明锋,丁万庆,谢世杰.GPS误差概论[J].测绘通报,1999(5):1-6.(HAN Mingfeng,DING Wanqing,XIE Shijie.Introduction of GPS Error[J].Bulletin of Surveying and Mapping,1999(5):1-6.)
[2]WHITE C E,BERNSTEIN D,KORNHAUSER A L.Some map matching algorithms for personal navigation assistants[J].Transportation Research Part C,2000,8(1):91-108.
[3]XU T,LI X,CLARAMUNT C.Trip-oriented travel time prediction(TOTTP)with historical vehicle trajectories[J].Frontiers of Earth Science,2017(1):1-11.
[4]XU T,XU X,HU Y,et al.An entropy-based approach for evaluating travel time predictability based on vehicle trajectory data[J].Entropy,2017,19(4):165.
[5]任慧君,许涛,李响.利用车载GPS轨迹数据实现公交车驾驶安全性分析[J].武汉大学学报(信息科学版),2014,39(6):739-744.(REN Huijun,XU Tao,LI Xiang.Driving behavior analysis based on trajectory data collected with vehicle-mounted GPS receivers[J].Geomatics and Information Science of Wuhan University,2014,39(6):739-744.)
[6]李响,林珲,沈大勇.新一代协作式智能交通系统(CITS)初探[J].交通信息与安全,2004,22(4):6-9.(LI Xiang,LIN Hui,SHEN Dayong.A new generation of collaborative intelligent transportation system(CITS)[J].Journal of Transport Information and Safety,2004,22(4):6-9.)
[7]KRAKIWSKY E J,HARRIS C B,WONG R V C.A Kalman filter for integrating dead reckoning,map matching and GPS positioning[C]∥Proceedings of IEEE Symposium on Position Location and Navigation.[S.l.]:[s.n.],1988.
[8]SCOTT C A.Improved GPS positioning for motor vehicles through map matching[C]∥Proceedings of International Technical Meeting of the Satellite Division of the Institute of Navigation.[S.l.]:[s.n.],1994.
[9]QUDDUS M A.High integrity map matching algorithms for advanced transport telematics applications[D].London:Imperial College London,2006.
[10]BOUJU A,STOCKUS A,BERTRAND F,et al.Location-based spatial data management in navigation systems[C]∥IEEE Symposium on Intelligent Vehicle.[S.l.]:[s.n.],2002.
[11]LI X,LIN H,ZHAO Y.A connectivity-based map matching algorithm[J].Asian Journal of Geoinformatics,2005,5(3):69-76.
[12]LI X,ZHANG X,LIN H.Deriving network-constrained trajectories from sporadic tracking points collected in location-based services[J].Geo-spatial Information Science,2009,12(2):85-94.
[13]VELAGA N R,QUDDUS M A,BRISTOW A L.Developing an enhanced weight-based topological mapmatching algorithm for intelligent transport systems[J].Transportation Research Part C,2009,17(6):672-683.
[14]XU X,LI X,HU Y,et al.A novel algorithm to identifying vehicle travel path in elevated road area based on GPS trajectory data[J].Frontiers of Earth Science,2012,6(4):354-363.
[15]刘张,王心迪,闫小勇.面向复杂城市道路网络的GPS轨迹匹配算法[J].电子科技大学学报,2016,46(6):1008-1013.(LIU Zhang,WANG Xindi,YAN Xiaoyong.Map-matching algorithm for GPS trajectories in complex urban road networks[J].Journal of University of Electronic Science and Technology of China,2016,46(6):1008-1013.)
[16]KIM W,JEE G,LEE J.Efficient use of digital road map in various positioning for ITS[C]∥IEEE Symposium on Position Location and Navigation.SanDeigo:[s.n.],2000.
[17]QUDDUS M A,OCHIENG W Y,NOLAND R B.A high accuracy fuzzy logic-based map matching algorithm for road transport[J].Journal of Intelligent Transportation Systems,2006,10(3):103-115.
[18]GOH C Y,DAUWELS J,MITROVIC N,et al.Online map-matching based on hidden Markov model for realtime traffic sensing applications[C]∥Proceedings of15th International IEEE Conference on ITSC.Anchorage:[s.n.],2012.
[19]LOU Y,ZHANG C Y,ZHENG Y,et al.Map-matching for low-sampling-rate GPS trajectories[C]∥Proceedings of the 17th ACM SIGSPATIAL.Seattle,WA:ACM,2009:352-361.
[20]PYO J,SHIN D,SUNG T.Development of a map matching method using the multiple hypothesis technique[J/OL]∥Intelligent Transportation Systems,2001:23-27[2018-01-17].http:∥xueshu.baidu.com/s?wd=Development+of+a+map+matching+method+using+the+multiple+hypothesis+technique&tn=SE_baiduxueshu_c1gjeupa&cl=3&ie=utf-8&bs=Online+map-matching+based+on+hidden+markov+model+for+real-time+traffic+sensing+applications&f=8&rsv_bp=1&rsv_sug2=1&sc_f_para=sc_tasktype%3D%7BfirstSimpleSearch%7D.
[21]韩明锋,丁万庆,谢世杰.GPS误差概论[J].测绘通报,1999(5):1-6.(HAN Mingfeng,DING Wanqing,XIE Shijie.Introduction of GPS Error[J].Bulletin of Surveying and Mapping,1999(5):1-6.)