用遗传算法解决车辆优化调度问题-免费毕业设计论文

PAGEPAGE47摘要近年来，物流作为“第三方利润的源泉”受到国内各行业的极大重视并得到了较大的发展。在高度发展的商业社会中，传统的VSP算法已无法满足顾客需求对物流配送提出的要求，于是时间窗的概念应运而生。带有时间窗的车辆优化调度问题是比VSP复杂程度更高的NP难题。本文在研究物流配送车辆优化调度问题的基础上，对有时间窗的车辆优化调度问题进行了分析。并对所采用的遗传算法的基本理论做了论述。对于有时间窗的非满载VSP问题，将货运量约束和软时间窗约束转化为目标约束，建立了非满载VSP模型，设计了基于自然数编码，使用最大保留交叉、改进的反转变异等技术的遗传算法。经实验分析，取得了较好的结果。由于此问题为小组成员共同研究，本文重点论述了本人完成的关于适应度函数和变异操作的部分。关键词：物流配送车辆优化调度遗传算法时间窗

AbstractRecentyears,logistics,takenas"thirdprofitresource”,hasbeendevelopingrapidly.Inthedevelopedcommercialsociety,traditionalVSPalgorithmhavebeenunabletomeettherequirementthatQuickResponsetocustomerdemandhadbroughtforth,thentheconceptionofTimeWindowhascomeintobeing.Thevehicle-schedulingproblemwithtimewindowisalsoaNP-hardproblembeingmorecomplicatedthanVSP.Thistexthasbeenresearchedtothevehicle-schedulingproblemwithtimewindowonthebasisofresearchedtologisticvehicleschedulingproblem.Andithasexplainedthebasictheoryofgeneticalgorithm.OntheVSPwithtimewindow,whiletherestraintsofcapacityandtimewindowsarechangedintoobjectrestraints,amathematicmodelisestablished.Weusetechniquesuchasmaximumpreservedcrossoveranddesigngeneticalgorithmonnaturenumber,whichcandealwithsofttimewindowsthroughexperimentalanalysis,havemadebetterresult.Becausethisproblemwasstudiedtogetherforgroupmembers,thistexthasexpoundedthepartaboutfitnessfunctionandmutationoperatorthatIfinished.Keywords:logisticdistributionvehicleschedulingproblemgeneticalgorithmtimewindows

