基于嵌入式电子地图的导航路径规划研究
|
摘要
交通是国民经济发展的重要支柱。长期以来,交通问题已成为困扰城市发展的重要问题,尤其当驾驶者进入一个陌生的城市时,引导驾驶者走上正确的道路,及时准确地到达目的地就变得很重要。随着科技的飞速发展,计算机技术、网络技术和通讯技术已逐步渗入到交通领域,智能交通系统(ITS,Intelligent Transportation System)正是在这种情况下提出来的。交通地理信息系统在ITS中占有举足轻重的作用,已成为地理信息系统(GIS,Geographic Information System)的一个重要研究方向。车辆导航系统是一种典型的交通地理信息系统,具有极大的市场前景和发展潜力,其中的路径规划模块作为整个导航系统的核心模块之一,在嵌入式设备里运行,与在PC(Personal Computer)机上操作相比,要求路径规划时间更短和数据存储空间足够小,这就对路径规划算法设计在时间和空间上提出了新的要求。
本文的研究主要涉及嵌入式开发(主要是软件开发)、测绘学中的地理信息系统原理、数据组织方法、数字地图可视化、最佳路径规划等技术。
本文在分析电子地图的数据构成和模型的基础上,从MapInfo格式的桌面电子地图的MIF文件中提取出所需的电子地图数据。以图论作为理论基础来分析道路网络,在比较了图的几种经典存储结构后,结合C++标准模板库(STL,Standard Template Library)提出了一种高效的道路网络数据组织方式。并以出行距离作为路阻权值,在分析、比较几种经典的最短路径算法的基础上,结合交通路网特有的特征,对启发式A~*算法在数据存储、搜索策略等方面进行了改进。在程序实现上,采用C++语言,数据初始化部分和算法实现部分分别在两个类:CwayPoint类和CAStar类中实现,减小了它们之间的耦合性,真正体现了大型软件编程的模块化思想。实现了基于嵌入式电子地图导航的基本功能:电子地图的放大、缩小、漫游、兴趣点简单查询、路径寻优等。最后,在我们建立的嵌入式开发环境下,验证了实现的电子地图和算法的可行性。
本文的研究以linux操作系统和Qt/Embedded作为开发平台,充分利用了免费的资源,与现有的大部分以WINCE操作系统和EVC(Embedded Visual C++)为平台的导航系统相比,大大节省了开发成本。
The traffic is an important pillar of national economy development. For a long time, the traffic problem has already become an important problem which troubled urban development. Especially when driving into an unfamiliar city, guiding motorists on the right path and reaching their destinations becomes very important. Along with the rapid development of science and technology, computer technology, internet technology and communication technology have infiltrated into traffic field gradually. ITS(Intelligent transportation system) is proposed precisely in this context. Traffic geographic information system play a pivotal role in ITS, and has become an important research direction of GIS(Geographic Information System). Vehicle navigation system is a typical example of Traffic geographic information system, has great market prospect and development potentiality. The path planning module, as a core module among whole navigation system, compared with operating on Personal Computer, running in embedded devices requires shorter time and datas storage space small enough, that result in new demands for path planning algorithm's design in time and space.
The paper mainly involved embedded development (mainly software development), geographic information system of topography, datas organization method, digital map visualization, best path planning technology etc.
On the basis of analyzing the data forming and model of electronic map, the paper extracted necessary datas from MIF files of MapInfo format electronic map, analyzed the road network based on graph theory. After comparing several kinds of classic storage structure of graph, combined STL(Standard Template Library) effectively, puted forward a datas organization method of road network. And used distance as road resistance weight, on the basis of analyzing and comparing several classical shortest path algorithm, combined specific characteristic of traffic network, improved heuristic A~* algorithm in data storage, search strategies etc. Adopted C++ language in program implementation aspect, data initialization and algorithm was implemented in two different class respectively: CwayPoint class and CAStar class, reduced coupling of them, reflected the modular idea of large software programming really. Came ture the basic functions of embedded navigation electronic map: zoom out, zoom in, roaming, inquiry of interested points, route planning etc. Finally, gave the expected experiment results under the embedded development environment that we set up.
The research of this paper used linux and Qt/Embedded as developing platform, taked advantage of free resources fully. Comparing with most existing navigation system which use WINCE operating system and EVC(Embedded Visual C++) as platform, saved cost of development greatly.
本文的研究主要涉及嵌入式开发(主要是软件开发)、测绘学中的地理信息系统原理、数据组织方法、数字地图可视化、最佳路径规划等技术。
本文在分析电子地图的数据构成和模型的基础上,从MapInfo格式的桌面电子地图的MIF文件中提取出所需的电子地图数据。以图论作为理论基础来分析道路网络,在比较了图的几种经典存储结构后,结合C++标准模板库(STL,Standard Template Library)提出了一种高效的道路网络数据组织方式。并以出行距离作为路阻权值,在分析、比较几种经典的最短路径算法的基础上,结合交通路网特有的特征,对启发式A~*算法在数据存储、搜索策略等方面进行了改进。在程序实现上,采用C++语言,数据初始化部分和算法实现部分分别在两个类:CwayPoint类和CAStar类中实现,减小了它们之间的耦合性,真正体现了大型软件编程的模块化思想。实现了基于嵌入式电子地图导航的基本功能:电子地图的放大、缩小、漫游、兴趣点简单查询、路径寻优等。最后,在我们建立的嵌入式开发环境下,验证了实现的电子地图和算法的可行性。
本文的研究以linux操作系统和Qt/Embedded作为开发平台,充分利用了免费的资源,与现有的大部分以WINCE操作系统和EVC(Embedded Visual C++)为平台的导航系统相比,大大节省了开发成本。
The traffic is an important pillar of national economy development. For a long time, the traffic problem has already become an important problem which troubled urban development. Especially when driving into an unfamiliar city, guiding motorists on the right path and reaching their destinations becomes very important. Along with the rapid development of science and technology, computer technology, internet technology and communication technology have infiltrated into traffic field gradually. ITS(Intelligent transportation system) is proposed precisely in this context. Traffic geographic information system play a pivotal role in ITS, and has become an important research direction of GIS(Geographic Information System). Vehicle navigation system is a typical example of Traffic geographic information system, has great market prospect and development potentiality. The path planning module, as a core module among whole navigation system, compared with operating on Personal Computer, running in embedded devices requires shorter time and datas storage space small enough, that result in new demands for path planning algorithm's design in time and space.
The paper mainly involved embedded development (mainly software development), geographic information system of topography, datas organization method, digital map visualization, best path planning technology etc.
On the basis of analyzing the data forming and model of electronic map, the paper extracted necessary datas from MIF files of MapInfo format electronic map, analyzed the road network based on graph theory. After comparing several kinds of classic storage structure of graph, combined STL(Standard Template Library) effectively, puted forward a datas organization method of road network. And used distance as road resistance weight, on the basis of analyzing and comparing several classical shortest path algorithm, combined specific characteristic of traffic network, improved heuristic A~* algorithm in data storage, search strategies etc. Adopted C++ language in program implementation aspect, data initialization and algorithm was implemented in two different class respectively: CwayPoint class and CAStar class, reduced coupling of them, reflected the modular idea of large software programming really. Came ture the basic functions of embedded navigation electronic map: zoom out, zoom in, roaming, inquiry of interested points, route planning etc. Finally, gave the expected experiment results under the embedded development environment that we set up.
The research of this paper used linux and Qt/Embedded as developing platform, taked advantage of free resources fully. Comparing with most existing navigation system which use WINCE operating system and EVC(Embedded Visual C++) as platform, saved cost of development greatly.
引文
[1]夏金锋.自主车辆导航系统最优路径规划算法应用研究[D].大连:大连海事大学硕士学位论文,2005.
[2]史其信.中国智能交通系统发展框架构想[OL].http://www.tworker.cn/Article/brain/article/guihua/3424.htm,2007-05-06
[3]匿名.智能交通系统的发展与思考[OL].http://www.cdjt.gov.cn/moban/moban.asp?ID=156,2006-08-14.
[4]慈炳坤.车辆自主导航系统数字电子地图的研究[D].大连:大连理工大学硕士学位论文,2000.
[5]林世究.基于GPS/GIS技术车辆监控管理系统的研究与设计[D].武汉:武汉理工大学硕士学位论文,2002.
[6]金砺.面向21世纪的嵌入式计算机系统及应用[J].太原师范学院学报(自然科学版),2004,3(2):46-49.
[7]匿名.智能交通中的嵌入式系统[OL].http://www.21chinaits.com/html/news_disp.asp?xwlbid=5&xw_id=3614,2005.
[8]匿名.电子地图--导航时代的移动风向标[OL].http://net.chinabyte.com/113/3164113.shtml,2007-04-10.
[9]匿名.中国电子地图导航产业发展面临的主要问题[OL].http://www.szght.com/news_list.asp?id=675,2007.
[10]李卫国.基于数据转换的嵌入式电子地图开发的研究[D].武汉:华中科技大学硕士学位论文,2003.
[11]汪亚雷,余春暄.基于嵌入式Linux的MapInfo格式地图显示[J].微计算机信息,2006,22(10-2):184-186.
[12]卢珺.基于GIS的路径规划系统研究[D].大连:大连理工大学硕士学位论文,2005.
[13]成洁,吕遵明,敖雪.基于嵌入式Linux的嵌入式GIS的设计与实现[J].电子工程师,2006,32(11):69-71.
[14]甘浩.车辆定位导航系统的最优路径规划技术研究[D].武汉:武汉理工大学硕士学位论文,2005.
[15]鲍文东,邵周岳,邹杰.土地利用矢量数据交换文件VCT和Mapinfo数据格式的转换研究与实现[J].山东农业大学学报(自然科学版),2007,38(1):103-110.
[16]费立凡.MapInfo基础教程[M].北京:测绘出版社,2005.
[17]Troy,NY.The MapInfo Interchange File(MIF)Format Specification[S].MapInfo Corporation,1999.
[18]张为舟.嵌入式电子地图开发方法的研究[D].武汉:华中师范大学硕士学位论文,2006.
[19]田劲松.GIS数据质量控制与数据转换研究[D].合肥:合肥工业大学硕士学位论文,2006.
[20]王轩.地理信息共享的数据转换技术与方法的研究[D].郑州:中国人民解放军信息工程大学硕士学位论文,2004.
[21]王炜.道路交通工程系统分析方法[M].北京:人民交通出版社,2003.
[22]徐俊明.图论及其应用[M].合肥:中国科学技术大学出版社,2004.
[23]孙健鹤.城市道路网络最短路径的统计学特征及实用算法研究[D].上海:华东师范大学硕士学位论文,2006.
[24]段莉琼.基于城市交通网络的路径分析与应用[D].郑州:中国人民解放军信息工程大学硕士学位论文,2004.
[25]耿国华.数据结构--C语言描述[M].西安:西安电子科技大学出版社,2002.
[26]Nicolai M.Josuttis.The C++ Standard Library[M].Addison Wesley Longman Inc,1999.
[27]武雪玲.基于STL的车辆导航系统中路径规划算法的设计与实验[D].武汉:武汉大学硕士学位论文,2005.
[28]潘福全.车辆诱导系统中路径优化的研究[D].青岛:青岛理工大学硕士学位论文,2004.
[29]winter.C++STL中用vector改进内存的再分配[OL].http://stl.winterxy.com/html/000067.html,2005.
[30]张雪燕.嵌入式车载GIS导航系统的设计与实现[D].杭州:浙江大学硕士学位论文,2005.
[31]宋善德,李卫国,熊展志.电子地图袖珍化的研究[J].计算机工程与科学,2003,25(2):83-94.
[32]龚义建,庄园.一种嵌入式电子地图开发方法的研究[J].计算机与数字工程,2005, 33(8):72-74.
[33]王爱文.Linux平台下基于Qt的电子海图的研究与实现[D].哈尔滨:哈尔滨工程大学硕士学位论文,2004.
[34]赵海龙,杨伟民.基于嵌入式设备的GIS系统的设计与实现[J].上海理工大学学报,2004,26(2):184-188.
[35](美)Arthur Griffith.KDE 2/Qt编程宝典[M].高寿福,译.北京:电子工业出版社,2002.
[36]Trolltech.Qt参考文档[OL].http://www.qiliang.net/qt/index.html,2002.
[37]陈建春.Visual C++开发GIS系统[M].北京:电子工业出版社,2004.
[38]于明俭.Qt国际化编程[OL].http://linux.chinaunix.net/doc/program/2005-01-18/813.shtml,2005.
[39](美)Robert Sedgewick.C++算法(第3版)--图算法[M].林琪,译.北京:清华大学出版社,2003.
[40]张文轩.路径搜索的最优策略研究[D].北京:北京科技大学硕士学位论文,2005.
[41]汪诗峰.空间网络分析关键技术研究[D].北京:中国科学院遥感应用研究所硕士学位论文,2006.
[42]陈刚,付少锋,周利华.A~*算法在游戏地图寻径中的几种改进策略研究[J].科学技术与工程,2007,7(15):3731-3736.
[43]刘名龙.城市交通动态路径诱导算法研究及系统设计[D].昆明:昆明理工大学硕士学位论文,2005.
[44]陈晓红.交通网络动态路径诱导算法研究及其在GIS环境下的仿真实现[D].长沙:长沙理工大学硕士学位论文,2005.
[45]杨天石,刘晓东,于小平.城市道路最短路径算法的研究[J].长春工程学院学报,2006,7(2):57-59.
[46]韩刚.车载导航系统路径规划与数据组织研究[D].北京:北京理工大学硕士学位论文,2002.
[47]邵峰,黄贤武.嵌入式系统中电子地图的路径寻优[J].现代电子技术,2006,12:51-55.
[48]张海涛,程荫杭.基于A~*算法的全局路径搜索[J].微计算机信息,2007,23(6-2):238-239.
[49]王宗原.基于电子地图的路径规划的设计与实现[D].哈尔滨:哈尔滨工程大学硕士学 位论文,2005.
[50](美)Stephen Prata.C++ Primer Plus(第五版)中文版[M].孙建春,韦强,译.北京:人民邮电出版社,2005.
[51]武雪玲,杜清运,任福.基于 A~*算法的路网数据组织[J].地理空间信息,2006,4(6):11-13.
[52]刘翠丽.路径规划技术在导游软件中的应用[D].北京:北京交通大学硕士学位论文,2005.
[53]L.Fu,D.Sun,L.R.Rilett.Heuristic shortest path algorithms for transportation application:State of the art[J].Computers & Operations Research,2006,33:3324-3343.
[54]Karim Yagbmour.构建嵌入式Linux系统[M].O'Reilly Taiwan公司,译.韩存兵,龚波,改编.北京:中国电力出版社,2004.
[55]UP-NEYARM2410-S嵌入式系统试验指导书[M].北京:北京博创兴业科技有限公司,2006.
[2]史其信.中国智能交通系统发展框架构想[OL].http://www.tworker.cn/Article/brain/article/guihua/3424.htm,2007-05-06
[3]匿名.智能交通系统的发展与思考[OL].http://www.cdjt.gov.cn/moban/moban.asp?ID=156,2006-08-14.
[4]慈炳坤.车辆自主导航系统数字电子地图的研究[D].大连:大连理工大学硕士学位论文,2000.
[5]林世究.基于GPS/GIS技术车辆监控管理系统的研究与设计[D].武汉:武汉理工大学硕士学位论文,2002.
[6]金砺.面向21世纪的嵌入式计算机系统及应用[J].太原师范学院学报(自然科学版),2004,3(2):46-49.
[7]匿名.智能交通中的嵌入式系统[OL].http://www.21chinaits.com/html/news_disp.asp?xwlbid=5&xw_id=3614,2005.
[8]匿名.电子地图--导航时代的移动风向标[OL].http://net.chinabyte.com/113/3164113.shtml,2007-04-10.
[9]匿名.中国电子地图导航产业发展面临的主要问题[OL].http://www.szght.com/news_list.asp?id=675,2007.
[10]李卫国.基于数据转换的嵌入式电子地图开发的研究[D].武汉:华中科技大学硕士学位论文,2003.
[11]汪亚雷,余春暄.基于嵌入式Linux的MapInfo格式地图显示[J].微计算机信息,2006,22(10-2):184-186.
[12]卢珺.基于GIS的路径规划系统研究[D].大连:大连理工大学硕士学位论文,2005.
[13]成洁,吕遵明,敖雪.基于嵌入式Linux的嵌入式GIS的设计与实现[J].电子工程师,2006,32(11):69-71.
[14]甘浩.车辆定位导航系统的最优路径规划技术研究[D].武汉:武汉理工大学硕士学位论文,2005.
[15]鲍文东,邵周岳,邹杰.土地利用矢量数据交换文件VCT和Mapinfo数据格式的转换研究与实现[J].山东农业大学学报(自然科学版),2007,38(1):103-110.
[16]费立凡.MapInfo基础教程[M].北京:测绘出版社,2005.
[17]Troy,NY.The MapInfo Interchange File(MIF)Format Specification[S].MapInfo Corporation,1999.
[18]张为舟.嵌入式电子地图开发方法的研究[D].武汉:华中师范大学硕士学位论文,2006.
[19]田劲松.GIS数据质量控制与数据转换研究[D].合肥:合肥工业大学硕士学位论文,2006.
[20]王轩.地理信息共享的数据转换技术与方法的研究[D].郑州:中国人民解放军信息工程大学硕士学位论文,2004.
[21]王炜.道路交通工程系统分析方法[M].北京:人民交通出版社,2003.
[22]徐俊明.图论及其应用[M].合肥:中国科学技术大学出版社,2004.
[23]孙健鹤.城市道路网络最短路径的统计学特征及实用算法研究[D].上海:华东师范大学硕士学位论文,2006.
[24]段莉琼.基于城市交通网络的路径分析与应用[D].郑州:中国人民解放军信息工程大学硕士学位论文,2004.
[25]耿国华.数据结构--C语言描述[M].西安:西安电子科技大学出版社,2002.
[26]Nicolai M.Josuttis.The C++ Standard Library[M].Addison Wesley Longman Inc,1999.
[27]武雪玲.基于STL的车辆导航系统中路径规划算法的设计与实验[D].武汉:武汉大学硕士学位论文,2005.
[28]潘福全.车辆诱导系统中路径优化的研究[D].青岛:青岛理工大学硕士学位论文,2004.
[29]winter.C++STL中用vector改进内存的再分配[OL].http://stl.winterxy.com/html/000067.html,2005.
[30]张雪燕.嵌入式车载GIS导航系统的设计与实现[D].杭州:浙江大学硕士学位论文,2005.
[31]宋善德,李卫国,熊展志.电子地图袖珍化的研究[J].计算机工程与科学,2003,25(2):83-94.
[32]龚义建,庄园.一种嵌入式电子地图开发方法的研究[J].计算机与数字工程,2005, 33(8):72-74.
[33]王爱文.Linux平台下基于Qt的电子海图的研究与实现[D].哈尔滨:哈尔滨工程大学硕士学位论文,2004.
[34]赵海龙,杨伟民.基于嵌入式设备的GIS系统的设计与实现[J].上海理工大学学报,2004,26(2):184-188.
[35](美)Arthur Griffith.KDE 2/Qt编程宝典[M].高寿福,译.北京:电子工业出版社,2002.
[36]Trolltech.Qt参考文档[OL].http://www.qiliang.net/qt/index.html,2002.
[37]陈建春.Visual C++开发GIS系统[M].北京:电子工业出版社,2004.
[38]于明俭.Qt国际化编程[OL].http://linux.chinaunix.net/doc/program/2005-01-18/813.shtml,2005.
[39](美)Robert Sedgewick.C++算法(第3版)--图算法[M].林琪,译.北京:清华大学出版社,2003.
[40]张文轩.路径搜索的最优策略研究[D].北京:北京科技大学硕士学位论文,2005.
[41]汪诗峰.空间网络分析关键技术研究[D].北京:中国科学院遥感应用研究所硕士学位论文,2006.
[42]陈刚,付少锋,周利华.A~*算法在游戏地图寻径中的几种改进策略研究[J].科学技术与工程,2007,7(15):3731-3736.
[43]刘名龙.城市交通动态路径诱导算法研究及系统设计[D].昆明:昆明理工大学硕士学位论文,2005.
[44]陈晓红.交通网络动态路径诱导算法研究及其在GIS环境下的仿真实现[D].长沙:长沙理工大学硕士学位论文,2005.
[45]杨天石,刘晓东,于小平.城市道路最短路径算法的研究[J].长春工程学院学报,2006,7(2):57-59.
[46]韩刚.车载导航系统路径规划与数据组织研究[D].北京:北京理工大学硕士学位论文,2002.
[47]邵峰,黄贤武.嵌入式系统中电子地图的路径寻优[J].现代电子技术,2006,12:51-55.
[48]张海涛,程荫杭.基于A~*算法的全局路径搜索[J].微计算机信息,2007,23(6-2):238-239.
[49]王宗原.基于电子地图的路径规划的设计与实现[D].哈尔滨:哈尔滨工程大学硕士学 位论文,2005.
[50](美)Stephen Prata.C++ Primer Plus(第五版)中文版[M].孙建春,韦强,译.北京:人民邮电出版社,2005.
[51]武雪玲,杜清运,任福.基于 A~*算法的路网数据组织[J].地理空间信息,2006,4(6):11-13.
[52]刘翠丽.路径规划技术在导游软件中的应用[D].北京:北京交通大学硕士学位论文,2005.
[53]L.Fu,D.Sun,L.R.Rilett.Heuristic shortest path algorithms for transportation application:State of the art[J].Computers & Operations Research,2006,33:3324-3343.
[54]Karim Yagbmour.构建嵌入式Linux系统[M].O'Reilly Taiwan公司,译.韩存兵,龚波,改编.北京:中国电力出版社,2004.
[55]UP-NEYARM2410-S嵌入式系统试验指导书[M].北京:北京博创兴业科技有限公司,2006.