一种求解多目标车辆路径问题的遗传算法研究

《一种求解多目标车辆路径问题的遗传算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据公迷昙／J大-了UDC密级学位论文一种求解多目标车辆路径问题的遗传算法研究作者姓名：于丰源指导教师：：三洪峰副教授咏北大学信息科学与工程学院申请学位级别：硕士学科类别：工学学科专业名称：系统工程论文提交日期：2014年6月论文答辩日期：2014年6月学位授予日期：2014年7月答獭蝴：雒兴刚评阅人：匀主关蹦勃起鳓奎浆、东北大学2014年6月万方数据AThesisinSystemEngineering

2、lIllllll[1llIIlUlIIlY2995043ResearchesonGeneticAlgorithmforMulti-·ObjectiveVehicleRoutingPro

3、blemByYuFengyuanSupervisor：AssociateProfessorWangHongfengNortheasternUniversityJune2014万方数据独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。学位论文作者签名：／碎砖日期：加f饵／闷学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保留并

4、向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年∥一年口一年半口两年口学位敝作者虢拼娲签字日期：力f啤饵导师躲王液吼签字吼功1乍匀多月万方数据东北大学硕士学位论文摘要一种求解多目标车辆路径问题的遗传算法研究摘要车辆路径问题(Vehicleroutingproblem，VI冲)是一个经典的运筹学问题，它是指若干个客户各自有着不同的货物需求，若干个配送中心向客户提供货物，由车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的

5、约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。VRP问题在科学和工程应用领域具有非常广泛的应用，很多实际的物流运输问题都可以转化成各种VRP问题来进行解决。由于VRP已经被证明是NP难的，所以对于大规模VRP问题往往考虑利用各种智能优化算法来进行求解。随着经济的发展、科学技术的进步以及人们需求的日益多元化，越来越多实际应用问题往往需要考虑多个优化目标，多目标优化正在成为近年来运筹学领域一个研究热点。需要注意的是目前关于多目标VRP问题的研究文献并不多，在很多方面尤其是求解算法设计方面亟需开展进一步深入的研究。本文采纳系统工程的思想，利用运筹学、进化计算等领域的相关研究成果，设计和

6、开发一种能够有效求解多目标VRP问题的遗传算法(Geneticalgorithm，GA)。本文的主要内容可以归纳如下几个方面：(1)相关工作综述部分。主要介绍了VRP问题及求解算法、多目标优化理论与方法等方面的研究工作。(2)问题建模部分。在给出一般VRP以及带有时间窗约束VRP问题数学模型的基础上，建立一个以最小化配送成本和最大化客户满意度为目标函数的多目标VRP问题的数学模型。(3)算法设计部分。研究一般VRP问题的求解算法，考虑到编码和解码是求解VRP问题的GA设计中所面临的主要挑战，对三种不同编码方法的有效性进行对比仿真实验。在上述研究结论的基础上，通过结合一种经典多目标进化算法(

7、MOEA／D)的相关思想，提出一种能够求解多目标VRP问题的新型多目标GA算法。(4)仿真实验部分。利用一组根据VRPLIB中标准测试问题构造的多目标VRP问题，对所提出的多目标GA算法进行仿真实验以检验其性能。此外，还在仿真实验中分析所提出的算法中关键参数及算子对算法性能的影响。TT万方数据东北大学硕士学位论文摘要(5)结论部分。对本文研究的主要工作进行总结，指出存在的不足之处，并对下一步的研究工作进行展望。关键词：车辆路径问题；多目标优化问题；遗传算法；多目标进化算法III万方数据东北大学硕士学位论文AbstractResearchesonGeneticAlgorithmforMult

8、i—-ObjectiveVehicleRoutingProblemAbstractAsoneofclassicalORproblems，vehicleroutingproblem(VRP)canbedescribedasoneoffindingasetofroutesforafleetofvehicleswhichhavetoserviceanumberofcustomerswithdifferentdemandquan