目录摘要 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排列编码 193.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.7控制参数和终止条件 374.4算法实现 394.5实验及结果分析 394.5.1控制参数选定 394.5.2实例实验 434.5.3实例数据 444.5.4实例数据分析 44结论 45参考文献 47谢辞 48引言随着市场经济的发展，大量经营规模较大的制造企业和商业企业纷纷建立起配送中心向商品流通效率化发起挑战，与此同时，相当部分的大型运输、仓储和航运企业开始转向第三方物流经营。此外，我国具有强大物流配送资源优势的邮政业更是在递送包裹的基础上为企业、商家和电子商务网站积极开展配送业务。物流配送开始在我国迅速兴起发展起来，对物流配送的研究引起了国内物流专家学者的广泛关注。目前国内采用遗传算法解决物流配送的车辆优化调度问题的研究还处在起步阶段。本文针对客户提出时间约束这一配送需求，对有时间窗的物流配送车辆优化调度问题（VSPTW）进行数学分析，研究探索性能更强的解决VSPTW的遗传算法。本文第1章研究目前物流配送车辆优化调度问题的研究动态和水平；第2章进一步研究有时间窗的物流配送车辆优化调度问题；第3章阐述和研究所采用遗传算法的基本理论；第4章详细论述如何采用遗传算法解决有时间窗的物流配送车辆优化调度问题并通过实验数据分析所采用改进的遗传算法的性能。第1章概述1.1研究背景随着社会主义市场经济的发展，在经济大循环中提高经济运作效率的物流对经济活动的影响日益明显，越来越引起人们的重视。据中国物流信息中心统计测算，2004年，全国社会物流总额达38.4万亿元，同比增长29.9%(按现价计算)，增幅比上年同期提高2.9个百分点。虽然我国物流发展持续加速，但与国民经济发展的要求还相差甚远，这就要求我们对物流产业的各个环节进行研究。配送是物流中一个重要的直接与消费者相连的环节。我国国家标准《物流术语》中对配送的定义是：“在经济合理区域范围内，根据用户要求，对物品进行拣选、加工、包装、分割、组配等作业，并按时送达指定地点的物流活动［７］。”配送是在集货、配货基础上，按用户要求，包括种类、品种搭配、数量、时间等方面的要求所进行的运送，是“配”和“送”的有机结合形式，其主要功能是输送。配送的流程一般如下图所示。用户工厂进货送货集货存储配货车辆配装图1-1配送流程图在传统的配送系统中，由于商品的需求量及种类较少，零售商可凭借较多的存货及较常的定货周期来减少供货商的配送频率，以降低运输成本。但是在现代的配送系统中，零售商为了减少资金积压及提供多样化的商品，势必要减少各种商品的存货数量，而同时又必须考虑到提供最好的服务品质(不允许缺货)。物流中心的功能就在于对商品的仓储与运输进行有效的统筹规划以降低配送成本。所谓“物流中心”，根据美国物流管理协会(TheCouncilofLogisticsManagement,CLM)定义：“以适合顾客要求为目的，对原物料、在制品、制成品与其相关信息，从产地到消费者的间的流程与保管，为求有效率且最小的机会成本，而进行计划、执行、控制的场所(Depot)”。在物流配送系统中，物流配送中心的成立可有效的简化配送程序与减少配送的频率，以i个供应商和j个零售商为例，传统的配送模式是假设j个零售商的需求都是由i个供应商自行配送，则一共有i×j次的运送，如图1-2所示。假设零售商与供应商之间通过一个物流配送中心来配送，则只需i+j次配送，如图1-3所示，如此一来即可减少(i×j-(i+j))的配送次数，当供应商与零售商数目越多，节省的配送次数也就会越多。供应商（S）零售商（R）图1-2传统的物流配送模式物流中心配送作业的重点是如何将车辆有效的使用并决定其最经济的行驶路线图，使商品能在最短的时间内送到顾客的手中。国外将此类问题称之为VehicleSchedulingProblem，简称为VSP问题。该问题一般定义为:对一系列装（卸）货点，组织适当的行车线路，使车辆有序的通过它们，在满足一定的约束条件(如货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制、时间限制等)下，达到一定的目标(如路程最短、费用最少、时间尽量少、使用车辆数尽量少等)［３］。供应商（S）供应商（S）零售商（R）物流中心图1-3以物流中心为主的配送模式1.2物流配送车辆优化调度的研究动态和水平1.2.1问题的提出物流配送车辆优化调度问题最早是由Dantzig和Ramser于1959年首次提出，自此，很快引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科的专家与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿与研究热点问题。各学科专家对该问题进行了大量的理论研究及实验分析，取得了很大的进展。国外对物流配送车辆优化调度问题作了大量而深入的研究，例如早在1983年Bodin,Golden等人在他们的综述文章中就列举了700余篇文献。在Christofides(1985)，Golden和Assad(1988)编辑的论文集，以及Altinkermer和Gavish(1991)，Laporte(1992)，Salhi(1993)等的综述文章中都进行了详尽阐述。该领域的代表人物有Bodin，Christfids，Golden，Assad，Ball，Laporte，RinnooyKan，Lenstra，Desrosiers和Desrochers等人［１］［３］。国内对物流配送车辆优化调度问题的研究相当少，主要研究对象是旅行商问题(TravelingSalesmanProblem，简称TSP)、中国邮递员问题(ChinesePostmanProblem,简称CPP)、有向中国邮递员问题(DirectedChinesePostmanProblem，简称DCPP)等，系统性研究还尚未见到。李大为等(1998)以TSP的最近距离启发式为基础，通过设置评价函数来处理时间窗约束，求解了简单的VSP。张震(1995)针对单车场满载问题，提出了考虑运输行程约束的优化方法。遗传算法和神经网络方法对简单TSP的求解取得了一定成果。蔡延光等(1998)应用并行表搜索法和模拟退火法针对简单情形对满载问题进行了求解［３］［５］。目前，问题的形式己有很大发展，该问题以不仅仅局限于汽车运输领域，在水运、航空、通讯、电力、工业管理、计算机应用等领域也有一定的应用，其算法己用于航空乘务员轮班安排、轮船公司运送货物经过港口与货物安排的优化设计、交通车线路安排、生产系统中的计划与控制等多种组合优化问题。1.2.2分类VSP被提出后，Linus(1981),Bodin和Golden(1981),Bodin(1983),Assad(1988),Desrochers,Lenstra和Savelsbergh(1990)等许多学者对VSP从不同角度，按不同的标准进行了分类。按任务特征分，有纯装问题或纯卸题(purepickuporpuredelivery,车辆在所有任务点装货或卸货，及集货或送货问题)及装卸混合问题(combinedpickupanddelivery，每项任务有不同的装货点和卸货点，即集货、送货一体化问题)。按任务性质分，有对弧服务问题(如中国邮递员问题)和对点服务问题(如旅行商问题)以及混合服务问题(如交通车线路安排问题)。按车辆载货状况分，有满载问题(货运量不小于车辆容量，完成一项任务需要不只一辆车)和非满载问题(货运量小于车辆容量，多项任务用一辆车)。按车场(或货场、配送中心等)数目分，有单车场问题和多车场问题。按车辆类型数分，有单车型问题(所有车辆容量相同)和多车型问题(执行任务的车辆容量不完全相同)。按车辆对车场的所属关系分，有车辆开放问题(车辆可以不返回其发出车场)和车辆封闭问题(车辆必须返回其发出车场)。按优化目标数来分，有单目标问题和多目标问题。由于情况的不同，车辆优化调度问题的模型构造及算法有很大的差别。1.2.3基本问题与基本方法为简化货运车辆优化调度问题的求解，常常应用一些技术将问题分解或转化成一个或几个已经研究过的基本问题，再用相应比较成熟的基本理论和方法，以得到原货运车辆优化调度问题的最优解或满意解。常用的基本问题有：旅行商问题、分派问题、运输问题、背包问题最短路问题、最小费用流问题、中国邮路问题等。常用的基本理论和方法有：分枝界定法、割平面法、线性规划法、动态规划法、匹配理论、对偶理论、组合理论、线搜索技术、列生成技术、概率分析、统计分析、最差情况分析、经验分析等。1.2.4算法货运车辆优化调度问题的求解方法非常丰富，目前主要有以下四类：1、系统仿真法(Simulation)此方法最早由Golden和Skiscim于1986年提出，主要应用于行车线路与物流中心区位的选择，优点在于可直接观察系统安排的效率与效果，但由于问题的实际情况多变且具有不确定性，是否能将实际的配送情形系统逻辑化为仿真程序，往往令人质疑。2、人机互动法此方法结合人类决策与计算机计算能力，在求解的过程中，通过高度的人机交互模式，结合专家的决策信息，并据以计算出结果；优点是寻优的过程中，决策者可以很清楚地看到各约束条件之间的替代关系，以及参数变化可能导致的成本变化。3、精确解法(Exactprocedures)精确解法指可求出最优解的算法，精确解法主要有：分枝界定法(BranchandBoundApproach)、割平面法(CuttingPlanesApproach)、网络流算法(NetworkFlowApproach)、动态规划方法(DynamicProgrammingApproach)。精确算法的计算量一般随着问题规模的增大呈指数增长。4、启发式解法(Heuristics)由于上述三种方法的求解效率较差，所以大部分的学者都致力于启发式解法的发展。该方法在解题时可减少搜寻的次数，所以是一种容易且快速的求解困难问题的算法。目前已提出的启发式算法很多，按CesarRego的分类法有以下四类：（1）算法(ConstructiveAlgorithm)根据一些准则，每一次将一个不在线路上的点增加进线路，直到所有的点都被安排进线路为止。该类算法的每一步，把当前的线路构形（很可能是不可行的）跟另外的构形（也可能是不可行的）进行比较并加以改进，后者是根据某个判别函数（例如总费用）会产生最大限度的节约的构形，或是以最小代价把一个在当前构形上的需求对象插入进来的构形(Clarke和Wright，1964；Mole和Jamesson，1976；Paessens，1988；Altinkemer和Gavish，1991；Desrochers和Verhoog，1989)。构造算法是最早提出用来解决旅行商问题(TravelingSalesmanProblem,简称TSP)及VSP的，这些方法一般速度快，也很灵活，但这类方法有时找到的解离最优解差的很远。（2）阶段法(Two-phaseAlgorithm)两阶段法是：第一阶段得到一可行解，第二阶段通过对点的调整，在始终保持解可行的情况下，力图向最优目标靠近，每一步都产生另一个可行解以代替原来的解，使目标函数值得以改进，一直继续到不能再改进目标函数值为止(Gillett和Miller，1974；Christofids、Mingozzi和Toth，1979；Fisher和Jaikumar，1981；Renaud、Boctor和Laporte，1996；Bramel和Simchi-Levi，1995)。一般第一阶段常用构造算法，在第二阶段常用的改进技术有2-opt(Lin，1965)、3-opt(LinKernighan，1973)和Or-opt(Or，1976)交换法，这是一种在解的邻域中搜索，对初始解进行某种程度优化的算法，以改进初始解。在两阶段法求解过程中，常常采用交互式优化技术，把人的主观能动作用结合到问题的求解过程中，其主要思想是：有经验的决策者具有对结果和参数的某种判断能力，并且根据知识直感，把主观的估计加到优化模型中去。这样做通常会增加模型最终实现并被采用的可能性。（3）不完全优化算法(IncompleteOptimizationAlgorithm)以启发式准则来代替精确算法中的决策准则，以缩小解搜索的空间(Toth、Christofides和Mingozzi，1979等)。（4）改进算法(ImprovementAlgorithm)从一个初始解开始，通过对当前的解进行反复地局部扰乱(Perturbations)以达到较好的解。基于启发式的并行算法和一些称为亚启发式算法(Metaheuristics、Laporte和Osman，1996)的方法都属于此类(CesarRego，1998；Gendrea、Laporte和Potvin，1994)［８］。亚启发式算法包括表搜索算法(TableSearch)、模拟退火算法(SimulatedAnnealing)、遗传算法(GeneticAlgorithm)和神经网络(NeuralNetworks)方法。1.2.5货运车辆优化调度问题的分类根据任务的性质将货物运输分成以下几类：1、非满载车辆优化调度问题当货物量小于车辆容量时，用一辆车执行任务，存在不满载运行情况，调度时可安排一辆车执行多项任务，即在一辆车上同时载有不同货主的货物。该类问题根据任务特征又分为以下两类：（1）集货或送货的车辆优化调度所有任务全是集货点或全是送货点，车辆空车从车场出发，去各货主处装满货后返回车场。这种情况下，货运量总数不超过车辆容量的任务可用一辆车来完成。（2）集货和送货一体化的车辆优化调度每一项货运任务都有自己的集货点和送货点，车辆从车场出发，去某一任务的集货地点装货后运至其送货地点卸货（即装卸混合），完成所有任务后返回车场。2、满载车辆优化调度问题当货主的货物量不小于车辆容量时，执行每项任务需要的车辆可能不只一辆，车辆为完成任务，需满载运行。根据任务特征可分为以下两类：（1）集货或送货的车辆优化调度载货车辆由车场出发到几个集货点装货后返回车场（仅有装货），或是车辆出发到几个送货点卸货（仅有卸货）后返回车场。（2）集货和送货一体化的车辆优化调度每一项货运任务都有自己的集货点和送货点，各项任务需要的车辆数不一致，这时需要对车辆进行优化调度，确定行车路线。1.3研究的意义目前有关VSP的研究，多致力于单一车种或多车种优化调度问题，很少涉及结合时间窗口的VSP问题。所谓时间窗口是指配送车辆或顾客希望服务或被服务的时间范围。由于消费者需求趋于多样化，对送货时间的要求日趋严格，尤其是运送有时效性的商品，例如海鲜、花卉、蔬菜、水果等讲究新鲜度的货物，除了因缺货造成的机会成本的损失外，由于配送不及时也会造成货物价值的大大降低。因此，在配送运输上，时间因素是十分重要的。有时间窗的VSP问题也称为VSPTW(VehicleSchedulingProblemwithTimeWindows），根据时间约束的严格与否，分为软时间窗和硬时间窗的VSP。由于有时间窗的VSP是典型的NP—难题，会随着节点的增加出现组合爆炸的现象，因此求解的困难度及时效性会有影响。1.4研究的范围由于有时间窗约束的车辆优化调度问题所牵涉的因素相当多，本研究仅针对具有普遍性的物流中心予以探讨，就研究范围与假设界定如下：1、仅考虑区位己知的单一物流配送中心和供应商；2、物流配送中心无缺货的可能，而且商品种类单一；3、物流配送中心已知顾客的基本配送资料(需求量、地理位置、时间窗约束等)；4、物流配送中心拥有足够数量的同类型配送车辆，即每辆车的载重量、时速相同。

第2章有时间窗的车辆优化调度问题(VSPTW)2.1时间窗的定义VSPTW问题是传统的车辆优化调度问题加上时间窗约束，时间窗约束可分为硬时间窗、软时间窗与混合型时间窗。三者分述如下：1、硬时间窗(HardTimeWindows)：指配送车必须在特定时间区段(如图2-1中的)内将货品送达顾客手中，不论是迟到或早到都完全不予接受。图2-1为一惩罚函数(PenaltyFunction)当货品送达时间超出时，其惩罚值等于一个非常大的正值，表示硬时间窗的限制。Desrochers(1988)曾指出硬时间窗宽度会影响寻优程序，并提出时间窗宽度评价指标，时间窗越宽则VSPTW问题越接近路线安排(Routing)问题，越窄则越近似行程安排(Scheduling)问题。图2-1硬时间窗约束示意图2、软时间窗(SoftTimeWindows)：指配送车辆如果无法将货物在特定的时段(如图2-2的)内送到顾客手中，则必须按照违反时间的长短施以一定的罚金或其它惩罚法则。图2-2就是一种可能的惩罚函数。图2-2软时间窗约束示意图3、混合型时间窗(MixedTimeWindows)：系统中有些顾客属于硬时间窗，有些则属于软时间窗；同一顾客，往往软、硬两种时间窗混合使用。在实际的物流配送中，配送车辆如果能在最佳时段(如图2-3中的内将货物送到顾客处，则不处罚；若在图2-3中的（或）时段内才送达，则顾客的满意度降低(转化为惩罚函数)，而且顾客不接受上述两个时段以外的时间（或）收货。图2-3混合型时间窗约束示意图2.2VSPTW问题的结构时间窗约束的车辆优化调度问题是在传统的车辆优化调度问题的基础上再加入顾客的时间窗约束，所以该问题包含以下三项关键问题：1、巡回(Routing)问题一般车辆优化调度问题中的配送车辆由配送中心出发后，必须完成其所指派客户的配送，然后回到配送中心。所以对每一部车辆来说，是一个旅行商问题(TSP)。2、装载(Loading)问题因为每一配送车辆都有规定负荷的载重量限制，所以在TSP问题中加入配送车辆的装载量限制，此时的问题成为一般车辆优化调度问题。3、行程安排(Scheduling)问题一般车辆优化调度问题再加入时间窗约束，则必须考虑到达各顾客的先后顺序，也就是行程安排问题。有时间窗约束的车辆优化调度问题可以用图2-4表示：旅行商问题旅行商问题一般车辆优化调度问题有时间窗约束的车辆优化调度问题加入车辆装载能力约束加入时间窗约束图2-4VSPTW问题的结构第3章遗传算法基本理论3.1遗传算法的基本原理遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，它由美国Holland教授首先在《自然结合人工智能系统的适应性》一书中提出，是利用生物进化的特性所发展的方法，由一群群体(Population)以随机配对产生下一代，利用交叉(Crossover)及变异(Mutation)等操作进行基因的进化，并经由选择(Selection)机能决定下一代相对的个数，使适应度越大的解存活的机会越大；也就是“适者生存”的原则来选择随机的值域，最后留下的就是最优解。3.1.1遗传算法的特点同传统的寻优算法相比，遗传算法具有以下特点：1、算法对问题参数的代码集起作用，而不是对参数本身起作用。遗传算法处理的对象是染色体，因而要求把所要优化问题的基本参数转化成一定长度的有限符号的染色体。2、遗传算法是从初始群体开始搜索的，而不是从单点开始搜索的。许多传统优化方法都是从搜索空间的单点出发，通过某些转换规则确定下一点。这种点到点的搜索方法在多峰值优化问题中，容易误入局部最优解。遗传算法是以点集开始的寻优过程，初始群体是随机地在搜索空间中选取的，覆盖面大，利于全局寻优。3、遗传算法在求解时只使用适应度函数的信息，而不使用导数及其他辅助信息。对于不同类型的优化问题，传统方法需要使用不同形式的辅助信息，没有一种优化方法能适应各类问题的要求。遗传算法在优化过程中，放弃使用这些辅助信息，具有广泛适应性。4、算法具有极强的容错能力。遗传算法的初始种群本身就带有大量与最优解甚远的信息，通过选择、交叉、变异操作能迅速排除与最优解相差极大的染色体。5、算法具有隐含的并行性。Goldeberg对GA的处理并行性进行了合理的分析，指出了GA对模式的处理效率是，Holland称之为GA的“隐式并行性”［５］。6、遗传算法中的选择、交叉、和变异都是随机操作，而不是确定的精确规则。复制体现了向最优解的逼近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。与传统方法相比，遗传算法的优越性主要表现在：首先，在遗传算子的作用下，遗传算法具有很强的搜索能力，能以很大的概率找到问题的全局最优解：其次，由于它固有的并行性，能有效地处理大规模的优化问题。3.1.2遗传算法的基本步骤和处理流程遗传算法的主要处理步骤是：首先构造满足约束条件的染色体。编码的目的主要是使优化问题解的表现形式适合于遗传算法中的遗传运算。实际问题的染色体有多种编码方式，染色体编码方式的选取应尽可能的符合问题约束，否则将影响计算效率。第二是随机产生初始群体。初始群体群体的染色体数量应适当选择。第三是是适应度函数的构造和应用，计算每个染色体适应度。适应度函数基本上依据问题的目标函数而定，是反映染色体优劣的唯一指标，遗传算法就是要寻得适应度最大的染色体。当适应度函数确定以后，复制是以适应度函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰。第四是染色体的交叉。父代的遗传基因的结合是通过父代染色体之间的交叉并到达下一代个体的。子代的产生是一个生殖过程，它产生了一个新解；最后是变异，新解产生过程中可能产生基因变异，变异使某些解的编码发生变化，使解具有更大的遍历性。遗传算法的基本流程如图3-1所示。问题问题确定表示问题解答的染色体（编码）初始化染色体种群计算每个染色体的适应度满足终止条件？根据适应度选择串进行复制交叉变异输出最优解否是图3-1遗传算法的基本流程3.1.3遗传算法的应用遗传算法是60年代由美国J.Holland教授首先在《自然结合人工智能系统的适应性》一书中提出的，是一种新兴的自适应随机搜索方法，具有极强的鲁棒性和内在的并行计算机制，特别适合于非凸空间中复杂的多极值优化和组合优化，在机器学习、自动控制、机器人技术、电器自动化以及计算机和通信领域以取得了非凡的成就。遗传算法的应用总的来说可以分为如下三大类：1、优化计算优化计算是遗传算法最直接的应用，应用面也最广。对于复杂的函数优化问题(如非线性、不连续、多峰值函数的优化等)和组合优化问题(如VSP,TSP,0-1背包问题、工作计划制定等)都有广阔的发展前景。目前在运筹学、机械优化设计、电网设计、生产管理等应用学科中都尝试着用遗传算法解决现实优化计算问题。2、机器学习基于遗传算法的机器学习也是遗传算法应用研究的一个重要方面。机器学习是为解决专家系统设计中的知识获取瓶颈问题而设计的。遗传算法从其开始就与机器学习有着密切的联系。分类器CS-1是Halland与Keitman实现的第一个基于遗传算法的机器学习系统。3、神经网络遗传算法的另一个活跃的研究方向是在神经网络方面的应用，这包括优化神经网络的连接权系数、网络的空间结构等。遗传算法与神经网络的相结合应用于机械设计、结构优化、决策分析。近些年来，人们在用遗传算法解决现实中的各种组合优化问题上进行了探索，如在生产调度问题中的应用、对一般TSP(TravelingSalesmanProblem,旅行商问题)问题的求解都取得了一些成果(Oliver和Smith,1989:Fogel,1993)。但在VSP中的应用才刚刚开始，已有文献利用遗传算法对VSP进行求解(Berthold,1995;Malmborg,1996;Ochi和Luiz1998)，但仅仅是开始尝试阶段，还有待于进一步的研究。有专家断言遗传算法是用来解决NP完全问题和NP难题的趋势［８］。3.2编码将问题的解编码为染色体是用遗传算法解决各类问题的第一步，也是关键一步。编码方法决定了染色体的排列形式。它实际上确定了对问题的描述方式，直接影响到选择、交叉、变异这一系列基因操作，最终影响到整个遗传算法的性能。设计优良的编码方案是遗传算法的应用难点之一。下面是几种常用的编码方法。3.2.1二进制编码二进制编码是最常用的编码技术之一，许多数值与非数值优化问题的解都可以用二进制位串进行编码。二进制编码是将原问题的解空间映射到位串空间上，其中L为某个固定常数。二进制编码结构简单，易于进行交叉、变异等遗传操作。但也存在以下缺点：（1）相邻整数的二进制编码可能具有较大的Hamming距离。例如7和8的二进制编码分别为0111和1000.这一缺陷称为Hamming悬崖（Hammingcliffs）,有可能降低遗传算法的搜索效率。（2）在求解连续优化问题时，采用二进制编码，一般要预先给出解的精度以确定串长，而精度确定后难以在算法中调整。若在一开始就选取较高的精度，则串长很大，也会降低算法的效率。（3）在求解多维高精度优化问题时，二进制编码将会非常长，从而降低算法效率。3.2.2Gray编码Gray编码的目的是为了克服二进制编码的Hamming悬崖缺陷。一个n阶Gray码是一个由所有n位二进制位串组成的有序循环序列，使得相邻的位串之间恰有一位不同。Gray编码的方法是首先对问题的解进行二进制编码，再将二进制编码转换为相应的Gray编码，然后进行遗传操作，当进行适应度计算时，再将Gray编码转换为相应的二进制编码。Gray编码可以有效的解决二进制编码的Hamming悬崖缺陷，但由于长度与二进制编码相同，因此同样存在二进制编码中（2）、（3）两项缺点。3.2.3实数向量编码在求解一些多维高精度优化问题时，二进制编码会占用大量的存储空间，而且使得搜索空间极其庞大，从而影响遗传算法的性能。因此当问题的解是实数向量时，可以直接采用实数向量编码。这样，可以直接在解的表现型上操作，从而便于引入与问题领域相关的启发式信息，增加遗传算法的搜索能力。3.2.4排列编码对于某些问题，排列是其解的一种自然的表示。例如旅行商问题（TSP）：选择一条商人遍历若干城市的最短路径。设共有n个城市，分别用来表示，每两个城市和之间的距离用表示，则商人的一次遍历路线可以用一个的全排列表示，该排列表示遍历路线。因此的全排列就可以作为TSP的染色体。3.3适应度函数在遗传算法中，适应度是用来区分群体中个体（问题的解）的好坏，适应度越大的个体越好，反之，适应度越小的个体越差。遗传算法正是基于适应度对个体进行选择，以保证适应性好的个体有机会在下一代中产生更多的子个体。适应度函数是用来区分群体中个体好坏的工具，是算法演化过程的驱动力，是进行自然选择的唯一依据。改变群体内部结构的操作都是通过适应度加以控制。在具体应用中，适应度函数的设计要结合求解问题本身的要求而定。3.3.1目标函数映射成适应度函数遗传算法适应度函数值作为染色体的性能指标，以及利用繁殖概率的大小来评估各染色体的优劣程度，多半以最大化为目标(亦即越大越好)；但是许多优化问题(比如物流配送VSP问题)是求取费用函数的最小值，必须将目标函数转化为求最大值形式己得到适应度函数，而且保证适应度函数非负。一般可采用以下的方法进行转换：其中MAX为一常数，最好与群体无关，一般可以由下列四种方式决定:1、任意足够大的正数。2、目前所出现最大的目标函数值。3、目前操作的群体中，最大的目标函数值。4、目前遗传世代中，最后n代出现的最大的目标函数值。适应度函数一般要求非负，上述适应度函数的转换方法并不能保证后代的适应度函数值为正数，一旦在遗传过程中出现了比MAX更大的适应度函数值，就可能出现负的适应度，使复制算子失效。为了保证适应度函数为非负，可以采用如下的转化形式：3.3.2适应度定标在设计遗传算法时，群体的规模一般在几十至几百，与实际物种的规模相差很远。因此，个体繁殖数量的调节在遗传操作中就显得比较重要。如果群体中出现了超级个体，即该个体的适应度大大超过了群体的平均适应度，则按照适应度比例选择时，该个体很快在群体中占有绝对优势，从而导致算法较早的收敛到一个局部最优点。这种现象称为过早收敛。在这种情况下，应该缩小这个个体的适应度，以降低这些超级个体的竞争力，防止过早收敛。在另一方面，在搜索过程的后期，虽然群体中存在足够的多样性，但群体的平均适应度可能会接近群体的最优适应度。在这种情况下，群体中实际上已不存在竞争，从而搜索目标难以得到改善，出现了停滞现象。在这种情况下，应该放大个体的适应度，以提高个体之间的竞争力。这种对适应度的缩放调整称为适应度函数的定标。目前，主要的定标技术归纳成表3-1。表3-1遗传算法中适应度常用的定标方法定标方法方法描述线性定标将群体中各个体的适应度以线性关系缩放，这种方法控制每一代中表现最佳的个体复制数目，但当群体中个体适应度差异在定标前就己经有显著差异时，经由此法转换的新适应度可能会有负值产生，违背了概率不得为负数的限制，必须辅以其他方法处理。标准差祛除法此方法是利用平均适应度函数与其标准差间的差异来修正原个体的适应度，以解决线性定标会产生负值的问题，是线性定标前的一个预处理方法，但计算上比较复杂。级数定标将原来适应度函数值以接近1的次方来扩大各个个体间的差异。此方法在计算上的步骤上比较简易，但k的设定与问题的类型具有相关性。3.4遗传算法的基因操作3.4.1选择算子发展各种复制算子的目的是为了避免基因缺失，提高全局收敛性和效率。复制算子策略与编码方式无关，复制的主要思想是染色体的复制概率正比于其适应度。适应度比例方法是目前遗传算法中最基本也是最常用的复制方法，它也叫轮盘赌复制法或蒙特卡罗复制，其具体步骤如下：Stepl：对各个染色体计算适应度；Step2：计算种群中n个染色体适应度的和；Step3：对各染色体，计算选择概率；Step4：对各染色体计算累计概率复制过程类似旋转转轮n次，每次按如下方式选出一个染色体来构造新的种群，具体过程为：在区间内产生一个均匀分布的伪随机数r，若：，则选择第一个染色体；否则选择第k个染色体，使得成立。由于染色体复制后，当前群体中最佳染色体可能丧失繁殖能力，为了提高遗传算法的性能，可在使用轮盘赌的基础上采用最佳保留策略。3.4.2交叉算子交叉算子的作用是组合出新的个体，在串空间进行有效搜索，同时需降低对有效模式的破坏概率。交叉算子是遗传算法区别于其他进化算法的重要特征[5]。在交叉算子之前需首先配对，目前采用的是随机配对。采用二进制编码、实数编码和自然数编码时所采用的交叉策略不一样，其中自然数编码所采用的交叉策略有如下几种：1、部分映射交叉(PMX)PMX可看作二进制串的两点或多点交叉在自然数编码中的扩展，并应用修复程序来解决简单两点交叉引起的非法性。步骤如下：Stepl：在字串上均匀的选择两点，由这两点定义的子串称为映射段；Step2：交换双亲的两个子串，产生原始后代；Step3：确定两映射段之间的关系；Step4：根据映射关系将后代合法化。过程说明见图3-2。2、顺序交叉(ox)Stepl：从第一双亲中随机选择一个子串；Step2：将子串复制到一个空子串的相应位置，产生一个原始后代；Step3：删去第二双亲子串已有的城市，得到原始后代需要的其他城市的顺序；Step4：按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。过程说明见图3-3，同样步骤可用同一对双亲产生另一个后代[793456128]。随机选择子巡回随机选择子巡回123498765546938712双亲1：双亲2：交换双亲中的子串126998712543438765原始后代1：原始后代2：用映射关系将后代合法化后代1：后代2：356948712293468765确定映射关系691234651632594图3-2PMX运算的说明双亲1双亲1：574982631原始后代：**49***31双亲2：123498765后代：254982631图3-3OX运算的说明3、基于位置的交叉Stepl：从第一双亲上随机地选择一组位置；Step2：将这些位置复制到一个空子串的相应位置，产生一个原始后代；Step3：删去第二双亲上该组中已有的城市，剩下的城市构成了原始后代需要的顺序；Step4：按照这个城市顺序，从左到右将这些城市定位到后代的空缺位置上。图3-4说明了交叉过程，同样步骤可产生另一个后代[423156789]。双亲1双亲1：546387291原始后代：*4**8**91双亲2：123498765后代：243587691选择位置图3-4基于位置交叉运算的说明4、基于顺序的交叉是基于位置交叉的变型，其中一个双亲选定位置上的城市的顺序强制被另一双亲相应城市所代替。说明见图3-5。用同样的步骤可产生另一个后代[245316978]。双亲1：双亲1：546387291原始后代：4**189***双亲2：123498765后代：423189765选择位置图3-5基于顺序交叉运算的说明3.4.3变异算子当交叉算子产生的后代的适应度不在比前辈好又未达到最优解，就会产生不成熟收敛，不成熟收敛的根源是发生了有效基因缺失，这时，为克服这种情况，只有依赖于变异。变异在遗传算法中的作用是第二位的［３］［５］。目前发展的主要变异算子如表3-2所示。表3-2变异算子类型名称特点研究者适用编码常规位变异标准遗传算法成员DeJong二进制有效基因变异避免有效基因缺失Yun二进制自适应有效基因变异最低有效基因个数自适应变化Yun二进制概率自调整变异由两个串的相似性确定变异概率Whitley二进制均匀变异由一个实数元素以相同的概率在域内变动Michalewicz十进制非均匀变异使整个矢量在解空间轻微变动Michalewicz十进制三次高斯近似变异Bosworth,Foo,Zeigler十进制零变异同上十进制目前较常用的高级遗传算子，来源于群体遗传学。主要有以下四种：1、反转变异在染色体上随机地选择两点，将两点间的子串反转。说明如图3-6所示。随机选择子巡回随机选择子巡回543981762插入子巡回543781926图3-6反转变异的说明2、插入变异随机地选择一个城市，并将它插入到一个随机的位置中。过程示于图3-7中。随机选择一个城市随机选择一个城市543981762插入到一个随机位置543982176图3-7插入变异的说明3、易位变异随机地选择一个子巡回，并将其插入到一个随机的位置中，如图3-8中所示。随机选择一个子巡回随机选择一个子巡回543981762插入到一个随机位置543786291图3-8易位变异的说明4、k—交换变异k—交换变异是解决VSP的一种局域寻优技术，即对初始可行路线的k条边（或弧）进行交换，在初始可行解的邻域内逐步改进方案，直到在邻域内不能改进为止。这里说明一下2—交换和3—交换。将2—交换和3—交换作为遗传算法的变异算子，即在每代群体中以概率P，随机选取染色体上的两点或3点，进行2—交换或3—交换。2—交换和3—交换说明分别示于图3-9和图3-10中。随机选择两个位置随机选择两个位置543981762交换相应的城市546981732图3-92—交换变异的说明随机选择三个位置随机选择三个位置543981762交换相应的城市543986712546981732546983712541986732541983762图3-103—交换变异的说明3.5遗传算法控制参数设定遗传算法中需要选择的参数主要有染色体长度、群体规模n、交叉率、变异率等，这些参数对GA性能影响很大。为了选择合适的群体规模n、交叉率、变异率，许多学者进行了研究。通常认为：若种群过小，算法就有可能收敛于局部最优解，而不能收敛到最优结果或最优结果附近。这主要是种群规模过小，导致种群内个体多样性减小，从而可能丢失一些有意义的搜索点或最优点，然而种群过大，每次迭代所需要的计算量就会很大，这又可能导致一个无法接受的慢收敛率。一般，当种群规模增大时，将有利于改善种群的多样性，从而可能有利于使算法收敛到最优解或最优解附近。建议的最优参数范围是,,。但在某些情况下，当种群达到一定规模时，再增大种群规模，对搜索结果的改善并无多大帮助，甚至有可能变差。目前常用的参数范围是,，。由于控制参数会相互影响，所以无法确定独立的最佳参数值，但当种群规模小时可选择较大的交叉及变异率以防止过早收敛；当群体规模大时可选择较小交叉及变异率以节省运算时间。目前许多学者认识到这些参数需要随着遗传进程而自适应变化，这种有自组织性能的遗传算法具有更强的鲁棒性、全局收敛性和计算效率［９］［１０］。

第4章遗传算法求解有时间窗非满载VSP由于现在各任务需求点，如零售商店、连锁店等都尽可能的销售畅销商品，库存数量最好不要太多，且不能缺货，因此现在的物流配送一般是小范围、近距离、多品种、小批量、多批次、为多用户服务的经济活动，这时每个任务点的货物量小于车辆容量，用一辆车执行单一任务，属于非满载运行情况，在一辆车上同时装载有不同任务点的货物，所以物流配送车辆优化调度大部分是非满载车辆优化调度问题。时间窗约束下的物流配送运输在实际中是存在的，如某些特定的用户在断货时提出的紧急配送到货的时间要求、为饭店配送鲜活水产品、为有固定时刻表的火车、飞机等转运点送货以及超市配送用户要求送货不能太早于开门营业时间、也不能太晚于销售缺货时间等。有时间窗约束的车辆优化调度问题归结为车辆优化调度问题中的单车场、单车型、非满载、多约束（含时间窗约束）、多目标、车辆封闭的对点服务问题。该问题属于组合优化领域的NP难题［１１］，本小组尝试使用遗传算法求得该类问题的最优解或近似最优解。根据小组成员的分工，本文就适应度函数的选定和变异算子进行主要阐述。4.1问题描述一般车辆优化调度问题可描述为：一个物流配送中心使用载重量相同的多辆汽车完成多个货物需求点的配送任务。每个需求点(供货点)的需求量(供货量)已知，且都小于配送车辆的载重量；配送中心和各需求点中任意两点间的运距已知或可以推算出来；一个需求点的任务只能由一辆车一次运送完成；每个配送车辆从配送中心出发，完成运送任务后返回配送中心。求满足货运需求和车辆载重量的费用最小的车辆行使线路。在日常生活中和生产实际中，许多类似的问题都可以归结为这类问题。如一个中心货场需向几个顾客有运送货物，每个顾客对货物有一定的要求，运送货物的车辆在货场装满货后发出，把货送到各顾客处，完成任务后，返回货场，如何确定满足用户需求的费用最小的车辆行使路线，即送货车辆优化调度。又如，若干厂家生产一些产品，需要运到配送中心，车辆从配送中心出发，到各厂家去装货，装满货后返回配送中心，在满足厂家发货要求的情况下，按什么线路行驶，可使总费用最小，即集货车辆优化调度。有时间窗的VSP则是在一般车辆优化调度问题的基础上要求每项任务i在时间范围内完成，并可根据时间约束的严格与否，分为软时间窗和硬时间窗的VSP。由于有时间窗的VSP是典型的NP难题，会随着节点的增加出现组合爆炸的现象［５］。4.2数学模型4.2.1一般VSP模型物流配送中心拥有足够的载重量为q的车辆，现有n个需求点任务需要货物运输，以表示，已知第i个需求点的需要的货物量为，且。一般来讲，当问题的约束越多，组织线路就越难，一辆车所完成的满足所有约束的任务就越少，这时，一辆车实际所能容纳的任务量要小，而所用的车辆数可能要多。为了使线路安排具有一定的弹性，可预先估计一个完成任务所需要的车辆数m：(4-1)其中，[]表示不大于括号内数字的最大整数，是对装车或卸车的复杂性程度及约束多少的估计，一般来讲，装(卸)车越复杂，约束越多，应越小，表示一辆车所能承载的货物量越小。本算法采用人机对话来调整的大小。为构造数学模型方便，将物流配送中心编号为0，需求点编号为，则物流配送中心及需求点均以点来表示，完成配送任务共需要车辆数目为，每辆车的载重量为，每个需求点的需求量为，配送中心及各需求点中任意两点间的距离为，第k辆车的行车路径称为第k条子路径，其中经过的需求点数目为，表示第k条子路径中包含的个需求点组成的集合，其中的元素代表第k条子路径中顺序为i的需求点；均表示配送中心，且有。得到车辆优化调度数学模型如下：(4-2)，(4-3)(4-4)(4-5)；；(4-6)4.2.2有时间窗VSP模型设完成任务i需要的时间(装货或卸货)表示为，又设任务i的开始时间需在一定的时间范围内，其中为任务i的允许最早开始时间，为任务i的允许最迟开始时间。如果车辆到达i的时间早于，则车辆需在i处等待，如果车辆到达时间晚于，则任务i要延迟执行。求满足货运要求的费用最少的车辆行使线路。此问题称之为有时间窗的车辆优化调度问题。以表示车辆到达点i的时间，一般应有以下关系式：(4-7)硬时间窗VSP指每项任务必须在要求的时间范围内完成，即必须满足式(4-7)。若超出这个时间范围，则得到的解为不可行解［２］［４］。软时间窗VSP指如果每项任务不能在要求的时间范围内完成，则给予一定的惩罚。惩罚成本函数的设定一般以配送中心与顾客在商议之后所签定的合同为主，但因实际上所签定合同是为维护买卖双方共同的利益，故考虑的因素相当多。若车辆在之前到达点i，则车辆在此等待，发生了机会成本损失。若车辆在之后到达点i，则服务被延迟，须支付一定的罚金。4.3算法设计4.3.1算法流程图算法流程图如图4-1示。4.3.2染色体结构为提高效率，对VSP采用自然数编码方式，即序数编码。单车场车辆优化调度问题的一条可行线路可编成长度为的染色体，其中用自然数表示，代表编号为的需求点。这样的染色体结构可通俗地理解为第一辆车从配送中心0出发，经过需求点后，回到配送中心0，形成子路径1；第二辆车也从配送中心0出发，经过以前未访问的需求点后，返回配送中心0，形成子路径2；依次类推，直到所有的n个需求点全部被遍历，形成子路径m。如染色体021304605870表示的行车线路为：子路径1:配送中心0→需求点2→需求点1→需求点3→配送中心0子路径2:配送中心0→需求点4→需求点6→配送中心0子路径3:配送中心0→需求点5→需求点8→需求点7→配送中心0开始开始输入配送中心及需求点数据输入系统控制参数输出配送中心及需求点数据和系统控制参数初始化运距数组dd遗传代数GEN=0初始化染色体种群计算染色体适应度输出中间结果输出结果满足终止条件？GEN=GEN+1进行遗传操作结束YN图4-1遗传算法解决VSPTW算法流程图这种染色体结构子路径内部是有序的，若子路径1中点1，3相互交换位置，会使目标函数值改变；而子路径之间是无序的，若子路径1和2相互交换位置，却不会改变目标函数的值；若子路径倒转，如0460倒转为0640，也不会改变目标函数的值。4.3.3约束处理对于VSP这类约束较复杂的优化问题，用遗传算法求解时，需要对约束进行处理。一般有下面几种方法：1、问题的约束在染色体中表现出来，设计专门的遗传算子，使染色体所表示的解在遗传算法的求解过程中始终保持为可行解。2、在编码的过程中不考虑约束，而在遗传算法的计算过程中检测得到的染色体相应的解是否可行，若可行，则放入下一代群体中，否则将其舍弃。3、采用惩罚的方法来处理约束。如果一个染色体对应的解违反了某个约束，试其违反程度给予一定惩罚，使其具有较小的适应度。这样，一些不可行解也有可能进入群体，以保证群体中染色体的数目，使遗传算法得以继续运行。若干代后，不可行解在群体中所占的比例应越来越小，可行解逐渐占据主导地位，并逐渐趋于最优解［５］［６］。载重量的约束处理上述第一种方法是直接的处理约束的方法，但适用领域有限，而且设计专门的染色体和遗传算子较为困难，能否采用这一方法与问题的特征关系很大；第二种方法只适用于约束简单、可行解易于得到的优化问题，使用价值不高。在此采用罚函数的方法处理约束。对于一般VSP，使用如下变换将承载量约束式变为目标函数式的一部分：(4-8)其中表示若解违反载重量约束处以的惩罚值。为第k辆车的超载量；maxpath是所有两点间运距中最大的运距；M为超载时施以的惩罚系数，即目标函数所加的最大的运距的倍数。2、时间窗的约束处理本文采用软时间窗约束处理，以d表示车辆在任务点处等待损失的单位时间机会成本，e表示车辆在要求时间之后到达单位时间所处以的罚值。若车辆在之前到达需求点j则产生成本；若车辆在之后到达需求点j则处以罚款。用罚函数法处理时间窗约束，得到软时间窗VSP的目标函数：(4-9)4.3.4适应度函数在有时间窗的车辆优化调度问题中，目标函数值越小越好(即在满足载重量和时间约束的基础上，行车线路的总运距越小越好)，而在遗传算法中，个体适应度越大，表示个体的性能越好,因此需要将目标函数转化为适应度函数。本算法采用了如式4-10所示的变换将目标函数转化为适应度函数。(4-10)式4-10中为群体中第k条染色体对应的目标函数值，反映了第k条染色体所对应解的运输费用；为最大运距；为第k条染色体的适应度，其值决定了该染色体产生后代的概率。4.3.5初始种群本算法采用随机生成的方法产生初试种群。4.3.6遗传算子本算法采用了最佳保留的轮盘赌复制法进行染色体的复制。本算法采用最优保留顺序交叉算子行染色体的交叉。本算法采用改进的反转变异算子进行变异操作。按照概率进行反转变异，第3章介绍的反转变异算子是在染色体中随机选取两个不同位置，将两位置间的子串进行反转。如直接在本算法的染色体结构中采用会产生如下两种问题：1、当随机选取的两点均为0点时，反转变异操作无效，因为此时只是将子路径倒转。2、当随机选取的两点中有一点是0，而另一点的邻位是0时进行反转操作会产生非法的染色体，在染色体中出现两个0相邻的情况，如图4-2示。0038004510276038204510067图4-2传统变异操作产生的非法染色体因此在变异操作前先进行判断，以杜绝以上两种情况的发生，改进的反转变异算子执行流程如图4-3示。4.3.7控制参数和终止条件1、群体规模popsize、交叉率和变异率控制参数(包括群体规模popsize、交叉率、变异率、)的选取对遗传算法的影响很大，要想得到遗传算法执行的最优性能，必须确定最优参数的设置。一般控制参数的选取要根据问题的属性确定。终止条件由于遗传算法具有较大的随机性，这里根据几条启发式的终止条件，给定参数A、X、Y，只要有一条满足就认为算法收敛了。在[1，lchrom-1]中生成两个不等的伪随机整数j1,j2在[1，lchrom-1]中生成两个不等的伪随机整数j1,j2j1,j2满足反转条件?将j1,j2间的元素倒排将数组f1赋给newpop[i]中对应的染色体基因i=i+1开始基于线性排序的轮盘赌策略选出中间代newpopi=0i<popsize?生成伪随机数rr<newpop[i].pm?将newpop[i]中的染色体基因赋给数组f1结束YYYNNN图4-3改进的反转变异算子流程图其中popsize为种群规模。（1）计算每代群体适应度均值，当均值与最佳染色体适应度的比值大于时，可认为算法收敛；（2）记录每代最佳染色体，若染色体连续最佳保持到X代，可终止算法；（3）由于计算时间和机器容量都是有限的，代数不能无限长，故迭代达到规定Y时，可停止计算。4.4算法实现在VC环境下采用c++语言依据算法编写了程序，并调试通过。4.5实验及结果分析4.5.1控制参数选定试验用的数据如下：表4-1需求点的需求信息任务i12345678需求量g21.54.531.542.53装卸时间T121322.530.8[ET,LT][1,4][4,6][1,2][4,7][3,5.5][2,5][5,8][1.5,4]表4-2需求点和物流配送中心任意两点间的位置距离(单位km)0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000货物的装载系数(VehicleRate)=0.95；车辆的载重量(VehicleLoad)=8(吨)；车辆的行使速度(speed)=50(km/h)；种