自从二十世纪60年代世界上第一个地理信息系统诞生以来,地理信息系统(GIS)在各行各业得到广泛的应用。近几年,嵌入式技术快速发展,给地理信息系统的应用提供了一个新的领域。把嵌入式技术与GIS、导航定位融合在一起,是当前GIS发展的一个重要研究方向。嵌入式GIS导航的应用领域相当广泛,如国防军事、车载导航、智能交通等,极大方便了人们的生活。因此,这种基于嵌入式GIS的导航系统的研究与开发具有重要的经济意义和社会意义。本论文首先介绍了国内外嵌入式GIS导航的研究现状、发展趋势、应用领域。接着讨论研究嵌入式GIS导航的相关技术和理论,包括嵌入式系统、地理信息系统、导航定位技术和电子地图,在此基础上对基于嵌入式GIS的导航系统进行研究与设计。主要是对系统进行了整体功能和接口设计,并对其中的模块,GPS数据采集与处理、导航定位和地图匹配进行了详细设计。接下来,针对嵌入式系统的特点,对地理信息系统的空间数据处理,如建立空间数据模型和数据结构,以及数据存储等进行了讨论,分析采用各种技术的利弊和本系统的选择。本文的重点工作是路径规划系统,包括最短路径算法讨论,分别对三种常用最短路径算法Dijkstra算法、A*算法和遗传算法进行了优化,对Dijkstra算法实行直线优化、对A*实行OPEN表的二叉堆排序优化,提出对遗传算法实行种群初始化方向优化原则等。对三种优化算法进行比较后,决定本系统采用优化之后的A*算法。接下来,设计路径规划所需的拓扑数据结构,并对拓扑关系的提取进行了讨论。最后,对A*算法在所建立的拓扑数据结构上进行了实现。