改进遗传算法在软时间窗车辆路径问题中的应用

《改进遗传算法在软时间窗车辆路径问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：______________密级：______________ＵＤＣ：______________单位代码：______________安徽工业大学硕士学位论文论文题目：改进遗传算法在软时间窗车辆路径问题中的应用学号：20100329作者：魏凯专业名称：管理科学与工程2013年6月4日万方数据安徽工业大学硕士学位论文论文题目：改进遗传算法在软时间窗车辆路径问题中的应用UsingImprovedGeneticAlgorithmtoSolveVehicleRoutingProblemwithSoftTimeWindows作者：魏凯学院：

2、管理科学与工程学院指导教师：郜振华单位：安徽工业大学协助指导教师：单位：单位：论文提交日期：2013年6月4日学位授予单位：安徽工业大学安徽马鞍山：243002万方数据独创性说明本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得安徽工业大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。签名日期：____________关于论文使用授权的说

3、明本人完全了解安徽工业大学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文,保密的论文在解密后应遵循此规定。签名导师签名日期：万方数据安徽工业大学硕士学位论文摘要物流技术的发展有助于企业降低物流成本、提高客户满意度、提高运作效率，车辆路径问题的研究是提高物流技术的有效途径。近年来，人们开始逐渐把注意力转移到由实际生产生活衍生出的众多车辆路径问题上，并取得了大量优异的成绩，随之带来了巨大的经济效益。本文主要研究了带有软时间窗的车辆路

4、径问题，在对相关模型深入研究的基础之上建立了带有软时间窗的车辆路径问题模型，并对求解带软时间窗车辆路径问题的常用启发式算法进行了介绍。同时，本文在对遗传算法和模拟退火算法研究的基础上提出了一种改进遗传算法。该算法结合了遗传算法的全局搜索功能和模拟退火算法的局部搜索功能，试验结果显示改进遗传算法在功能上有显著的提高。在研究Solomon和Gehring标准算例的基础上设计出一个具有一般性的多车场算例，并求解出该算例。本文对算例的求解步骤是：(1)结合Sweep算法和Saving算法把多车场化为单车场，弥补了单纯用Sweep算法的不足。(2)利

5、用LINGO软件分配可供车场使用的车辆，得到了满足运输要求下车辆使用费用最低的分配方案。(3)在求解具体车辆路径问题时，利用改进扫描法进行具体分派。该改进扫描法最大限度的使用计算机的运算能力，尽量使车场的信息不被破坏，这样得到最终的顾客点分配较使用传统扫描法优秀。(4)运用C++编程和改进遗传算法对分解后的系统进行求解，得到了每辆车的运行路线和费用值，显示了改进遗传算法的优越性。关键词：车辆路径问题；时间窗；改进遗传算法；模拟退火算法；Sweep算法；Saving算法I万方数据安徽工业大学硕士学位论文AbstractTheimproveme

6、ntoflogisticstechnologyishelpfultoreducethelogisticalcost,enhancethecustomersatisfaction,andimprovetheoperationefficiency.TheresearchofVehicleRoutingProblemisanimportantmeasuretoimprovelogisticstechnology.Inrecentyears,researchersarefocusedonamassofbranchesofvehiclerouting

7、problem,whicharederivedfromreal-worldapplications,andagreatdealofresearchresultsandeconomicalbenefitshavebeengained.ThemainresearchofthisthesisisVehicleRoutingProblemwithsofttimewindows,andamodelofvehicleroutingproblemwithsofttimewindowsisbuiltbylearningsomerelevantmodels.

8、Someusualheuristicalgorithms,whichareusedtosolvevehicleroutingproblemwithsofttimewindowsa