带有随机需求的容量约束弧路径问题的算法研究

《带有随机需求的容量约束弧路径问题的算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之外，论文中不包含其他人已经发表或撰写过的研究胜过，也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：签字日期：年月日学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和

2、磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日中文摘要容量约束弧路径问题(CapacitatedArcRoutingProblem,CARP)源于垃圾回收、扫雪、邮件投递等实际问题，是弧路径问题(ArcRoutingProblem,ARP)的一种扩展类型，在现实中具有非常重要的应用价值，故近年来越来越受到研究者的关注。本文所研究的带有随机需求的容量约束弧路径问题（CapacitatedArcRoutingProblemwithStochasticDemands,CARPSD），由于考虑每条任务边的需求是随机的,因此属于容量约束弧

3、路径问题的一种推广形式。该类问题是NP-hard问题，传统的算法如分支定界方法等无法求解实际中出现的大规模例子，而元启发式算法因其内在的自适应性、并行性、稳定性等强大优点有望能解决大型的容量约束弧路径问题。本文以CARPSD为研究对象，在广泛查阅国内外文献的基础上，深入探索该问题的求解方法，提出了求解CARPSD问题的分割算法、自适应局部搜索算法和自适应领域搜索算法，有效地解决CARPSD问题，主要研究工作和成果如下：首先，对基本CARP问题进行了描述，并引入了带有随机需求的CARP问题(CARPSD)，给出该问题的数学模型，进行了相关的理论证明，完成对问题可行性的基本假设。其次，根据C

4、ARPSD问题的特性，提出一种随机路径扫描(StochasticPathScanning，SPS)与分割算法来建立随机条件下的可行解及最短路径，其中设计的分割算法对可行解进行重新排序分割，计算所有可能情况下的最小费用。以最小费用的期望作为最终的判断指标，记录并保存从车场到当前弧的最小期望费用，直到所有需求弧服务完毕。最后，基于算法的自适应，利用启发式算法极强的鲁棒性和内在并行机制等优点进一步求得问题的近似最优解。但由于基本启发式算法例如遗传算法，模拟退火算法、禁忌搜索算法在求解过程中易限于局部最优，因此设计出两种相对有效的启发式算法：自适应局部搜索算法、自适应领域搜索算法。数值试验结果表

5、明，两种算法在该类问题的表现优于以往所设计的启发式算法，使CARPSD问题得到有效解决。关键词：容量约束弧路径问题；启发式算法；邻域结构；局部搜索；随机路径扫描；自适应性；随机需求；ABSTRACTTheCapacitatedArcRoutingProblem(CARP),arisesinpracticalissueslikewastecollection,wintergrittingandmaildelivery,isanextensionofArc-RoutingProblem(ARP).Inreality,ithasbeenreceivingincreasingresearchre

6、centlyforitscrucialvalueofapplication.TheCapacitatedArc-RoutingProblemwithStochasticDemands(CARPSD),studiedinthispaperandconsideringthedemandofeveryrequiredarcisstochastic,isaspreadingformoftraditionalCapacitatedArcRoutingProblem.Manytraditionalmethodssuchasbranchandboundalgorithmcan’tsolvethisla

7、rgesizeofproblembecauseitisNP-hard.But,meta-heuristic,knownasitspowerfuladvantageininherentself-adaptiveability,parallelcomputingandstability,havepromisingtogiveagoodsolutiontothecapacitatedarcroutingproblem.Thispaperm