基于gis的大规模数据下k优路径规划算法的研究与实现

《基于gis的大规模数据下k优路径规划算法的研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于GIS的大规模数据下K优路径规划算法的研究与实现田大鑫2016年1月中图分类号：TP391UDC分类号：004.9基于GIS的大规模数据下K优路径规划算法的研究与实现作者姓名田大鑫学院名称计算机学院指导教师刘琼昕副教授答辩委员会主席刘玉树教授申请学位工学硕士学科专业计算机科学与技术学位授予单位北京理工大学论文答辩日期2016年1月基于GIS的大规模数据下K优路径规划算法的研究与实现作者姓名田大鑫学院名称计算机学院指导教师刘琼昕副教授答辩委员会主席刘玉树教授申请学位工学硕士学科专业计算机科学与技术学位授予单位北京理工大学论文答辩日期2016年1月

2、ResearchandImplementionofKoptimalPathPlanningAlgorithmbasedonGISforLargeScaledataCandidateName：TianDaxinSchoolorDepartment:ComputerScienceandTechnologyFacultyMentor:AssociateProf.LiuQiongxinChair,ThesisCommittee：Prof.LiuYushuDegreeApplied:MasterofEngineeringMajor：ComputerScien

3、ceandTechnologyDegreeby:BeijingInstituteofTechnologyTheDateofDefence：January，2016研究成果声明本人郑重声明：所提交的学位论文是我本人在指导教师的指导下进行的研究工作获得的研究成果。尽我所知，文中除特别标注和致谢的地方外，学位论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得北京理工大学或其它教育机构的学位或证书所使用过的材料。与我一同工作的合作者对此研究工作所做的任何贡献均已在学位论文中作了明确的说明并表示了谢意。特此申明。签名：日期：北京理工大学硕士学位论文

4、摘要路径规划问题是地理信息系统（GIS）研究领域中的关键内容之一，最短路径的寻找更是热点问题。在数据量较大时，传统前K条最短路径算法效率较低，且不能解决某些实际需求下规划K条差异较大的路径问题。以Dijkstra算法为预处理，为有向图的节点引入有利度的概念，通过对路径结果重复度的检测以及改变有利度引起图的变化，循环使用A*算法寻找当前图中的最佳路径，从而实现了Kth条差异路径的规划。使用的A*算法时间复杂度较低，所以与同类算法相比，效率较高，得到的Kth条路径结果在满足一定重复度要求的同时长度也较为合理。同时针对大规模数据量下多次路径规划下路段拓扑

5、路径规划系统的效率低下的问题，提出地图缓冲算法，优化了路段拓扑，提升路径规划系统总体效率。关键词：Kth路径；Dijkstra算法；有利度；大规模数据；地图缓冲I北京理工大学硕士学位论文AbstractPathplanningproblemisoneofthekeycontentsintheresearchfieldofGeographicInformationSystem(GIS),amongwhichthefindingoftheshortestpathisalwaysahottopic.underlarge-scaledata,theeffi

6、ciencyoftraditionalalgorithmsofKthshortestpathsisrelativelylow,andsomepathproblemsconcerningbigdifferencebetweentheplannedKthpathsunderactualrequirementscannotbesolved.Dijkstra’salgorithmwasemployedforpreprocessing,applyingtheconceptsoffavourabilityandrepeatability.Throughexam

7、inationoftherepeatabilityofthepathresultsandchangesinthegraphcausedbyadjustmentsmadetothefavourability,theA*algorithmwasusedrepeatedlytoidentifytheoptimalpathsinthecurrentgeographicinformationsystemgraph.Comparedwithsimilaralgorithms,thisalgorithmisfaster,andthemultiplepathres

8、ultsobtainedmeettherequirementforcertainrepeatabilitywhilethe