搜索
电子科技大学UNIVERSITYOFELECTRONICSCIENCEANDTECHNOLOGYOFCHINA硕士学位论文MASTERTHESIS论文题目路径规划算法的研究及应用学科专业计算机软件与理论学号201221060340作者姓名谢娟指导教师刘贵松（副）教授分类号密级UDC注1学位论文路径规划算法的研究及应用（题名和副题名）谢娟（作者姓名）指导教师刘贵松(副)教授电子科技大学成都（姓名、职称、单位名称）申请学位级别硕士学科专业计算机软件与理论提交论文日期2015.3.26论文答辩日期2015.5.11学位授予单位和日期电子科技大学2015年6月答辩委员会主席评阅人注1：注明《国际十进分类法UDC》的类号。2015.05.112015.03.266PATHPLANNINGALGORITHMSANDITSAPPLICATIONRESEARCHAMasterThesisSubmittedtoUniversityofElectronicScienceandTechnologyofChinaMajor:ComputerSoftwareandTheoryAuthor:XieJuanAdvisor:ProfessorGuisongLiuSchool:SchoolofComputerScience&Engineering独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。作者签名：日期：年月日论文使用授权本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后应遵守此规定）作者签名：导师签名：日期：年月日摘要I摘要路径规划近年来一个热点研究问题，它被广泛应用于多个领域也形成了较完善的理论体系和算法基础。随着科学技术的不断进步，路径规划的应用范围也不断扩展，逐渐成为众多领域的关键技术。其应用最多的领域有：机器人避障行驶、智能交通、物流运输等。路径规划方法已经拓展到一切以点线构成网络拓扑的多目标问题当中。因此，路径规划算法由于其广泛的应用范围、种类繁多更是得到广大研究人员广泛的关注。本文将通过对路径规划算法进行一定的研究，旨在应用路径规划算法解决实际应用问题。首先，本文将针对VRPTW（VehicleRoutingProblemwithTimeWindow）问题构建一种改进的禁忌搜索（TabuSearch）算法进行求解。改进TS算法主要从初始解生成方式、禁忌结构设计以及禁忌长度等方面进行。文中将详细介绍改进TS算法的各个组成部分以及执行流程，并通过实验对该改进方法进行效果验证。实验结果表明，本文所构建的算法对具有一定聚集分布特性的数据集能够达到理想目标，但是也存在对随机分布数据的适用性不足的缺陷。通过对VRPTW问题的求解，本文将根据实际运输中可能出现新的运送需求、或者原来客户偶然提出的服务需求量的变化等情况，在VRPTW模型中增加动态需求，构成DCVRPTW（DemandChangeVehicleRoutingProblemwithTimeWindow）模型。本文将进一步将改进TS算法应用到DCVRPTW中，并使用局部最小变动为目标对动态需求进行调整。通过实验表明，本文所使用的局部调整算法对DCVRPTW问题具有一定的适用性并且加快调整速度从而保证实时需求。最后，本文将进一步将路径规划算法的应用范围进行拓展探究。本文将路径规划技术与社交网络进行有机结合，从路径规划的角度重新审视社交网络中不同用户间信任关系或者影响力的计算问题。文中将构建一种简单并且高效的影响力计算方法并将该方法应用到微博关注关系中以验证算法的有效性。为了将计算结果进行实用性探究，本文将影响力大小应用到好友推荐中，进一步验证了影响力计算的重要性以及本文计算方法的合理性和实用性。路径规划的应用范围广泛，而且拥有许多优秀的规划算法。本文通过对其某一方面的研究旨在探讨其应用价值以及存在的不足。对现有算法进行改进或者结合多种算法构建混合算法是未来工作的主要方向。此外，与一些新领域的结合也是路径规划技术未来的发展方向。关键字:路径规划，车辆路径问题，禁忌搜索，社交网络ABSTRACTIIABSTRACTRouteplanningisahotissueinrecentyears.Itiswidelyusedinavarietyoffieldsandhasformedacompletetheoreticalsystem.Withtheprogressofscienceandtechnology,thescopeofapplicationofpathplanningtechnologyisexpanded.Now,itbecomesthekeytechnologyinmanyareas.Themainapplicationareasarerobotrouteplanning,intelligenttransportation,logistics,andsoon.Pathplanningmethodhasbeenextendedtotheentiremulti-objectiveproblemsthatcanconsistwithdotsandlines.Therefore,thepath-planningalgorithmsreceivetheattentionofresearchersbecauseofthewidelyuseofit.Thispaperwilldosomeresearchonthepathplanningalgorithmanduseittosolvepracticalapplicationproblems.Firstofall,thisarticlewillbuildanimprovedTS(TabuSearch)algorithmtosolvetheVRPTW(VehicleRoutingProblemwithTimeWindow)problem.Theimprovementswillbeprocessedfromthewaytogeneratetheinitialsolution,thestructureofthetabooobjectandthelengthofthetaboolistandsoon.WewilldescribetheimprovedTSalgorithminmoredetailformthepartitionsofthealgorithmandthestepsofit.Then,wewilldosomeexperimentstotesttheresultsofourimprovedmethods.Theresultsoftheexperimentsshowthatouralgorithmcanachievegoodresultsunderthedatathatwithaclustereddistributioncharacteristic,butthereisadeficiencythattheresultsunderthedatawithrandomlydistributedareinferior.BysolvingtheVRPTWproblems,accordingtothenewdeliveryrequirementmayappearintheactualtransportationorthechangesinthedemandmayoccur,weaddsomedynamicneedstotheVRPTWmodel.ItconstitutesanewmodelthatnamedDCVRPTW(DemandChangeVehicleRoutingProblemwithTimeWindow)problem.ThisarticlewilltrytoapplythemodifiedTSalgorithmtosolveDCVRPTW.Andwewillchoosethesmallestchangeoftheinitialroutesasthegoalsinadjustmentstothedynamicrequirements.ExperimentsshowthatpartialadjustmentalgorithmwhichusedinthisarticleforsolvingDCVRPTWhasapplicabilityandefficiencyandcanensuretherealtimerestraint.Finally,wewilltrytoexpandthescopeofapplicationofpathplanningalgorithm.Wewillattempttointegratethepathplanningtechnologyintothesocialnetworking.Andtrytocalculatethetrustsorinfluencebetweentwousersinthenetfromtheperspectiveofpathplanning.ThispaperwillbuildasimpleandefficientcalculationABSTRACTIIImethodtoevaluatetheinfluencebetweenusersandwewillapplyittoassesstherelationshipsinmicro-blogtoverifytheeffectivenessofthealgorithm.Inordertoapplytheresultstopracticalresearch,wewillusetheinfluencetodosomerecommendation.Thiswillvalidatetheimportanceofthecalculationoftheinfluenceandtherationalityandpracticalityofourmethod.Pathplanningiswidelyusedindifferentarea,anditalsohasmanyexcellentalgorithms.Basedontheresearchontheoneaspectofit,wetrytoexplorethevalueoftherouteplanningtechnologyandthedeficienciesofthealgorithms.Toimprovetheexistingmethodsorcombinemultiplealgorithmstobuildahybridalgorithmisthemaindirectionoffuturework.Inaddition,toapplythepathplanningtechnologytothenewareasisthefutureworkneedtobedone.Keywords:pathplanning,vehicleroutingproblem,tabusearch,socialnetwork.目录IV目录第一章绪论.....................................................................................................................................11.1研究背景与意义...