曾志雄——基于GPS的最佳动态路径分析与仿真研究

序号： 编码： 第十一届“挑战杯”广东大学生课外学术科技作品竞赛作品申报书 作品名称： 基于GPS的最佳动态路径分析与仿真研究 学校全称： 华南农业大学 申报者姓名 （集体名称）：曾志雄 陈沛明 黄涵 吴月宜 黄灿培 类别： 自然科学类学术论文 哲学社会科学类社会调查报告和学术论文 科技发明制作A类 科技发明制作B类 说 明1申报者应在认真阅读此说明各项内容后按要求详细填写。2申报者在填写申报作品情况时只需根据个人项目或集体项目填写A1或A2表，根据作品类别（自然科学类学术论文、哲学社会科学类社会调查报告和学术论文、科技发明制作）分别填写B1、B2或B3表。所有申报者可根据情况填写C表。3表内项目填写时一律用钢笔或打印，字迹要端正、清楚，此申报书可复制。4序号、编码由第十一届“挑战杯”广东大学生课外学术科技作品竞赛组委会填写。5学术论文、社会调查报告及所附的有关材料必须是中文（若是外文，请附中文本），请以4号楷体打印在A4纸上（文章版面尺寸14.522cm），附于申报书后，论文不超8000字，调查报告不超15000字。6作品申报书须按要求由各校竞赛组织协调机构统一寄送。7其他参赛事宜请向本校竞赛组织协调机构咨询。A2申报者情况（集体项目）说明：1必须由申报者本人按要求填写；2申报者代表必须是作者中学历最高者，其余作者按学历高低排列；3本表中的学籍管理部门签章视为申报者情况的确认。申报者代表情况姓名曾志雄性别男出生年月1989年2月学校华南农业大学系别、专业、年级2008级交通运输（汽车运用工程）学历本科学制4年入学时间2008年9月作品名称基于GPS的最佳动态路径分析与仿真研究毕业论文题目无通讯地址广东省广州市天河区五山路483号华南农业大学华山区3栋218室邮政编码510642办公电住地通讯地址广东省广州市天河区五山路483号华南农业大学华山区3栋218室邮政编码510642住宅电他作者情况姓 名性别年龄学历所在单位陈沛明男21本科华南农业大学工程学黄涵男21本科华南农业大学信息学院吴月宜女21本科华南农业大学林学院黄灿培男21本科华南农业大学经济管理学院资格认定学校学籍管理部门意见以上作者是否为2011年7月1日前正式注册在校的全日制非成人教育、非在职的高等学校中国籍专科生、本科生、硕士研究生或博士研究生。是否 （部门签章）年 月 日院、系负责人或导师意见本作品是否为课外学术科技或社会实践活动成果。是否负责人签名：年 月 日B1申报作品情况（自然科学类学术论文）说明：1必须由申报者本人填写；2本部分中的科研管理部门签章视为对申报者所填内容的确认；3作品分类请按作品的学术方向或所涉及的主要学科领域填写；4硕士研究生、博士研究生作品不在此列。作品全称基于GPS的最佳动态路径分析与仿真研究作品分类（A） A机械与控制（包括机械、仪器仪表、自动化控 制、工程、交通、建筑等） B信息技术（包括计算机、电信、通讯、电子等） C数理（包括数学、物理、地球与空间科学等） D生命科学（包括生物、农学、药学、医学、健 康、卫生、食品等） E能源化工（包括能源、材料、石油、化学、化 工、生态、环保等）作品撰写的目的和基本思路作品撰写的目的：为缓解城市交通拥挤，改善交通状况，保障公共安全，提高汽车出行效率，通过以GPS为核心的动态路径分析，配合交通部门调度，使得交通网络运行畅通、高效。作品撰写的基本思路： 以基于静态路网的A*算法为核心，通过对原算法添加道路权值的约束（约束包括：道路等级系数、道路堵塞系数、道路通过系数、广播与交通部门信息的推荐系数），判断路径的动态情况，并作出车辆与路网的实时匹配，从而获得对交通行驶最有利的高效路径。作品的科学性、先进性及独特之处A*算法引入了启发式函数，启发式估价函数估价每一生成节点以确定此节点的优劣性。由于算法首先搜索最有希望的节点，利用这种方式，启发式函数决定在诸多路径中首先遍历那条路径以便搜索过程更为有效。而通过添加道路权值改进了A*算法，能够更精确地寻找出适合交通行驶的动态路径。算法通过添加广播与交通部门的推荐系数，能够结合实时交通情况对车辆进行有效地调度，提高了道路的利用效率。而GPS/DR相关模块的引入，可操作性强，两者结合1+12，能减少系统的搜索时间和运算速度，便于最佳路径的快速获得。作品的实际应用价值和现实意义针对城市路网的特点，对最短路径分析的关键技术进行了优化，提出实用的最佳路径分析解决方案，在此基础上实施了最佳路径分析方法及技术。随着城市交通设施和规则日益复杂，需要电子地图数据库能够完整地建立和表达路网的拓扑关系。本文的算法能准确、快速地检测和提取出运动目标并有很强的实践性,仿真程序能够按照算法约束条件的动态反馈信息对突发事件作出及时的处理，从而为城乡交通路网提供有效的、智能化的调度。学术论文文摘利用车辆导航技术的反馈信息，通过A*算法对静态路网的最优路径做出动态选择。基于静态路网信息的最优路径求解是现时车辆GPS导航领域所面临的关键问题。现今流行的Dijkstra算法、A*算法等，都是基于完全静态、确定的信息数据库下，求解得出的最短路径。本文通过A*算法充分利用静态路网信息，借助车辆导航系统加以动态路网中的适应条件，以及实时更新的交通数据，得出计算结果精确，时间复杂度较低，且符合实际情况的最佳路径。 作品在何时、何地、何种机构举行的会议上或报刊上发表及所获奖励于2011年3月获华南农业大学“丁颖杯”课外学术科技作品竞赛中获得一等奖鉴定结果请提供对于理解、审查、评价所申报作品具有参考价值的现有技术及技术文献的检索目录1杨利强,张宁,陶志祥. 3G移动通信技术在城市交通信息系统中的应用研究J. 公路交通科技, 2007,(12)2杨兆升. 关于智能运输系统的关键理论综合路段行程时间预测的研究J. 交通运输工程学报, 2001,(01)3于德新，杨兆升，高鹏. 动态限制搜索区域的带约束K则最优路径算法J. 吉林大学学报（工学版），2009（39）2:172-1764Van der Auweraer H,Mas P,Dom S,et al. Transfer analysis in the critical path of vehicle refinement:the role of fast,hybrid and operational path analysis .SAE Paper 2007 -01-23525杨瑞臣,周永付,云庆夏. 寻找车辆最优路径的混合算法J. 交通运输工程学报, 2005,(01) 6张兰,雷秀娟. 几种改进PSO算法在带时间窗车辆路径问题中的比较与分析J. 计算机工程与科学, 2008,(12) 7Juha Plunt. Finding and fixing vehicle nvh problems transfer path analysisJ .Sound and Vibration, 2005, 39 (11) :12-16 8Hendricx William,De Vis Dirk. An overview of the European research project DIANA .SAE Paper 9718979贺竹磬,孙林岩. 动态交通下车辆路径选择模型及算法J. 交通运输工程学报, 2007,(01) 10李瑞敏,陆化普. 基于WebGIS的智能交通管理指挥调度系统J. 计算机工程, 2007,(21) 11XU Yin-feng,HU Mao-lin,SU Bing,et al. The Canadian traveller problem and its competitive analysisJ .Journal of Combinatorial Opti mization, 2008, 15 (3) :223-227 申报材料清单（申报论文一篇，相关资料名称及数量）1、申报论文2、程序代码科研管理部门签章 年 月 日C.当前国内外同类课题研究水平概述 说明：1.申报者可根据作品类别和情况填写； 2.填写此栏有助于评审。1、 美国、西欧和日本等发达国家为了解决共同所面临的交通问题，竞相投入大量资金和人力，开始大规模地进行道路交通运输智能化的研究试验。2、 在美国，智能交通应用发展较快的几个方面分别是，车辆安全系统（占 51%），电子收费（占37%），公路及车辆管理系统（占28%），实时自动定位系统（占20%），商业车辆管理系统（占14%）。因为美国交通路网的前期规划十分合理，因此其关注的重点是安全。3、 北美、欧洲和日本的很多城市现在都在开始使用“自适应面控系统”，即面控的信号灯系统模式，而我国还主要停留在点控的信号灯系统模式上，可见差距巨大。国外一些城市现在已经尝试对每辆车安装GPS，以此确定每辆车的位置，最终通过物流网技术来调节交通拥堵。而国内还在对智能交通系统的基础中国国情下的“车流量”如何计算投入研究，规划实现一条线上四五个路口之间信号灯配合的线控系统模式。4、 国外的研究表明，智能交通系统可极大地提高公路的通行能力和服务水平，使每条车道每小时的车流量增加2至3倍，缩短行车时间35 50。此外，智能交通系统还可以大大提高公路交通的安全性，降低并排除人为错误、驾驶员心理对交通安全的消极影响，使预防和避免交通事故成为可能。从理论上讲，智能交通系统可以减少事故31 85。5、 利用地理信息系统（GIS），GPS，专用短程通信技术（DSRC）开发ATIS，ETC，CVO的车辆安全系统作为智能交通的主要应用在全球范围内已呈一种趋势。6、 智能交通的前景是美好的，但也是交通运输领域中技术难度最高的系统，其中，基于磁性标记诱导的车辆车道自动保持技术是当今世界车辆工程及自动控制领域的研究前沿，无论在理论上，还是在工程实践上都是对各国科研攻关实力和水平的考验。D.推荐者情况及对作品的说明说明：1由推荐者本人填写；2推荐者必须具有高级专业技术职称，并是与申报作品相同或相关领域的专家学者或专业技术人员（教研组 集体推荐亦可）；3推荐者填写此部分，即视为同意推荐；4推荐者所在单位签章仅被视为对推荐者身份的确认。推荐者情况姓 名洪添胜性别男年龄55职称教授工作单位华南农业大学工程学院通讯地址广东省广州市天河区五山路483号华南农业大学工程学院邮政编码510642单位电话（020）85282269 住宅电话推荐者所在单位签章 （签章） 年 月 日请对申报者申报情况的真实性作出阐述本论文主要由学生构思、编撰，符合 “丁颖杯”课外学术科技作品竞赛的要求，具有较高的可行性和实用价值。请对作品的意义、技术水平、适用范围及推广前景作出您的评价利用GPS/GIS进行动态路径优化，一定程度上缓解城市交通拥挤问题。而GPS技术已发展成熟，本方案能较好适用于交通流较大的区域，具有一定的推广意义。其它说明推荐者情况姓 名性别年龄职称工作单位华南农业大学工程学院通讯地址广东省广州市天河区五山路483号华南农业大学工程学院邮政编码510642单位电话住宅电话推荐者所在单位签章 （签章） 年 月 日请对申报者申报情况的真实性作出阐述本自然论文是曾志雄等学生在老师的指导下通过一系列的理论分析和讨论研究完成的，情况属实。请对作品的意义、技术水平、适用范围及推广前景作出您的评价针对交通路网的特点，对最优动态路径分析的各项关键技术进行了研究，编写了相关程序进行模拟，算法能准确、快速地检测运动车辆,有一定的实用价值。其它说明学校组织协调机构确认并盖章 （团委代章） 年 月 日 校主管领导或校主管部门确认盖章 年 月 日E大赛组织委员会秘书处资格和形式审查意见组委会秘书处资格审查意见 审查人（签名） 年 月 日组委会秘书处形式审查意见 审查人（签名） 年 月 日组委会秘书处审查结果合格 不合格 负责人（签名） 年 月 日基于GPS的最佳动态路径分析与仿真研究 陈沛明 曾志雄 黄涵 吴月宜 黄灿培指导老师：吴伟斌摘要：利用车辆导航技术的反馈信息，通过A*算法对静态路网的最优路径做出动态选择。基于静态路网信息的最优路径求解是现时车辆GPS导航领域所面临的关键问题。现今流行的Dijkstra算法、A*算法等，都是基于完全静态、确定的信息数据库下，求解得出的最短路径。本文通过A*算法充分利用静态路网信息，借助车辆导航系统加以动态路网中的适应条件，以及实时更新的交通数据，得出计算结果精确，时间复杂度较低，且符合实际情况的最佳路径。关键词：交通调度 动态路网 最佳路径 A*算法 GPSGPS-Based Dynamic Path Analysis Chen Peiming, Zeng Zhixiong, Huang Han, Wu Yueyi，Huang Canpei Abstract: Through the feedback information of vehicle navigation technologies, the best dynamic choice is made in static road network by A*algorithm. The solution of optimal path which static road network information based is the key point vehicle navigation (GPS) facing. Dijkstra algorithm and A*algorithm, which are completely based on static information database to determine the shortest path, are now popular. In order to obtain the best path, analyzing A*algorithm while making good use of static network, vehicle navigation system and real-time updates of traffic information. The Path has an accurate result and fits in different actual situations. Moreover, the time complexity of it is low and easy to realize.Key Words: Intelligent Transportation, Dynamic Network, Best Path, A*algorithm, GPS/DR0 引言目前，随着社会经济的发展、城市化进程的加快和机动车保有量的快速增长，尤其私家小汽车的快速发展，城市交通越发拥挤。由于土地资源不足，建造各种公路等物理设施的能力是有限的, 所以单纯地依靠修建更多的道路、扩大路网规模等这样的措施仅仅能解一时之需, 并不能从根本上解决日益增长的交通需求。基于这种需要，提出了以车载GPS（Global Positioning System）为核心的路径分析系统。该技术是以GPS技术为核心, 综合利用广播技术、光电传感器、计算机网络、自动控制和人工智能等技术的一种新型车辆导航技术1。现阶段，车载GPS进入规模化发展阶段。“车载GPS 最佳路径分析” 在车辆导航系统及城市应急系统中有着广泛的应用前景。针对城市道路网的特点，对基于城市道路网的最佳路径分析的关键技术进行了研究和验证。提出了一种实用、高效的最佳路径分析解决方案，并在此基础上实现了一个最佳路径分析法的高效实现算法。1 基于静态路网的A*算法原理一条路径的确定取决于许多因素，如距离、行程时间、路网弯数、路况复杂度、转向灯个数、交通信号灯的数目和动态交通信息等。选择最短路径、最佳路径、最低耗费等问题，都离不开最短路径搜索并以其作为选择依据。路径选择标准可由程序设计决定或通过用户界面修改2。最短路径问题的解决方法很多，包括启发式搜索A*算法、动态规划方法、神经网络、Dijkstra 算法等，其中以迪杰斯特拉(Dijkstra)算法在实际应用中较为广泛。由于Dijkstra算法的搜索过程属于遍历计算，所以出现大量的搜索节点。其中，Dijkstra算法与A*算法搜索范围特点如下图1所示。由于所引入的动态算法，是要求处理大量的静态数据的同时，还需要实时监测接受的动态数据，并计算当前对于最佳路径的影响的一些数据3。因此，处理量就变得相当大，一般来说，硬件不能支持。A*算法是比较流行的启发式搜索算法之一，被广泛应用于路径的最优解。A*算法对比其他算法，不同之处在于A*算法引入了启发式函数。启发式估价函数估价每一生成节点以确定此节点的优劣性。通过这种方式，启发式函数决定在诸多路径中首先遍历那条路径以便搜索过程更为有效，因为算法首先搜索最优希望的节点4。A*算法的算法步骤：1) 创建开放列表OPENLIST，初始化列表，使其只包含起始点；2) 创建关闭列表CLOSEDLIST，初始化清空列表；3) 从OPENLIST中选择f(n)值最小的一个节点n；4) 如果n是目标节点，停止搜索，转到步骤（7）；5) 对于n的相邻节点中的一个节点m；（1） 如果m在CLOSEDLIST中并且g（m）更小，更新节点m的g值，将其父节点指向n。（2） 如果m在OPENLIST中且目前的g（m）更小，更新节点m的g值，将其父节点指向n。（3） 如果m不在OPENLIST和CLOSEDLIST中，将m加入OPENLIST中，计算其g值，将其父指针指向n。6) 返回执行步骤（3），继续搜索；Dijkstra算法原节点目标节点A*算法图1 Dijkstra算法与A*算法搜索范围特点7) 从目标节点向上回溯到原节点，记录经过的节点。遍历一系列后向指针后，得到最佳路径；2 基于A*算法的最佳路径求解2.1 动态路网2.1.1 约束条件现实生活当中，交通信息属于动态信息，即每一段路都有其自己的属性。如果单纯地从距离和时间出发，所得出的最短路径与实际驾驶者所希望的并不能完全符合。譬如，得出的最短路径上，有其中路段属于交通拥堵严重的，即其路段的效率就相对低下。相对驾驶者来说，意味着比其他路径所使用的路径花费更多时间。又或者即使路径上没有交通意外，堵塞等情况，但是路径上出现较多的收费设置，同样对于驾驶者来说是不利的5。因为这意味着花费更多的费用。因此，必须从动态路网中分析主要影响车辆行驶最佳路径的因素。根据路径选择的限制要求，得出以下几点：1）道路系数道路的级别对于车辆通过性有重要意义，高速公路的效率肯定要比城市里面的支路的效率高。同样级别的道路，双车道和四车道同样拥有不同的通过效率6。根据我国现行的公路工程技术标准（JTJ001-1997），公路按使用任务、功能和适应的交通量分为高速公路、一级公路、二级公路、三级公路、四级公路五个等级： （1）、高速公路为专供汽车分向分车道行驶并应全部控制出入的多车道公路。 四车道高速公路能适应将各种汽车折合成小客车的年平均日交通量2500055000辆。 六车道高速公路能适应将各种汽车折合成小客车的年平均日交通量4500080000辆。 八车道高速公路能适应将各种汽车折合成小客车的年平均日交通量60000100000辆。 （2）、一级公路为供汽车分向分车道行驶并可根据需要控制出入的多车道公路。 四车道一级公路能适应将各种汽车折合成小客车的年平均日交通量1500030000辆。 六车道一级公路能适应将各种汽车折合成小客车的年平均日交通量2500055000辆。 （3）、二级公路为供汽车行驶的双车道公路。 一般能适应每昼夜30007500辆中型载重汽车交通量。 （4）、三级公路为主要供汽车行驶的双车道公路。 一般能适应每昼夜10004000辆中型载重汽车交通量。 （5）、四级公路为主要供汽车行驶的双车道或单车道公路。 双车道四级公路能适应每昼夜中型载重汽车交通量1500辆以下。 单车道四级公路能适应每昼夜中型载重汽车交通量200辆以下。2）GPS/DR（航位推算,Dead-Reckoning)组合定位的反馈信息DR的基本原理是利用方向传感器和速度传感器来推算车辆的瞬时位置，可以实现连续自主式定位。但由于其推算过程是一个累加过程，方向传感器的误差随时间的延长而积累，另外，推算只能确定相对位置和航向。因此，将航位推算与GPS 组合起来，两者取长补短，可以弥补各自的缺点, 确保系统能在任何时候都能为运动车辆提供较为准确的导航信息。一方面可以利用GPS精确的定位结果辅助DR 的初始化并且可以定期地用它对DR 的定位误差进行在线校正。另一方面，在GPS无法定位时系统又可以自动地切换到DR 导航方式，直至GPS 恢复正常接收后, 系统再回到GPS 与DR 的组合导航方式7。从而，即使在GPS失效、单独使用DR推算定位时也能长时间保持较高的定位精度。通过GPS反馈的定位信号进行运动车辆的检测和分割，预测其在相关路径的运动轨迹，从而根据交通流量综合其他情况进行调度，可以把发生冲突的交通流从时间和空间上进行分离，稳定平衡交通流的密度。3）广播和交通部门信息的双向调控在通信网络的支持下，参考广播电台的实时路面路况信息，即时接受交通部门发布的突发事故，并通过GSM通信网与移动中的车辆进行通话、短信息传输和数据传输，完成车辆定位、调度、监控、报警等功能，且在电子地图上显示车辆的位置，做出应急路径选择，间接地约束最优动态路径，避免大面积的交通瘫痪，保证动态路网运动车辆行驶路径的准确性8。其中，接受短信息可用GSM用户终端（如车载台、手机）或用可接收短信息功能的固定用户设备，也可用ISDN方式直接连接到移动通信局的短消息服务中心，并联通车辆导航管理系统，这样接收短信息更迅捷，容量更大9。4）可自动更新的数据库管理系统车辆定位导航系统由自导航系统，管理系统，组合系统三部分组成。同时，系统应配置有图形结构简单、冗余度小、拓扑关系简单、空间信息查询与分析速度快、拥有开放数据接口的电子地图数据库。出发地和目的地之间的最佳线路需要参照最新的时间、距离、收费等标准，并且所要求的数据存储冗余小，空间数据处理与分析操作时间短。因此，要求电子地图的数据库能够智能通过GRPS联网更新，进行电子地图数据的自适应，并要求装载硬盘的剩余空间足够大而拥有不断下载更新包的能力。2.1.2 算法流程 由上述约束条件，得到基于A*算法的最佳路径的算法流程图如图2所示。2.2 动态路径引导算法 （1）其中，g(n)是从原节点到当前节点所经过所有路段的时间总和。h(n)是从当前节点到目标节点的距离所估价的时间。di(n)是路段i（即该节点与前继节点之间）的距离。Vi(n)是路段i（即该节点与前继节点之间）允许的实际最大通过速度。Vi（n）通过速度的大小与道路等级系数K1、道路堵塞系数K2、道路通过系数K3、广播与交通部门信息的推荐系数K4、该路段所允许通过的最高车速Vimax有关。1）道路等级系数K1高速公路为1；一级路为0.95，城市路段中的快速路为0.95；二级路为0.9，城市路段中的主干路为0.9；三级路为0.85，城市路段中的次干路为0.85四级路为0.8，城市路段中的支路为0.8。2）道路堵塞系数K2不能通过为0，可以通过为1。影响原因有道路升级、保养、单向道或其它情况来判断。3）道路通过系数K3道路通过系数K3与当前道路交通流量、道路所允许通过最大交通流量max有关。 （与动态数据有关，可根据历史数据模拟得出稳定曲线。） 图2 基于A*算法的最佳路径算法步骤是不是结束在开始基于静态数据的路径规划引导车辆信号接收信号范围内抽取相关信息更新信息（为受影响的路段更新数据库）影响路段在路径上基于影响路段的动态信息和重新规划建立新的最优路径没有有不在开始 4）广播与交通部门信息的推荐系数K4由广播台统计各位在行司机上报的实时交通数据，整理并向交通部门进行实时信息的传输。由广播台收集的信息大多属于一手资讯，具有较高的可靠性。并由其对各主要路段提供道路通行的推荐系数（0=K4=1）。默认情况为K4=1。交通部门将收集整理所得数据，实时发送数据，装有GPS导航车辆接收后，导入算法计算，从而优化路径的选择。= （2）其中，d(n)是当前节点到目标节点的距离。用欧氏距离估算，通常小于、等于实际路径距离；V是估算速度；n为路段数。即可得函数： = （3）欧氏距离：，即两项间的差是每个变量值差的平方和再平方根，目的是计算其间的整体距离即不相似性。欧氏距离在路网中的代码如下：function distance=euclideandis(x，y)x and y：two vectors to be testedif(max(size(x)-max(size(y)label lerror(Array sizes do not match)；endif(rain(size(x)-=1)l(min(size(y)-一-1)error(Both x and Y are vectors)；endlabel2distance=sqrt(sum(xy)2)max(size(x)；3 RS、GIS的信息收发与处理GPS DR快速定位功能弥补了遥感不足，GPS 能将遥感获取数据实时快速进入地理信息系统，并保证遥感数据与地面同步监测数据获取动态配准，动态进入GIS（地理信息系统，Geographic Information System）、RS (遥感，Remote Sensing) 数据库。同时，利用遥感数据可实现GPS 定位遥感信息查询。GIS系统，GPS 定位信息电子地图上将以实时反映和漫游查询。将GPS 和电子图相配合，可组成各种电子导航和监控系统。并且，GPSDR 可为GIS 及时采集，更新和修正数据，输入电子图或数据库后，可对原有专题图进行修正，核实或形成新专题图件，从而得到动态实时的显示车辆的运行状况，车辆所处的位置，周围道路两侧的空间信息等10。通过最小距离点连点的方法获取原始路径，再由行车电脑内置的大容量导航电子地图处理相关位置信息，同时，对比优化电子地图的数据库进行自适应管理，添补更多的路面信息，包括路途上的交通信息，入限速标志、交叉路口转弯限制、信号灯等。根据当前位置和将要到达的目标位置(工作时输入)，导航系统自动，实时地计算和显示最短路径或最佳路径，引导驾驶员最快地到达目的地。最短路径或最佳路径的分析计算量比较大，因此采用上述的算法，减少系统的搜索时间和运算速度至关重要。最佳路径的选择不仅要考虑，距离最短，而且也要考虑时间最省，道路状况，交通管制等因素11。根据用户的要求，系统建立空间索引，通过查询和分析数据库的历史数据和道路空间数据的信息，选择满足用户要求的一条路线。4 仿真与结果分析因为权值是在GPS等约束条件的反馈信息中不断变化的，为了便于模拟路线的选择，通过Microsoft Visual C+ 6.0软件编程作出权值设定的最佳动态路径仿真。如图3所示，当目标车辆在某个起始点（如3）中，通过对周围路况的判断，可清晰地得到各路线的情况，从而选择最佳路径。 图 3 当起始点为3时的路径选择仿真 由起始点为3的路径选择模拟可知，此程序可以实现：1）、判断不同路线的实际可通过情况；2）、在路程上比较不同路线的优劣，计算出最短路程；3）、智能选择从起始点到目的地的最佳路线。不过，此程序的进一步优化还需要确定的、实时的反馈信息来约束。5 结论本文讨论分析了基于车辆监控导航系统的A*算法最佳路径,并通过相关的约束条件进行优化。针对城乡路网的特点，对最短路径分析的各项关键技术进行了研究，编写了相关路径选择程序进行了模拟，提出了一种实用的最佳路径分析解决方案，在此基础上实施了最佳路径分析方法及技术；城市交通设施和规则日益复杂，需要进一步改进数据模型，较完整地表达和建立了路网的拓扑关系。本文的算法能较准确、快速地检测和提取出运动目标,为交通调度提供了保障,有一定的实用价值。参考文献1杨利强,张宁,陶志祥. 3G移动通信技术在城市交通信息系统中的应用研究J. 公路交通科技, 2007,(12)2杨兆升. 关于智能运输系统的关键理论综合路段行程时间预测的研究J. 交通运输工程学报, 2001,(01)3于德新，杨兆升，高鹏. 动态限制搜索区域的带约束K则最优路径算法J. 吉林大学学报（工学版），2009（39）2:172-1764Van der Auweraer H,Mas P,Dom S,et al. Transfer analysis in the critical path of vehicle refinement:the role of fast,hybrid and operational path analysis .SAE Paper 2007 -01-23525杨瑞臣,周永付,云庆夏. 寻找车辆最优路径的混合算法J. 交通运输工程学报, 2005,(01) 6张兰,雷秀娟. 几种改进PSO算法在带时间窗车辆路径问题中的比较与分析J. 计算机工程与科学, 2008,(12) 7Juha Plunt. Finding and fixing vehicle nvh problem stransfer path analysisJ .Sound and Vibration, 2005, 39 (11) :12-16 8Hendricx William,De Vis Dirk. An overview of the european research project DIANA .SAE Paper 9718979贺竹磬,孙林岩. 动态交通下车辆路径选择模型及算法J. 交通运输工程学报, 2007,(01) 10李瑞敏,陆化普. 基于WebGIS的智能交通管理指挥调度系统J. 计算机工程, 2007,(21) 11XU Yin-feng,HU Mao-lin,SU Bing,et al. The Canadian traveller problemand its competitive analysisJ .Journal of Combinatorial Opti mization, 2008, 15 (3) :223-227 附录 A*算法的代码与代码的功能using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Linq;using System.Text;using System.Windows.Forms;namespace GPSSystem public partial class Form1 : Form / 邻接矩阵 protected static int?, EdgeMetrix; / 经过顶点的标示符 protected static int Space; / 起点到各点最短路径 protected static int? ShortDistance; / 最短路径线路 protected static string Path; / 顶点个数 protected static readonly int NumVertices = 10; / 起点 protected static int StartIndex; protected static string content; public Form1() InitializeComponent(); private void button1_Click(object sender, EventArgs e) Space = new intNumVertices; ShortDistance = new int?NumVertices; Path = new stringNumVertices; FillEdgeMetrix(); string StrIndex = textBox1.Text; content = ; if (Int32.TryParse(StrIndex, out StartIndex) ComputeShortPath(StartIndex); PrintShortPath(); textBox2.Text = content; / 填充邻接矩阵 static void FillEdgeMetrix() EdgeMetrix = new int?NumVertice