带有收益的无向容量约束弧路径问题的算法研究

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

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

2、保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：金倩倩导师签名：林丹签字日期：2013年5月28日签字日期：2013年5月28日中文摘要容量约束弧路径问题(CapacitatedArcRoutingProblem,CARP)产生于交通运输服务系统，是弧路径问题(ArcRoutingProblem,ARP)的一种特殊情况，因其可应用于如城市垃圾回收、街道清扫、邮件投递、结冰路面撒盐及路面维护等实际问题，故近年来得到了广泛的研究。本文主要研究此问题的一种

3、新的扩展类型，即带有收益的无向容量约束弧路径问题(UCARPP)。此问题与传统的弧路径问题最大的区别就是不必对网络中所有的客户弧进行服务，每条客户弧有收益、遍历时间、需求三个属性值，服务车队在满足容量及时间限制的前提下，对部分客户弧进行服务，目标使总收益值最大。该类问题是NP-hard问题，传统的算法如精确算法、下界法都因自身缺陷而不能很好地解决这类问题，而变邻域搜索算法(VNS)作为一种元启发式算法因其内在的简单高效、通用性强等优点有希望很好地解决UCARPP问题。本文以UCARPP为研究对象，在广泛查阅国内外文献的基础上，深入研究该

4、问题的求解方法，提出了求解UCARPP问题的分割启发式算法和变邻域搜索算法，为CARP问题推广形式的求解提供了借鉴与参考，主要研究工作和成果如下：1、对CARP问题及其推广形式进行了描述，并引入了带有收益的无向容量约束弧路径问题(UCARPP)，并给出该问题的数学模型，在归纳总结已有方法的基础上，设计相应算法解决该问题。2、本文根据UCARPP问题的特性，提出一种分割启发式算法来获得初始解，加快程序运行速度，同时加大算法寻优能力。3、运用六种邻域结构进行广域搜索，其中针对邻域结构的选择设计了旋轮法。数值试验结果表明，分割算法提高了算法的

5、效率，六种邻域结构的设计避免了早期陷入局部最优，该算法能有效解决一定规模的UCARPP问题，为实际应用奠定了基础。关键词：带有收益的有容限的弧路径问题；变邻域搜索算法；局部搜索；分割算法；邻域结构；旋轮法ABSTRACTCapacitatedArcRoutingProblem(CARP)stemsfromtransportationservicesystem,aspecialcaseofarcroutingproblem,hasbeenwidelystudiedrecentlybecauseofitsusageinpracticalis

6、suessuchasurbangarbagecollection,streetcleaning,maildelivery,saltsprinkleandroadmaintenance.Inthispaperanewextensionofthisproblem,calledtheundirectedcapacitatedarcroutingproblemwithprofits(UCAPP),isconsidered.ThebiggestdifferencebetweenCARPandUCARPPisthatthelatterdonotha

7、vetoserveallthecustomeredges,withwhichcollectingprofit,traversaltimeandservicingdemandareassociated.TheUCARPPmodelaimsatgeneratingseveralroutes,whicharesubjecttocapacityandtraveltimeconstraints,andprimarilymaximizetheprofitcollectedfromthesubsetofcustomeredges.Manytradit

8、ionalmethodssuchasaccuracyalgorithmandlowerboundmethodcan’teffectivelysolvethiskindofproblembecauseitis