汽车导航引擎技术的研究与实现
|
摘要
汽车导航引擎,应实现地图显示、路径规划、语音引导和兴趣点检索等功能,导航引擎的优劣直接决定整个导航产品性能的好坏。国内汽车导航系统多基于二次平台开发,通常只能利用二次平台提供的接口或功能,极大影响了开发的自主性和引擎功能的完善性。针对以上局限性,本文采用独立开发模式实现引擎模块的核心部分,设计出的导航引擎结构及功能更加合理和完善。
针对道路状况和行车规则的复杂性,本文采用交叉口模型描述实际交叉路口,根据节点—路段关系,建立基于层次网格索引的路网数据模型。在此基础上,设计出基于新引擎构架的地图文件格式,加快了地图数据的读取速度。
地图显示速度直接影响用户体验,针对嵌入式设备资源有限,地图显示较慢等问题,论文提出将地图数据分为背景数据、道路数据和兴趣点数据等部分,并对其分层分块建索引,不同比例尺地图对应不同地图数据格式文件,能快速定位到所需的数据。同时,对显示要素划分等级,每次只显示当前比例尺下的对应级别要素,减少了数据冗余,加快了地图显示速度,增强了用户体验。
路径规划是汽车导航的核心问题。实际导航中,交通转向限制和交叉口延误等,会造成规划结果的不准确。对此,本文采用对偶图思想建立转向限制关系表来表达转向限制关系,能更好地配合实际路径规划。针对导航仪规划速度慢等问题,采用结合分层策略的双向启发式融合算法,同时从起点和终点进行搜索,并对A~*算法结构和节点扩展方式加以改进。系统运行结果表明,采用此算法,大大减少了参与计算的路段数量,节省了存储空间,提高了路径规划的效率。
论文最后以武汉市区某范围内的路网数据为研究对象,对论文主要工作进行实证研究和测试。理论分析和实际运行结果表明,本文所做的主要工作有效地克服了当前导航引擎开发中的不足,极大地提高了地图显示速度,并能在交通转向限制情况下提供有效的路径规划。
Automobile navigation engine, should realize the functions such as map display, route plan, voice guidance and retrievals of points of interest and so on, the quality of navigation engine directly determines the whole performance of navigation products. The development of domestic automobile navigation system is mostly based on the second platform, only those interfaces or functions belong to the second platform can be used, this has played a great role on the autonomy of the development and improvement of engine functions. In response to this limitation, this paper suggested realize the core functions of engine through independent development mode. The structure and functions designed by this way tend to be more reasonable and perfect.
Considering the complexities of road conditions and traffic rules, this paper used cross road model to describe the actual crossing intersections, established the road network data model according to node-link relation based on multilayer grid index. The format of map files designed on the basis of new engine framework mentioned above, has greatly improved the speed of map data reading.
The speed of map display influences the user experience directly, in view of problems, like limited resources of embedded devices and slow speed of map display, this paper suggested divide the whole map data into background data, road data and data of points of interest, and construct indexes according to its hierarchical block, so maps of different scales match along with different map data files, by this we can quickly locate the data needed. At the same time, divided the geographical elements into different levels, only displayed the corresponding class elements in light of the current scale, this reduced data redundancy, speeded up the speed of the map display, enhanced user experience.
Route plan is the core issue of antomobile navigation. In actual navigation, traffic restrictions of turns and the delays at the intersections will make the result of route plan inaccurate or even wrong. This paper expressed the traffic redirection restrictions by establishing the table of redirection restrictions with the dual-graph, could match the actual route plan better. In view of the slow speed of navigation instruments, adopted bi-directional heuristic search algorithm with the combination of layered strategy, search from the start and the end at the same time respectively, and improved the structure of A algorithm and the method to expand node. The results of actual runs showed that using this algorithm, could greatly reduce the number of sections involved in the path calculation, save storage space and raise the efficiency of route plan.
Finally, this paper used certain part of Wuhan urban road network data as the study object and maked empirical research and testing for major work. Theoretical analysis and the actual operating results showed that the major work this paper had done overcomed the insufficiency during current development process of navigation engine, thus greatly enhanced the speed of map display, and provided effective route plan under the circumstances of traffic redirection restrictions.
针对道路状况和行车规则的复杂性,本文采用交叉口模型描述实际交叉路口,根据节点—路段关系,建立基于层次网格索引的路网数据模型。在此基础上,设计出基于新引擎构架的地图文件格式,加快了地图数据的读取速度。
地图显示速度直接影响用户体验,针对嵌入式设备资源有限,地图显示较慢等问题,论文提出将地图数据分为背景数据、道路数据和兴趣点数据等部分,并对其分层分块建索引,不同比例尺地图对应不同地图数据格式文件,能快速定位到所需的数据。同时,对显示要素划分等级,每次只显示当前比例尺下的对应级别要素,减少了数据冗余,加快了地图显示速度,增强了用户体验。
路径规划是汽车导航的核心问题。实际导航中,交通转向限制和交叉口延误等,会造成规划结果的不准确。对此,本文采用对偶图思想建立转向限制关系表来表达转向限制关系,能更好地配合实际路径规划。针对导航仪规划速度慢等问题,采用结合分层策略的双向启发式融合算法,同时从起点和终点进行搜索,并对A~*算法结构和节点扩展方式加以改进。系统运行结果表明,采用此算法,大大减少了参与计算的路段数量,节省了存储空间,提高了路径规划的效率。
论文最后以武汉市区某范围内的路网数据为研究对象,对论文主要工作进行实证研究和测试。理论分析和实际运行结果表明,本文所做的主要工作有效地克服了当前导航引擎开发中的不足,极大地提高了地图显示速度,并能在交通转向限制情况下提供有效的路径规划。
Automobile navigation engine, should realize the functions such as map display, route plan, voice guidance and retrievals of points of interest and so on, the quality of navigation engine directly determines the whole performance of navigation products. The development of domestic automobile navigation system is mostly based on the second platform, only those interfaces or functions belong to the second platform can be used, this has played a great role on the autonomy of the development and improvement of engine functions. In response to this limitation, this paper suggested realize the core functions of engine through independent development mode. The structure and functions designed by this way tend to be more reasonable and perfect.
Considering the complexities of road conditions and traffic rules, this paper used cross road model to describe the actual crossing intersections, established the road network data model according to node-link relation based on multilayer grid index. The format of map files designed on the basis of new engine framework mentioned above, has greatly improved the speed of map data reading.
The speed of map display influences the user experience directly, in view of problems, like limited resources of embedded devices and slow speed of map display, this paper suggested divide the whole map data into background data, road data and data of points of interest, and construct indexes according to its hierarchical block, so maps of different scales match along with different map data files, by this we can quickly locate the data needed. At the same time, divided the geographical elements into different levels, only displayed the corresponding class elements in light of the current scale, this reduced data redundancy, speeded up the speed of the map display, enhanced user experience.
Route plan is the core issue of antomobile navigation. In actual navigation, traffic restrictions of turns and the delays at the intersections will make the result of route plan inaccurate or even wrong. This paper expressed the traffic redirection restrictions by establishing the table of redirection restrictions with the dual-graph, could match the actual route plan better. In view of the slow speed of navigation instruments, adopted bi-directional heuristic search algorithm with the combination of layered strategy, search from the start and the end at the same time respectively, and improved the structure of A algorithm and the method to expand node. The results of actual runs showed that using this algorithm, could greatly reduce the number of sections involved in the path calculation, save storage space and raise the efficiency of route plan.
Finally, this paper used certain part of Wuhan urban road network data as the study object and maked empirical research and testing for major work. Theoretical analysis and the actual operating results showed that the major work this paper had done overcomed the insufficiency during current development process of navigation engine, thus greatly enhanced the speed of map display, and provided effective route plan under the circumstances of traffic redirection restrictions.
引文
[1]张国伍,彭宏勤.智能交通系统工程导论[M].北京:电子工业出版社,2003.7-9
[2]赵亦林.车辆定位与导航系统[M].北京:电子工业出版社,1999.1-7
[3]W.Y.Ochieng,K Saner.Urban road transport navigation:performance of the global position system after selective availability.Transportation Research Part C10.2002,171-187
[4]Harvey J.Miller and Shih-Lung Shaw.Geographic Information Systems for TransportationPrinciples and Applications Z.Oxford University Press,Inc,2001
[5]中国车载导航市场发展趋势.http://bbs.yuntom.com/viewthread.php?tid=225
[6]李清泉,李必军,李锦辉.汽车导航技术的现状与发展趋势.测绘工程,2005,14(4)
[7]唐克双,姚恩建.日本ITS开发和运用的实例—名古屋基于浮动车信息的P-DRGS简介.城市交通,2006,4(3):74-76
[8]世界GPS汽车导航系统现状.http://www.szchehang.com/zt/gps/js2.asp
[9]杨殿阁,卜健,郑四发,李克强,连小珉.车载导航系统的研究与实现.汽车技术,2005,(1):1-4
[10]罗朝丞.车辆自导航应用软件设计:[硕士学位论文].北京:中国地质大学计算机应用技术专业,2006
[11]曹晓航.GPS车载导航系统技术趋势浅析.现代测绘,2006.29(1):14-16.
[12]金丽华,杨根兴.嵌入式车载导航系统的研究与实现.电脑开发与应用,2005,19(4):36-37
[13]汽车导航电子地图及其引擎.http://www.zhuoyaxin.com/ProFile/Info_48.htm.
[14]刘春,史文中,刘大杰.导航电子地图中道路数据的空间索引和组织.工程勘查,2003,(1):38-41
[15]吴立新等.关于空间数据与空间数据模型的思考[J].地理信息世界,2005,3(2):41-46
[16]刘春,姚连璧.车载导航电子地图中道路数据的空间逻辑描述.同济大学学报,2002,30(3):346-351
[17]Version 3.0—95,European committee for standardization:Geographic data files(GDF)S
[18]USGS,National Mapping Division.Spatial data transfer standard(SDTS)—Part 1:Logical specifications M.New York:American National Standards Institute(ANSI),1995
[19]ZHANGDong,LIU Ailong,ZHANG De.The present situation of vehicle navigation techniques in china and the multi-topological information and route computing of national navigation map[C].ⅩⅫ International Cartographic Conference(ICC2005).Spain:Global Congresos,2005
[20]ArcPad:Mobile Mapping and Gis[A],An ESRI White Paper,2000[C]
[21]Fang T-P,Piegl L A.Delaunay Triangulation Using a Uniform Grid IEEE Comp.Graph.Appl 36-47
[22]梁中,孙小燕,谭勇桂.空间索引技术—回顾与展望.计算机工程与应用,2002,(24):197-199
[23]周勇.改进的层次网格空间索引技术研究与实现:[硕士学位论文].福州:福州大学应用数学专业,2004
[24]Timpf S,Frank U.A Multi-scale Data Structure Cartographic Objects[A.Proceedings of 17th CA/ACI international cartographic conference[C].1037-1044
[25]舒忠玲,汪林林,王佐成.利用层次网格索引提高WebGIS性能.计算机应用,2004,24(9):150-152
[26]刘新贵,孙群,黄雅鹃等.实现电子地图快速显示的策略和方法[J].测绘通报,2004,(1):54-55
[27]高博.车辆导航系统中数据处理、地图匹配和路径规划的研究:[硕士学位论文].郑州:解放军信息工程大学地图制图学与地理信息工程专业,2001
[28]王亚文.智能交通系统中路径规划算法研究与系统设计:[硕士学位论文].两安:陕西师范大学计算机应用技术专业,2007
[29]Solka L,Perry C,Pocllinger R.Fast computation of optimal paths using a parallel Dijkstra algorithm with embedded constraints.Neurocomputing,1995,(8):195-212
[30]VLIET D V.Improved Shortest Path Algorithms for Transport Networks[J].Transportation Research,1977,(12):7-20
[31]Fleischman R N,Thelen L A,Dennard D.A preliminary account of TravTek route guidance used by rental and local drivers[A].1993 Vehicle Navigation and Information Systems Conference[C].Published by IEEE,1993
[32]陈涛.车辆导航系统中大区域路径规划算法的设计与实现:[硕士学位论文].郑州:解放军信息工程大学地图制图学与地理信息工程专业,2005
[33]郑年波,李清泉,徐敬海,宋莺.基于转向限制和延误的双向启发式最短路径算法.武汉大学学报·信息科学版,2006,31(3):257-258
[34]韩刚,蒋捷等.车载导航系统中顾及道路转向限制的弧段Dijkstra算法.测绘学报,2002,31(4):366-368
[35]郭建科,张仁平等.Dijkstra改进算法及其在地理信息系统中的应用.计算机系统应用,2007,(1):59-62
[36]夏永锋,曹元大.启发式搜索算法的面向对象设计实现.微机发展,2005,15(7):11-13
[37]王敏,高太平,刘桂枝,刘宏英.交叉立方体网络上的一种双向搜索路由算法.计算机工程与应用,2007,43(35):123-125
[38]王丰元,潘福全等.基于交通限制的路网最优路径算法.交通运输工程学报,2005,5(1):92-95
[39]Deuker Kenneth J,Allison BJ.GIS-Tenterprise data model with suggested implementation choices R.s.1.:Center for Urban Studies,Portland State University,1997
[40]Hadzilacos T,Tryfona N.Logical data modeling for geographic databases J.Journal of Geographical Information Science,1996,(3):212-232
[41]RAVINDA K.AHUJA.Faster Algorithms for the Shortest Path Problem.Journal of the Association for Computing Machinery 1990,37(2):12-27
[42]包渊秋,严凌.面向交通规划的交叉口延误函数的研究和应用.上海理工大学学报,2005,27(3):253-258
[43]段莉琼,雷大伟.车辆自导航系统中加入道路转向限制的最短路径算法.海洋测绘,2003,23(5):12-15
[44]Zhan F B.Noon C E.A Comparison Between Label-Setting and Label-Correcting Algorithms For Computing One-to-One Shortest Paths[J].Journal of Geographic Information and Decision Analysis
[45]Zhan F B.Three Fastest Shortest Path Algorithms on Real Road Networks:Data Structures and Procedures[J].Journal of Geographic Information and Decision Analysis,1997,1(1):69-82
[2]赵亦林.车辆定位与导航系统[M].北京:电子工业出版社,1999.1-7
[3]W.Y.Ochieng,K Saner.Urban road transport navigation:performance of the global position system after selective availability.Transportation Research Part C10.2002,171-187
[4]Harvey J.Miller and Shih-Lung Shaw.Geographic Information Systems for TransportationPrinciples and Applications Z.Oxford University Press,Inc,2001
[5]中国车载导航市场发展趋势.http://bbs.yuntom.com/viewthread.php?tid=225
[6]李清泉,李必军,李锦辉.汽车导航技术的现状与发展趋势.测绘工程,2005,14(4)
[7]唐克双,姚恩建.日本ITS开发和运用的实例—名古屋基于浮动车信息的P-DRGS简介.城市交通,2006,4(3):74-76
[8]世界GPS汽车导航系统现状.http://www.szchehang.com/zt/gps/js2.asp
[9]杨殿阁,卜健,郑四发,李克强,连小珉.车载导航系统的研究与实现.汽车技术,2005,(1):1-4
[10]罗朝丞.车辆自导航应用软件设计:[硕士学位论文].北京:中国地质大学计算机应用技术专业,2006
[11]曹晓航.GPS车载导航系统技术趋势浅析.现代测绘,2006.29(1):14-16.
[12]金丽华,杨根兴.嵌入式车载导航系统的研究与实现.电脑开发与应用,2005,19(4):36-37
[13]汽车导航电子地图及其引擎.http://www.zhuoyaxin.com/ProFile/Info_48.htm.
[14]刘春,史文中,刘大杰.导航电子地图中道路数据的空间索引和组织.工程勘查,2003,(1):38-41
[15]吴立新等.关于空间数据与空间数据模型的思考[J].地理信息世界,2005,3(2):41-46
[16]刘春,姚连璧.车载导航电子地图中道路数据的空间逻辑描述.同济大学学报,2002,30(3):346-351
[17]Version 3.0—95,European committee for standardization:Geographic data files(GDF)S
[18]USGS,National Mapping Division.Spatial data transfer standard(SDTS)—Part 1:Logical specifications M.New York:American National Standards Institute(ANSI),1995
[19]ZHANGDong,LIU Ailong,ZHANG De.The present situation of vehicle navigation techniques in china and the multi-topological information and route computing of national navigation map[C].ⅩⅫ International Cartographic Conference(ICC2005).Spain:Global Congresos,2005
[20]ArcPad:Mobile Mapping and Gis[A],An ESRI White Paper,2000[C]
[21]Fang T-P,Piegl L A.Delaunay Triangulation Using a Uniform Grid IEEE Comp.Graph.Appl 36-47
[22]梁中,孙小燕,谭勇桂.空间索引技术—回顾与展望.计算机工程与应用,2002,(24):197-199
[23]周勇.改进的层次网格空间索引技术研究与实现:[硕士学位论文].福州:福州大学应用数学专业,2004
[24]Timpf S,Frank U.A Multi-scale Data Structure Cartographic Objects[A.Proceedings of 17th CA/ACI international cartographic conference[C].1037-1044
[25]舒忠玲,汪林林,王佐成.利用层次网格索引提高WebGIS性能.计算机应用,2004,24(9):150-152
[26]刘新贵,孙群,黄雅鹃等.实现电子地图快速显示的策略和方法[J].测绘通报,2004,(1):54-55
[27]高博.车辆导航系统中数据处理、地图匹配和路径规划的研究:[硕士学位论文].郑州:解放军信息工程大学地图制图学与地理信息工程专业,2001
[28]王亚文.智能交通系统中路径规划算法研究与系统设计:[硕士学位论文].两安:陕西师范大学计算机应用技术专业,2007
[29]Solka L,Perry C,Pocllinger R.Fast computation of optimal paths using a parallel Dijkstra algorithm with embedded constraints.Neurocomputing,1995,(8):195-212
[30]VLIET D V.Improved Shortest Path Algorithms for Transport Networks[J].Transportation Research,1977,(12):7-20
[31]Fleischman R N,Thelen L A,Dennard D.A preliminary account of TravTek route guidance used by rental and local drivers[A].1993 Vehicle Navigation and Information Systems Conference[C].Published by IEEE,1993
[32]陈涛.车辆导航系统中大区域路径规划算法的设计与实现:[硕士学位论文].郑州:解放军信息工程大学地图制图学与地理信息工程专业,2005
[33]郑年波,李清泉,徐敬海,宋莺.基于转向限制和延误的双向启发式最短路径算法.武汉大学学报·信息科学版,2006,31(3):257-258
[34]韩刚,蒋捷等.车载导航系统中顾及道路转向限制的弧段Dijkstra算法.测绘学报,2002,31(4):366-368
[35]郭建科,张仁平等.Dijkstra改进算法及其在地理信息系统中的应用.计算机系统应用,2007,(1):59-62
[36]夏永锋,曹元大.启发式搜索算法的面向对象设计实现.微机发展,2005,15(7):11-13
[37]王敏,高太平,刘桂枝,刘宏英.交叉立方体网络上的一种双向搜索路由算法.计算机工程与应用,2007,43(35):123-125
[38]王丰元,潘福全等.基于交通限制的路网最优路径算法.交通运输工程学报,2005,5(1):92-95
[39]Deuker Kenneth J,Allison BJ.GIS-Tenterprise data model with suggested implementation choices R.s.1.:Center for Urban Studies,Portland State University,1997
[40]Hadzilacos T,Tryfona N.Logical data modeling for geographic databases J.Journal of Geographical Information Science,1996,(3):212-232
[41]RAVINDA K.AHUJA.Faster Algorithms for the Shortest Path Problem.Journal of the Association for Computing Machinery 1990,37(2):12-27
[42]包渊秋,严凌.面向交通规划的交叉口延误函数的研究和应用.上海理工大学学报,2005,27(3):253-258
[43]段莉琼,雷大伟.车辆自导航系统中加入道路转向限制的最短路径算法.海洋测绘,2003,23(5):12-15
[44]Zhan F B.Noon C E.A Comparison Between Label-Setting and Label-Correcting Algorithms For Computing One-to-One Shortest Paths[J].Journal of Geographic Information and Decision Analysis
[45]Zhan F B.Three Fastest Shortest Path Algorithms on Real Road Networks:Data Structures and Procedures[J].Journal of Geographic Information and Decision Analysis,1997,1(1):69-82