带容量约束的开放式弧路径问题的算法研究

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

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

2、件和磁盘。（保密的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日万方数据中文摘要具有容量约束弧路径问题（CapacitatedArcRoutingProblem,CARP）产生于交通运输服务系统，因其广泛应用于城市街道清扫、垃圾回收、输电线路检查、物流配送等现实生活中，而得到了广泛的研究。本文主要研究CARP的一种新的扩展类型―具有容量约束的开放式弧路径问题（OpenCARP,OCARP），该类问题与CARP的主要区别在于车辆在服务完所有客户后无需返回车场。该类问题主要产生于第三方物流配送服务业，而且随着电子商务的日渐繁荣，第三方物流配送企

3、业间的竞争也更加激烈，提升物流配送服务效率，较好地满足大城市及超大城市的密集型配送需求，降低物流配送成本，对第三方物流企业的存亡至关重要。本文详细描述了OCARP的图论模型及数学模型，分析了其现有的求解算法及求解效果，设计了两种算法用于求解OCARP，即禁忌搜索算法与改进的变邻域搜索算法。禁忌搜索算法基于局部搜索算法，通过接受劣解来避免算法陷入局部最优，同时使用禁忌表来避免循环搜索，最后配合破特赦则来允许算法向更好的区域搜索，该策略使得算法同时具有广度搜索与深度搜索的良好性能。变邻域搜索其基本思想是在局部搜索的过程中系统地改变当前解的邻域结构，以降低陷入局部最优的风险，经过多次迭代，最

4、终达到收敛的目的。两种算法在81个基准数据集上的测试结果表明了它的有效性，TS算法在23个算例上达到了最优下界，并优化了51个算例的最优上界；IVNS算法在28个算例上达到了最优下界，并优化了55个算例的最优上界。关键词：开放式，弧路径问题，禁忌搜索，变邻域搜索，劣解万方数据ABSTRACTTheCapacitatedArcRoutingProblem(CARP)comesfromurbantransportationsystem.Lotsofstudieshavebeenattractedduetoitswidelyuseinurbanstreetswapping,wastecoll

5、ection,inspectionofpowerlines,packagedeliveriesandsoon.AnewkindofCARP,openCARP(OCARP)isstudiedinthispaper.ThisproblemisrelatedtotheCARPbutdiffersfromitsincetoursarenotconstrainttoformcyclesinOCARP.Basedonthedevelopmentofexternalthird-partylogistics,thisproblemisproposed.Alongwiththeprosperityofe

6、-commerce,competitionbetweenrelatedcompaniesbecomesmoreandmorefierce.Liftingefficiencyoflogisticssystem,satisfyingthedemandsinlargeandsuperurbancityandloweringthelogisticscostplayanimportantroleinthesurvivalofthelogisticscompanies.Inthispaper,adetailedmodelisproposed,theexistingalgorithmsandther

7、eeffectsarestudied,andtwokindsofalgorithmsareadoptedforOCARP,calledTabuSearch(TS)andImprovedVariableNeighborhoodSearch(IVNS).Basedonthelocalsearchalgorithm,TSalgorithmhasagoodperformanceinbothwidthandbreadthbyacceptinginferi