汽车导航系统

汽车导航系统摘要：汽车GPS导航系统是以全球24颗定位人造卫星为基础，向全球各地全天候地提供三维位置、三维速度等信息的一种无线电导航定位系统。它由三部分构成，一是地面控制部分，由主控站、地面天线、滥测站及通讯辅助系统组成。二是空间部分，由24颗卫星组成，分布在6个轨道平面。三是用户装置部分，由GPS接收机和卫星天线组成。现在民用的定位精度可达10米内。本文根据采用图论求两个定点之间的最短路径，其中应用Dijkstra算法（双标号法），即对图中的点v进行标号，分别记录v到v之间的最短路径和v到v最短路径上前一邻点的下标用来标识路径，从而可以由终点到起点进行反向追踪，最终找到最短路径。然后根据网路标记出最短路径发送给用户，从而问题得以解决。关键词：GPS导航，图论，最短路径，Dijkstia算法，综合分析，迭代。一：问题重述随着经济和社会的高速发展，时间变得越来越宝贵，在这个越发忙碌的生活里，交通变得让人越来越头痛，人类迫切的想找到这样一种设备来掌握自己的时间，于是导航仪便应用而生，其内置的GPS天线会接收到来自环绕地球的24颗GPS卫星中的至少3颗所传递的数据信息，结合储存在车载导航仪内的电子地图，通过GPS卫星信号确定的位置坐标与此相匹配，进行确定汽车在电子地图中的准确位置，这就是平常所说的定位功能。在定位的基础上，可以通过多功能显视器，提供最佳行车路线，前方路况以及最近的加油站、饭店、旅馆等信息。假如不幸GPS信号中断，你因此而迷了路，也不用担心，GPS已记录了你的行车路线，你还可以按原路返回。当然，这些功能都离不开已经事先编制好的使用地区的地图软件。二：模型假设（一）假设所经过路线的交通情况和拥挤情况一致（二）所走路线车速都相同（三）把车辆与交通路口当作有向图的顶点，忽略质量与形状。三：符号说明iV顶点的标号sV起点的标号()iPV起点sV到iV的最短路径iiV前面一个邻点的下标I标号的点的集合J没标号的点的集合A弧集空集ijwiV到jV路径的权ijT顶点到jV最小弧四：模型建立与求解步骤1：给拐点进行编号iV，即有向图的顶点。步骤2：点sV标号（0，s）,表示从1V到1V的距离为0，sV为起点。步骤3找出已标号的点的集合I，没标号的点的集合J,求出弧集{(,)|,}ijijAvvvIvJ,这个弧集是指所有从已标号的点到未标号的点的集合。步骤4，如果上述弧集A，表明从所有已经赋予标号的顶点出发，不再有这样的弧，它的另一顶点尚未标号，则计算结束。对于已标号的顶点，可求得从1V到达这个顶点的最短路，对于没标号的顶点，则不存在从1V到达这个顶点的路。如果弧集A，转步骤5。步骤5，对弧集A中的每一条弧(,)ijvv，计算()ijiijTPVw在所有的中，找到其值为最小的弧，假设为(,)stvv。需要注意的是，若上述ijT值为最小的弧有多条，且这些弧的第二个顶点jvv相同，则表明存在多条最优路径，因此，jv应得到多个双标号。最后，给弧(,)stvv终点tv赋予双标号((),)tPVs。返回步骤3。经上述一个循环的计算，将求出1V到一个顶点jv的最短路及长度，从而使一个顶点jv得到双标号。若图中总共有n个顶点，故最多计算1n个循环，即可得到最后结果。求解过程如下，取定顶点和边以后，便可进行计算得到：给定起点1v的标号(0,)s，则表示从1v到1v的距离1()0Pv，1v为起点。则开始时标号的集合1{}Iv，没标号的点的集合234567891011121314{,,,,,,,,,,,,}Jvvvvvvvvvvvvv，弧集1214{(,)|,}{(,),(,)}ijijAvvvIvJvvvv12112()01600TPvw14114()01800TPvw121412min{,}min{1600,1800}1600TTT米给弧12(,)vv的终点2v以双标号(1600,1)。这样我们就把距离1v最短路径求出。下面按照图的最短路径方法继续求得第二部为：12{,}Ivv;34567891011121314{,,,,,,,,,,,}Jvvvvvvvvvvvv;142326{(,)|,}{(,),(,),(,)}ijijAvvvIvJvvvvvv则所求得的弧为：14114()018001800TPvw；23223()160016003200TPvw；26226()160042005800TPvw；14232614min{,,}min{1800,3200,5800}1800TTTT;给弧14(,)vv的终点4v以标号为(1800,1)。按照上述类型，我们利用迭代的方法，最终可以得到我们所需要的最短路径。五：模型优缺点分析本文所建立的模型主要有以下优点：本文利用图论知识求的最短路径，及任意一段也是最短路，采用树生长的过程来求指定顶点到其余顶点的最短路径，综合分析可以知道Dijkstra算法，利用迭代法倒推出那套我们所需的路径，这种方法简明易了，可以迅速求出最短路径。本文主要有以下缺点：模型假设中是假定路面状况都一致，故每条路线只需考虑距离就行，但实际上这是不对的，路面状况和交通状况，再加上车速，我们需要正确对待这些客观因素。所以该模型可以在时间最短的基础上来改善模型。参考文献：(1)赵静，但琦，《数学建模与数学实验》，高等教育出版社，2002。（2）吴清烈，尤海燕，《运筹学》，南京，东南大学出版社，2004.附件：最短路线.jpg