摘要
便携式GPS导航设备是集嵌入式技术、全球定位系统(GPS)、地理信息系统(GIS)、智能交通系统(ITS)、计算机科学技术、多媒体技术和现代通信技术于一体的高科技产品。本文针对便携式设备的特性,根据交通网络的特点和实际驾驶情况,在嵌入式环境中对导航设备中导航引擎的路径规划模块所涉及的关键技术进行了研究。其中,着重研究并改进了城市交通网络的导航电子地图分层技术、海量地理数据存储技术,采用符合交通规则的网络拓扑结构模型,从多个角度对最短路径算法进行联合优化,总结出运行更为高效的最优路径算法。通过在WinCE操作系统中,使用VC嵌入Mapinfo/MapX控件的方式对算法进行仿真发现;该算法能够减少数据冗余,高效的存储电子地图数据,有利于节省便携式产品的硬盘及内存空间,减少CPU的计算量;进一步减少了路径搜索时访问的节点数目,有效地提高了寻径速度;弥补了现有算法的不足之处,并得出一些有益的数据和结论。该算法现已使用在某软件公司的导航产品中。
Embedded Technology, Global Positioning System, Geographic Information System, Intelligence Traffic System, Computer Science Technology, Multimedia and Modern Communication Technology were applied to the high technology product—Portable Navigation Device. Aimming at the characteristics of portable device and according to the traffic network characters and practical applications, this thesis researched and analyzed the key technologies of route planning in navigation engine under embedded environment. Thereinto, putting the main emphases on researching and modifying the technology of city traffic network electronic route map, technology of great geography data storage and using a model of actual network topology structure, this thesis optimized the shortest path algorithm from some aspects, and then, summarized a more efficient algorithm. The algorithm is realized by VC pluged with Mapinfo/MapX control already under WinCE operation system. It is shown that this algorithm can reduce the data redundancy, store the electorical map data efficiently, which is fit for the hard disk and memory space requirements of protable device, and it can reduce the heavy computation of CPU and decrease the number of the possible visited nodes when searching route further, which can accelerate the searching speed; overcome a shortcoming in some previous algorithms, at last, we get some useful data and conclusion. The proposed optimal algorithm has been adopted in the navigation products of a software company.
引文
[1]严蔚敏,吴伟民.数据结构;C语言版.北京;清华大学出版社,1996.187～188
[2]徐业昌,李树祥,朱建民等.基于地理信息系统的最短路径搜索算法.中国图形图象学报,1998,3(1);39～43
[3]潘金贵,顾铁成,曾俭等编译.现代计算机常用数据结构和算法.南京;南京大学出版社,1994.92～124
[4]Cherkassky B.V.& Goldberg A.V.Shortest paths algorithms;theory and experimental evaluation,Mathematical Programming,1996,73,129～174
[5]程财,肖艳辉.GPS在公路工程中的应用.黑龙江交通科技,2007,9;104～105
[6]王广运.美国对GPS的SA和AS政策.测绘通报,2001,11;11
[7]陶春鸣,梅杨.基于GPS差分算法的研究与滑坡监测系统软件实现.河南科学,2007,25(5);797～799
[8]中国汽车新网.2004年汽车电子导航(GPS)市场研究报告.http;//www.qiche.com.cn/info/report show.php?id=87
[9]电子地图.百度百科.http;//baike.baidu.com/view/71120.htm
[10]孙厚科,董刚,李婷.现代地图——电子地图.青海师专学报(教育科学),2006,3;156
[11]Car A,Frank A.General Principles of Hierarchical Spatial Reasoning the Case of Wayfinding.In;Proceedings of the 6th International Symposium on Spatial Data Handing.Scotand;Edinburgh,1994,646～664
[12]Caldwell T.On Finding Minimum Routes in a Network with Turn Penalties.Communication of the ACM,1961,4(2);107～108
[13]EASA S M.Traffic assignment in practice;overview and guidelines for users.Journal of Transportation Engineering,1999,117(6);602～623
[14]对偶图.百度百科.http;//baike.baidu.com/view/599961.htm
[15]De La Barra T.Integrated land use and transport modeling.Cambridge;Cambridge Univ Press,1989,65～87
[16]段隆振,胡学钢主编.数据结构.武汉;武汉理工大学出版社,2003
[17]陆锋.最短路径算法;分类体系与研究进展.测绘学报,2001,30(3);269～274
[18]Sunway.初识A*算法.http;//dev.gameres.com/Program/Abstract/a8first.htm
[19]彭飞,柳重堪,张其善.车辆定位与导航系统中的快速路径规划算法.北京航空航天大学学报,2002,28(1);70～73
[20]吴尚智.改进的堆排序算法及其复杂度分析.西北师范大学学报(自然科学版),2002,38(3);24～26
[21]T.A.J.Nicholson.Finding the Shortest Route Between Two Points in a Network.The Computer Journal.1966,3;275～280
[22]李华贵,项志华,李玲等.电子地图在车辆导航定位系统中的应用.现代电子技术,2006,17;125～129
[23]侯俊杰.深入浅出MFC.武汉;华中科技大学出版社,2001
[24]严寒冰,刘迎春,崔伟宏.交通网络限制搜索区域时间最短路径算法.中国图形图象学报,1999,4(10);849～853
[25]聂运菊,赵吉先,费小睿.基于MapX的道路拓扑和最短路径分析的讨论与实现.测绘科学,2006,31(3);96～98
[26]张小国,王庆等.基于电子地图的路径最优算法研究.中国惯性技术学报,2001,9(1);45～48
[27]Anez J,De La Barra T,Perez B.Dual graph representation of transport networks.Transportation Research B,1996,30(3);209～216
[28]王凌,段江涛,王保保.GIS中最短路径的算法研究与仿真.计算机仿真,2005,22(1);117～120
[29]张贵明.GPS/GIS车辆导航系统中最佳路径算法研究.四川师范大学学报,2005,28(4);497～500
[30]苏永云,晏克非,黄翔等.车辆导航系统的动态最优路径搜索方法研究.系统工程,2000,18(4);32～37
[31]陈壁峰,陆昊娟,黄樟灿.车辆导航系统的动态最优路径搜索模型及算法.武汉理工大学学报信息与管理工程版,2002,24(3);46～48
[32]向怀坤,刘小明.车辆导航系统的研究开发现状与趋势.汽车工程,2001,23(5);296～318
[33]汤晓,李贻斌,王彦堂等.基于Mapinfo的最短路径混合搜索算法.山东理工大学学报.2006,20(2);82～84
[34]K.Mustafa,A.Mehmet,K.Faouzi.Neural Networks for Shortest Path Computation and Routing in Computer Network.IEEE Transaction on Neural Networks.1993,4(6);941 ～ 953
[35]吴成东,韩中华,张颖等.基于并行遗传神经网络算法的限制搜索区域最优路径方法.公路交通科技,2006,23(8);127～129
[36]唐文武,施晓东,朱大奎.GIS中使用改进的Dijkstra算法实现最短路径的计算.中国图形图象学报,2000,5(12);1021～1023
[37]J.E.Mccormack,J.Hogg.Virtual-memory Tiling for Spatial Data Handing in GIS.Computer&Geoscience.1997,23(4);659～669
[38]王文杰,叶世伟.人工智能原理与应用.北京;人民邮电出版社,2004
[39]陈军.GIS空间数据模型的基本问题和学术前沿.地理学报,1995,(50)增刊;24～33
[40]乐阳,龚健雅.Dijkstra最短路径算法的一种高效率实现.武汉测绘科技大学学报,1999,24(3);209～212
[41]鲍运慧,冯三强,徐敏.基于矢量地图的路径寻优算法.微电子学与计算机,1999,(5);10～13
[42]吴京,景宁,陈荦.空间查询和路径搜索的集成处理策略.软件学报,2000,11(2);265～270
[43]李强,黄莎白.GIS环境下的最佳路径规划.信息与控制,2000,29(1);76～81
[44]D.P.Bertseksa.A Simple and Fast Label Correcting Algorithm for Shortest Path.Networks.1993,23;703～709
[45]王学军,贾冰媛.地理信息系统.北京;中国环境科学出版社,1993
[46]宋关福,钟耳顺.组件式地理信息系统研究与开发.中国图象图形学报,1998,(4);313～317
[47]郑佳春.车载电子地图系统中的最佳路径搜索.集美大学学报自然科学版,2000,5(3);69～73
[48]许志海,张绍云.交通限制条件下的最短路径算法分析与优化.信息过程大学测绘学院学报,2005,22(1);62～64
[49]杨长保,王开义,马生忠.一种最短路径分析优化算法的实现.吉林大学学报,2002,20(2);70～74
[50]张渭军,王华.城市道路最短路径的Dijkstra算法优化.长安大学学报(自然科学版),2005,31(13);78～80
[51]张怡.复杂环境下车辆导航系统最优路径规划算法研究.弹箭与制导学报,2005,25(1);9～11
[52]浦争艳,李明禄,李治洪.复杂网络环境下一种面向对象的最优路径算法研究.计算机工程,2005,30(16);80～82
[53]宋延,石建军,许国华.适用于路径规划系统的动态路网描述模型.交通与计算机,2004,22(5);28～31
[54]韩刚,蒋捷,陈军.车载导航系统中顾及道路转向限制的Dijstra算法.测绘学报,2002,31(4);366～368
[55]西蒙著.嵌入式系统软件教程;第1版.陈向群等译.北京;机械工业出版社,2005
[56]汪兵,李存斌,陈鹏.EVC高级编程及其应用开发(Embedded Visual c++嵌入式编程).北京;水利水电出版社,2005
[57]Daivd J.Kruglinski,Scot Wingo etc.Visual c++6.0技术内幕.希望图书创作室译.北京;北京希望电子出版社,2002