时间限制下动态路网路径规划算法的研究与实现

《时间限制下动态路网路径规划算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、UniversityofScienceandTechnologyofChina硕士学位论文肘问阪喇下动态路网路径规划论文题目算法的斫免与卖现程思故作者姓名信妾全学科专业许胤龙教救孙卢中到教提导师姓名二〇一五年四月完成时间肀科嗲技术大營硕士学位论文时间限制下动态路网路径规划算法的研究与实现作者姓名程思敏学科专业信息安全导师姓名许胤龙教授孙广中副教授完成时间UniversityofScienceandTechnologyofChinaAdissertationformaster'sdegreeTimeConstrainedDynamicRoad

2、NetworkPathPlanningAlgorithmDesignandImplementAuthor'sName：：：中国科学技术大学学位论文原创性声明本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写过的研宄成果。与我一同工作的同志对本研究所做的贡献均己在论文中作了明确的说明。作者签名：签字日期：中国科学技术大学学位论文授权使用声明作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥有学位论文的部分使用权，卩：学校有权按有关规定向国家有

3、关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入《中国学位论文全文数据库》等有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。保的学位论文在解密后也遵守此规定。公开口保密年作者签名导师签名：今中签字日期：签字日期：摘要摘要静态路网无法实时地对交通状态进行表达，传统的路径规划算法也多是基于静态信息进行路径规划，没有利用到实时的交通信息。但是随着信息釆集技术的发展，能够很容易获得到实时的交通路况信息，所以在当代导航设备中，更适合使用基于实时交通

4、信息的动态路径规划算法进行导航。另外，由于路网的不断变化，在某些场景下，可用的求解时间非常少，用户对动态路径规划算法有着非常高的实时性要求。算法如何在有限的求解时间内，尽可能地提高求得的路径的质量，是一个很值得研究的问题。本文的主要工作有：，改进的动态路网模型的研究本文结合以下事实对传统实时路网模型进行改进。用户在一次出行过程中，交叉口的等待时延占总时间，不可忽略。传统的路网模型笼统地用一个权值来表示经过一个路段的行驶时间，不便实时信息的收集和计算，且无法直观表现出路段的拥堵程度。本文针对上述两点改进，引入交叉口时延和路阻系数，对动态路网进

5、行更为准确地表达，方便后续的算法研宄。对已有的动态路径规划算法进行分析，提出算法文中对已有的、算法进行分析研宄，指出它们的算法思想，并结合它们的性质提出算法。并用实验比较它们的导航结果，分析指出，算法会将较多的节点放入下一轮进行搜索，总体上反而增加了求出最优路径的计算量，在实时性要求较高的场景中，算法的导航效果反而总体表现较好。，利用算法的性质，提出算法算法可以通过改变影响因子调整求解时间和路径质量，多核导航设备具有并行计算的能力。结合以上因素，文中提出的算法并行运行多个影响因子不同的算法实例，在限制时间内返回己得路径集合中的最优解，能有效

6、保证每轮搜索的路径质量。实验表明，由于各个算法实例运行时间和返回的路径质量都不同，通过合理地设计各个实例影响因子，算法能很好地适应各种不同实时性要求的导航场景。关键词：动态路网，路径规划，求解时间限制，ABSTRACTABSTRACTStaticroadnetworkscannotreflectreal-timetransportation.Likewise,traditionalnavigationsystem，，’，，，，，，，，ABSTRACTvariedimpactfactore5canguaranteethepathquality

7、ineachsearchsession.Experi?mentsshowthatdespitedifferencesincomputationtimeandreturnpathqualityunderdiferentalgorithms，，目录目录录表格索弓丨插图索引算法索引第一章绪论研宄问题概述点到点的最短路径问题动态路径规划问题现实场景中对求解过程的高实时性要求相关工作介绍静态路径规划算法概述用于估值的启发函数动态路径规划算法概述本文研宄内容本文组织结构本章小结第二章改进的实时路网模型传统的路网模型模型描述上述模型中的不足之处改进的实时

8、路网模型模型描述模型中的参数获取改进路网模型与传统模型的比较在上述改进模型中进行动态路径规划问题的数学描述本章小结目录第三章研究基础与实验说明研究基础算法算法算法算法实验说明实验