需求可拆分的容量约束弧路径问题分析-analysis of capacity constrained arc path problem with split requirements.docxVIP

独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。学位论文作者签名：签字日期：年月日学位论文版权使用授权书本学位论文作者完全了解天津大学有关保留、使用学位论文的规定。特授权天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交论文的复印件和磁盘。（必威体育官网网址的学位论文在解密后适用本授权说明）学位论文作者签名：导师签名：签字日期：年月日签字日期：年月日中文摘要本文所研究的需求可拆分的容量约束弧路径问题是一个运筹学领域中的组合优化问题。它在现实生活中具有非常广泛的应用，如：冬季道路撒盐问题、市政垃圾清理问题、邮件投递问题等都能抽象为需求可拆分的容量约束弧路径问题。通常，车辆运输成本是具有容量约束的弧路径问题的总成本的主要组成部分，因此通过优化车辆路径安排可有效地降低成本，同时也能提高服务水平和降低零担空载率。通常的容量约束弧路径问题的研究中，都设定了预先条件，即每个客户的需求(指小于车辆容量的需求)必须由一辆车且必须在一次服务中完成。然而，在满足服务要求前提下的实际运作中，通过需求的拆分可进一步降低运输成本，尤其是在需求量较大的情况下。基于上述原因，选择需求可拆分的容量约束弧路径问题作为本文的研究主题。由于问题本身的复杂性，现有的研究工作均无法在此问题规模的多项式时间内找到全局最优解。构造型启发式方法得到的解可作为元启发式算法的初始解，从而保证元启发式算法的性能优于构造型启发式方法。因此，本文考虑利用构造型启发式算法来对问题进行求解，求出的是问题的初始解。本文在广泛深入地查阅国内外文献的基础上，通过理论分析、建模、算法求解这一过程对需求可拆分的容量约束弧路径问题进行了深入研究，研究重点在于如何利用构造型启发式算法求解需求可拆分的容量约束弧路径问题。主要内容如下：首先，简要介绍了容量约束弧路径问题和需求可拆分的车辆路径问题的起源和发展历史，归纳总结了其求解方法。建立了需求可拆分的容量约束弧路径问题的整数规划模型，对可行解的基本特性进行了分析，证明了判断解是否可行的两个重要判据，并对拆分需求的意义进行了简单分析。其次，系统、详尽的介绍了三种算法的基本理论和方法，在目前国际上普遍认同的公共测试集上进行三种算法的对比实验分析。最后，对全文进行总结，并对下一步的研究进行展望。关键词：需求可拆分；容量约束弧路径问题；构造型启发式算法ABSTRACTSplitdeliverycapacitatedarcroutingproblemisacombinatorialoptimizationproblem.ItisoneoftheattractiveareainthecirclesofOperationsResearch.Ithaswidereal-worldapplicationssuchaswintergritting,urbanwastecollectionandpostdelivery.Usuallythetransportationcostofvehiclesisamajorcomponentofthetotalcostforcapacitatedarcroutingproblem.Thereforeitcannotonlyeffectivelyreducecostbutalsoimproveservicelevels.Atthesametime,itcanreducethescatteredfreightratethroughtheoptimizationofvehiclerouting.Inmoststudyofcapacitatedarcroutingproblem，aconditionhasalwaysbeendefinedthatonecustomermustbeservicedbyonlyonevehicle.Ofcourse，inthisproblemthedemandofonecustomerislessthanthecapacityofonevehicle.However，sometransportationcostsavingcouldbeobtainedbysplittingthedemandofcustomerswiththeservicerequirementsatisfiedinrealsociety，especiallywhenamajorityofcustomers