文档介绍：兰州理工大学
硕士学位论文
车载导航系统中路径规划问题的研究
姓名:屈展
申请学位级别:硕士
专业:系统工程
指导教师:曹洁
20090515
摘要路径,该方法能够根据人们不同的需求和道路实时隋况,有效地避开狭窄和交通拥挤地在经典的车辆路径规划问题中,道路的交通信息如行车距离、固定的交通管理信息等,在路径规划前是已知的,这些信息不随时间的推移而变化,属于静态的路径规划。而在实际的车辆路径规划问题中,如路网中交通信息分配、交通事件信息等,都是实时变化的。近年来,通信和信息处理技术以及计算机硬件的发展,使得快速获取和处理实时信息、动态安排车辆路径成为可能,从而为动态规划研究创造了条件,动态车辆路径规划问题也就成为了研究的热点。本文将路径规划问题转化为加权路径,以路径长度与通行时间的线性组合为目标函数的优化问题,加入了道路的重要程度和宽敞程度等作为权值。并且总结和讨论了车载导航系统存在的问题和静态、动态最优路径规划的基本概念和理论,建立了动态路径规划模型,根据加入的权值得出模型的解。同时,分别给出了静态路径规划的算法和动态路径规划最佳成熟时间法,由于这两种方法求解动态路径规划问题都存在缺陷,本文提出用蚁群算法来求解动态路径规划问题,并采用效率优先的信息素实时更新策略,对于求解过程中出现局部最优解,引入随机蚂蚁这一概念。接着简要介绍了模型和广义费用模型,在模型的基础上,对路径状况进行了分析,根据广义费用方程,设计分层搜索算法,结合蚁群算法求解最优路径。最后,以时间最少作为规划准则,采用蚁群算法与分层搜索相结合的方法求解最优段,并且规划的路径长度和通行时间都较短,符合人们日常生活所需,实验结果表明,用该方法进行最优路径规划合理、有效。关键词:车载导航系统;静态路径规划;动态路径规划;蚁群算法;随机蚂蚁;分层搜索算法;模型;硕士学位论文
,瑂,.....瑆,,.,;Ⅱ
硕士学何论文籹;籬
插图索引图车载导航系统示意图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.慕峁雇肌图车载导航系统的基本框图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯低匙槌伞ぷ魑佬羌肮斓朗疽馔肌图最短路径算法分类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图基于问题类型的最短路径问题的分类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图基于网络特征得最短路径问题分类体系⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图基于实现技术的最短路径问题的分类体系⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图导航用寻路算法分类⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图离路引导⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图时间路网模型⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图最优路径所搜过程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图先进先出条件⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图宦鉌跫难奥贰图煲洗映惭ㄒ浦潦澄镌础图搜索空间对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图邻接节点集的引入⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图路径分层搜索算法流程⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图兰州市地图子图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图交通网络图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图分类查找⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图站点选择对话框⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图节点属性表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。图路段属性表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。图网络结构属性表⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯图算法得到的最短路径⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯.图改进蚁群算法的流程图⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。图煌髡G榭鱿碌穆肪豆婊图承┲凡枞榭鱿陆峁员取图尤ê蟮慕峁车载导航系统【路径规划问题的研究
附表索引表中国汽车数量调查表ノ唬和蛄⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯表节点表结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯表路段表结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯:⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..表拓扑网络结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..表可行表的结构⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯表道路权值的设置⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯..表参数设定⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯一表交通流正常情况下结果对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯。表某些支路产生阻塞情况下结果对比⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯硕十学位论文
日期