用遗传算法解决车辆优化调度问题.doc

I摘要近年来，物流作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大的发展。在高度发展的商业社会中，传统的VSP算法已无法满足顾客需求对物流配送提出的要求，于是时间窗的概念应运而生。带有时间窗的车辆优化调度问题是比VSP复杂程度更高的NP难题。本文在研究物流配送车辆优化调度问题的基础上，对有时间窗的车辆优化调度问题进行了分析。并对所采用的遗传算法的基本理论做了论述。对于有时间窗的非满载VSP问题，将货运量约束和软时间窗约束转化为目标约束，建立了非满载VSP模型，设计了基于自然数编码，使用最大保留交叉、改进的反转变异等技术的遗传算法。经实验分析，取得了较好的结果。由于此问题为小组成员共同研究，本文重点论述了本人完成的关于适应度函数和变异操作的部分。关键词：物流配送车辆优化调度遗传算法时间窗IIAbstractRecentyears,logistics,takenasthirdprofitresource”,hasbeendevelopingrapidly.Inthedevelopedcommercialsociety,traditionalVSPalgorithmhavebeenunabletomeettherequirementthatQuickResponsetocustomerdemandhadbroughtforth,thentheconceptionofTimeWindowhascomeintobeing.Thevehicle-schedulingproblemwithtimewindowisalsoaNP-hardproblembeingmorecomplicatedthanVSP.Thistexthasbeenresearchedtothevehicle-schedulingproblemwithtimewindowonthebasisofresearchedtologisticvehicleschedulingproblem.Andithasexplainedthebasictheoryofgeneticalgorithm.OntheVSPwithtimewindow,whiletherestraintsofcapacityandtimewindowsarechangedintoobjectrestraints,amathematicmodelisestablished.Weusetechniquesuchasmaximumpreservedcrossoveranddesigngeneticalgorithmonnaturenumber,whichcandealwithsofttimewindowsthroughexperimentalanalysis,havemadebetterresult.Becausethisproblemwasstudiedtogetherforgroupmembers,thistexthasexpoundedthepartaboutfitnessfunctionandmutationoperatorthatIfinished.Keywords:logisticdistributionvehicleschedulingproblemgeneticalgorithmtimewindowsIII目录摘要.IAbstract.II目录.III引言.1第1章概述.21.1研究背景.21.2物流配送车辆优化调度的研究动态和水平.41.2.1问题的提出.41.2.2分类.51.2.3基本问题与基本方法.61.2.4算法.61.2.5货运车辆优化调度问题的分类.81.3研究的意义.91.4研究的范围.10第2章有时间窗的车辆优化调度问题(VSPTW).112.1时间窗的定义.112.2VSPTW问题的结构.13第3章遗传算法基本理论.143.1遗传算法的基本原理.143.1.1遗传算法的特点.143.1.2遗传算法的基本步骤和处理流程.153.1.3遗传算法的应用.163.2编码.173.2.1二进制编码.183.2.2Gray编码.183.2.3实数向量编码.183.2.4排列编码.19IV3.3适应度函数.193.3.1目标函数映射成适应度函数.193.3.2适应度定标.203.4遗传算法的基因操作.213.4.1选择算子.213.4.2交叉算子.223.4.3变异算子.253.5遗传算法控制参数设定.28第4章遗传算法求解有时间窗非满载VSP.304.1问题描述.304.2数学模型.314.2.1一般VSP模型.314.2.2有时间窗VSP模型.324.3算法设计.334.3.1算法流程图.334.3.2染色体结构.334.3.3约束处理.354.3.4适应度函数.364.3.5初始种群.364.3.6遗传算子.364.3