《基于遗传算法的物流车辆路径规划探究》15000字

PAGE3基于遗传算法的物流车辆路径规划研究TOC\o"1-2"\h\u15193第一章绪论 191291.1研究背景与意义 1180741.2国内外研究发展现状 396241.3本文主要内容 5242861.4本文组织结构 5264251.5本章小结 619666第二章相关技术介绍 737072.1车辆路径问题描述 7263192.2车辆路径规划常用算法 8265802.3遗传算法 10248202.4本章小结 1429308第三章总体设计与建模 15130233.1总体架构 1540213.2CVPR数学模型 16267223.3基于遗传算法的CVPR设计流程 17300163.4本章小结 187334第四章算法实现 19175074.1编码设计 1970634.2初始种群生成 20292254.3评价种群 21173014.4遗传算子设计 22212054.5本章小结 2420922第五章仿真 25270245.1实验数据 25218075.2实验结果 2626330第六章总结 28108666.1完成的工作 28213276.2存在的问题及下一步工作 289590参考文献 29第一章绪论1.1研究背景与意义由于经济社会的不断发展，物流已经成为在劳动力和资源以后的“第三利润源泉”，物流配送是对利润源泉进行挖掘的重要突破口，也引起了物流行业的高度关注。当前世界各国的物流配送都呈现出迅猛的发展态势，物流配送数量迅猛增加，配送规模不断扩大，出现了一些先进的配送方式，比如即时配送（JIT）等[1]，同时物流配送的水平也在不断提升。当前我国企业结合政府部门对于物流配送的发展都非常关注，并且我国政府专门针对物流配送出台了一系列的扶持和鼓励政策，由于我国对物流业的发展高度关注，近几年国内物流配送服务迅猛发展，并且成为很多企业强化自身竞争力和加强成本控制的有力手段。当前物流的高速发展，为城市的建设带来了非常有利的机会，要实现城市的信息化，离不开物流的现代化，城市的建设和发展也需要完善的物流配送体系，为其提供支撑[2]。由于我国城市化进程的逐步推进，不管是经济发展，还是城市的基础设施建设与交通运输布局亦或是城市的空间结构，都需要对原来的物流体系升级改进。我国自21世纪初以来面向物流业推出了一系列的扶持政策，表示对物流行业发展的关注与支持，同时很多城市也意识到物流发展对城市建设与发展的重要意义，我国物流产业也逐渐步入良性发展时期。对于城市来说物流的发展能够对经济建设产生非常重要的拉动作用，够使城市在经济和物流领域的中心地位得到有效提升，并且当前物流业已经不单纯是某个行业，而是成为经济竞争力提升的重要条件。在物流活动中配送是非常重要的业务方式，并且和资金流与物流以及商流有非常密切的联系，涉及资金流与物流以及商流等各种活动，所以也可以将配送理解为一种包括各种物流活动的业务形式。配送涵盖了物流功能的全部要素，可以将其看作是物流的一个缩影，也可以将其看作是物流中各种活动在一定小范围的表现。一般的配送包括运输与保管，以及包装和装卸等环节，通过这些活动共同完成配送。配送系统的运行会影响整个物流系统的运行，要确保物流系统的良好发展，需要制定科学的规划策略。若是依然采用传统的规划方式进行组织配送，那么很可能会带来一系列问题，主要包括：(1)服务量的下降。在城市中物流配送的目的是服务于民众的基本生活，同时还需要为工业企业进行产成品与零部件以及原材料等的配送，所以城市物流配送的商品与货物呈现出流向多变，并且流量大和批次多的特征。但是传统物流配送主要是依赖人工进行调度，因为调度规模比较大，很难快速完成处理，所以会影响配送服务的及时性，同时也会消耗比较长的时间。由于物流配送的业务规模不断扩大，传统的物流配送服务模式已经无法使配送质量得到保证。(2)物流成本控制困难。在传统的物流配送中，我交一辆比较小，那么就能够对配送进行比较科学的安排，可以有效降低成本，然而当交易速度加快、交易规模扩大之后，仅仅依赖人工已经无法完成配送调度的任务，会造成大量的不合理调度，严重影响物流成本的管控。(3)加大城市的负担。现阶段，城市经济社会活动面临的最突出的问题就是环境恶化以及交通资源短缺。如果不能合理调度物流配送，会导致配送成本大幅增加，并且增加交通事故发生的概率，会进一步加重原本就已经非常沉重的交通负担，同时配送调度不合理还会造成大量废气的排放。所以基于现阶段的技术和经济社会条件，对物流配送进行研究有非常重要的现实意义，并且非常迫切。1.2国内外研究发展现状车辆路径问题（VehicleRoutingProblem,VRP）本质上可以理解为优化组合问题，在日常的生活中和理论研究中都具有意义。VRP属于NP难题。VRP在文献中也也被称为车辆调度或者派遣问题。Dantzig和Ramse在上世纪50年代末首次提出这一概念，引起了很多研究者的关注，基于经典或创新的优化算法对其进行研究。车辆路径问题涉及的因素众多，在研究中需要考虑的层面众多，不同的角度研究的结果之间差异较大，所以本文重点是从带能力约束的车辆路径问题展开研究，通过对车辆能力的约束，保证车辆路径规划问题在解决的过程中各项数据信息的完整性和科学性。车辆的载货量达到设计要求。Clarke和Wright[3]在上世纪60年代初针对车队配送问题进行分析，指出启发式节省法在车辆路线的规划和成本的控制上具有很好的效果，随后引起了计算机应用以及运筹学等领域专家的关注，该算法能够快速完成求解并且简单易懂，但是主要适用于较为简单、小规模车辆路径问题的求解。上世纪90年代早期，ElhassaniaM[4]等主要对动态车辆路径问题的求解进行分析，提出可以应用遗传算法进行求解，在研究过程中应用了交叉算子以及启发式算法，通过研究对该算法的有效性进行了验证。KarakatičS[5]等学者在对多中心的车辆路径问题进行分析时，提出可通过遗传算法进行求解，并且对各种遗传方法的效率进行了评估。MungwattanaA[6]等学者在对VRPTW进行研究时提出，可以通过遗传算法以及局部搜索下降法的方式进行求解，通过实验对方法的可行性进行验证，并证明了该方法求解的高效性。相比较而言，我国到90年代才开始兴起关于车辆路径问题的研究，比国外起步要晚，并且研究成果相对较少，目前的研究主要是通过遗传算法进行求解，有的学者觉得遗传算法的收敛效果不高，算法的科学性和精准性不高，以及计算时间长等问题提出了改进方法，主要是单亲遗传算法，以及优化遗传算子和改进编码方式等等。上世纪90年代末，李大卫和王莉[7]等学者通过研究改进了遗传算法的交叉算子以及编码方式，能够通过更加直观的方式进行编码，同时提出了以优先关系为基础的交叉算子，在对算法改善之后可以有效的解决车辆路径规划上的问题。宋伟刚等[8]学者在2005年对遗传算法进行了改进，主要是对其中的交叉算子进行优化，使得算法的寻优能力得到有效提升，并且能够有效避免出现早熟的情况。2006年姜灵敏[9]在对此类问题进行研究时提出，综合应用爬山法和遗传算法可以有效提高求解效率，同时还能够对解的质量进行优化。2009年龙磊[10]等学者针对存在同时急送或需求的车辆路径问题进行探究，指出通过B型算法能够使求解速度得到有效提升，能够独立进行不同子群体的遗传操作。詹孝龙[11]对车辆路径问题情况进行分析时，提出了一种新的改进遗传算法，主要是应用交叉算子进行遗传算法的构建。姚卫粉[12]等学者主要针对遗传算法存在的早熟现象进行分析，通过研究指出，动态小生境协同进化遗传算法的应用能够有效解决这种早熟现象带来的问题，同时也可以使调节效率得到提升。黄务兰和张涛[13]在对带时间窗的车辆路径问题进行探究时，提出可以将段和点交叉段子结合起来对遗传算法进行改进，对该算法的效果进行验证，指出该算法的收敛速度更快，并且在全局寻优能力方面也具有一定的优势。1.3本文主要内容文章的研究主要是为了给物流配送作业的决策提供支持，重点对CVRP问题进行分析和探究，并且通过建立数学模型，以遗传算法为基础，制定路径规划策略，满足物流运输成本最小化。本文的主要研究内容为：(1)建立带能力约束的车辆路径问题模型，将车辆行驶的总油耗成本最少作为目标函数。(2)改进优化遗传算法中的遗传算子与适应度函数，以及染色体编码等，用遗传算法解决物流配送路径规划问题。(3)完成模型创建和数据分析，实现对物流配送问题的仿真实验。1.4本文组织结构本文共分为六章，各章内容如下：第1章，绪论。首先阐述物流配送的背景及意义，简要介绍车辆路径问题的研究和发展现状，说明了本文的研究意义与结构安排。第2章，相关技术介绍。介绍了经典VRP问题的定义与描述，分析对比了车辆路径问题（VRP）的几种常见求解算法。并重点阐述了遗传算法的基本概念与原理，及其特点。第3章，总体设计与建模。介绍了设计车辆路径规划程序的整体架构，建立带能力约束的车辆路径问题（CVRP）数学模型，设计基于遗传算法的CVPR工作流程。第4章，算法实现。阐述了算法实现的各个模块，将建立的CVPR数学模型与算法术语具体结合，以此设计出独特的编码方式，并对初代种群、适应度函数以及遗传算子进行了改进优化。第5章，仿真实例。通过对一个常见路网模型进行仿真模拟。根据实验的数据进行实验验证分析，找出最佳方案，为车辆路径规划问题的解决提供保障。最后，总结与展望。对本文研究内容的总结以及未来发展目标的规划，为接下来的工作指明方向1.5本章小结本章简要分析物流配送的意义研究背景、以及国内外相关领域的研究和发展现状。最后，陈述了本文的主要工作及本文的组织结构。第二章相关技术介绍2.1车辆路径问题描述随着经济的发展和技术的进步车辆路径问题开始成为社会关注的焦点，特别是在融入运筹学、数学、图论、计算机应用及交通运输等学科之后，公路交通运输以及车辆路径管理成为人们经济发展的重要考虑层面，对于改善人们生产效率起到极大的帮助。郭耀煌、李军在对物流行业的研究中将VRP定义为：运输车队在物流配送中心的监管下，实现对多个城市运输过程中的路线优化，创建的最佳路线运输方案，并结合运输过程中的各个约束要求，例如运输的时间、距离、重量以及成本控制等，最终实现用最低的成本达到运输的目的。在对车辆路径问题的研究中经常被描述为；假设存在一个配送中心存在n辆车,此时需要m个结点对其进行运输服务,节点的运输量为gi(i=1,2,...,m)<(i=1,2,…,C),每辆车最大的货物装载量为Q.设Cij就是在运输过程中需要付出的成本,也就是约束能力的条件.此时的配送中心编号为0,节点的信息数据为i(i=1,2,...,m),可以将其定义为：(2-1)(2-2)VRP问题的数学模型：(2-3)(2-4)(2-5)(2-6)(2-7)2.2车辆路径规划常用算法2.2.1精确算法精确算法指的是能够计算得到最优解的一种算法，对于VRP问题的求解而言，常用的精确算法包括网络流算法与动态规划法，以及割平面法和分枝定界法、等。(1)分枝定界法[14]。该方法在对VRP问题进行求解时，主要的思路是先求解与原VRP问题(A)对应的不含整数约束的VRP问题(B)的最优解，若是得到整数解，那么该解就是原问题的最优解。就是得到的解不是整数，那么就需要将非整数解的相邻整数作为一种附加条件，然后得到两个分枝,这就是形成的两个子问题，在此基础上对此问题进行求解。(2)割平面法。用该方法对问题进行求解的思路主要是，对问题(B)进行求解时增加了线性约束条件，也就是割平面，主要是割掉问题B的一部分可行域，以此保留保留整数解而舍弃非整数解，最终刚好有一个整数坐标点为问题A的最优解。因为该方法需要较长的时间才能完成求解，因此对于大规模问题同样不适用。(3)动态规划法[15-16]。Eilon等人最早通过研究提出动态规划法，该方法主要是通过递归方法求解固定车辆数的VRP问题。将问题分解为多阶段其策略求解，然后分别对不同阶段的问题进行求解，这些阶段彼此之间存在递推关系，通过该方法能够得到问题的最优解，但是同样只适用于小规模问题的求解。(4)网络流算法[17]。该算法在对问题进行求解时的思路主要是，先完成VRP问题网络模型的构建，然后从中发现需调量最大的弧，在此基础上对弧两端节点以及弧流量的位势进行调节，从而使弧上的虚调量得到减少，最终让全部弧的需调量都为零。因为边的数目和顶点的数目会对算法的执行效率产生直接影响，因此只适用于小规模VRP问题应用中。精确算法在能够求解的条件下与启发式算法相比，精确算法得到的解往往更优，主要适用于一些小规模问题的求解，特别是对于一些边界和结构都比较清晰的良性结构问题是很好的解决办法。因为如果问题有比较清晰的边界与结构，那么就有对解进行判定的明确准则，同时得到的解也可以很好的反映解决问题的方案，不需要耗费太大的工作量就可以完成求解。然而在实践中，由于问题自身结构以及问题规模，如果应用精确算法进行求解，可能会出现指数爆炸问题，所以精确算法的应用范围较为有限，只是用于小规模和中等规模确定性VRP问题的求解。基于上述分析能够发现，在求解VRP问题方面，没有可能的高效的精确算法，因此需要找到能够对其进行求解的近似算法，基于这种环境，有研究者提出启发式算法，并且启发式算法也成为解决VRP问题的重要方式。对2.2.2启发式算法(1)线路构造算法(TourConstructiveAlgorithm)。主要是基于特定的准则，每一次都需要在线路中增加一个不在其上的点，直到线路中安排全部的点。构造算法是最早应用于VSP问题以及TSP问题的求解，其特点在于具有较强的灵活性，并且求解速度比较快，但是找到的解可能同最优解之间有很远的距离。(2)节约法[18]。ClarkeandWright在上世纪60年代早期，通过研究提出这一算法，所以该算法也被称为ClarkeandWright算法。其特点在于对容量车辆路径问题能够很好的解决，并且不限制车辆的数目。该方法的思路主要是先假设，所有的线路中都有一个车库和顾客，遵循最大节省费用原则对两条路线进行合并，该方法相对较为复杂。(3)禁忌搜索(简称TS)[19]。Glover最早提出禁忌搜索，是在局部领域搜索的基础上进行的一种扩展，其本质属于全局迭代寻优算法，能够通过禁忌准则和灵活的存储结构对迂回搜索进行规避，同时可以利用特赦规则对被禁忌的优良状态进行赦免，一方面可以保证搜索的多样性和有效性，另一方面也可以实现全局的优化。竞技搜索主要是对已经搜索到的局部最优解进行标记，然后通过迭代搜索对这些对象进行避开，但是并非绝对禁止循环，通过这种方式确保对各个区域进行有效搜索，并不断对其进行改进，在此过程中产生的一些车辆路线不一定可行，所以需要通过目标罚函数对这些不可行的路线进行测量，并对其进行改正。Tabu搜索法对目标函数并没有太多的要求，在理论上能够找到全局的最优解，并且能够快速完成。但禁忌搜索在搜索效率方面，可能会对初始解有较强的依赖性，需要精心构造禁忌表结构以及搜索领域结构。(4)模拟退火算法(SimulatedAnnealing，SA)[20]。模拟退火算法主要是在热力学退火原理基础上进行随机搜索的一种算法，最早出现在上世纪中期，直到上世纪80年代才在组合优化领域得到应用。模拟退火算法的思路主要是将目标函数作为能量函数，对物理学中的固体物质退火处理进行模拟，如果能够应用适当的退火步骤，就可以形成能量最低的基态。应用模拟退火算法进行问题求解时，需要接受目标函数有改进的状态。模拟退火算法算较于其他算法来说对目标函数没有特殊的要求，在理论上能够找到全局最优解，并且在大多数情况下都能得到质量较好的解。然而模拟退火算法也有一定的缺陷，主要是很难控制冷却温度，在实践中往往只能得到近似解，并且有非常庞大的算量，耗时比较长，这一点对模拟退火算法的实用性产生了一定的影响。(5)蚁群优化算法(AntColonyOptimization，ACO)[21]。M.Dorigo等人通过蚁群觅食受到了启发，进而提出蚁群优化算法，是一种在组合优化问题进行求解的基础上进行仿生进化的算法，最初被称为蚁群系统(AntSystem,AS)。该算法在求解一些较为复杂的组合优化问题时，表现出了比较好的性质以及比较强的寻优能力。2.3遗传算法2.3.1基本概念与原理遗传算法[22-24]最早是在西方出现，是在达尔文生物进化论基础上发展而来，随后被美国学者进行深入研究并成为主流的算法，它以优异的全局寻优能力、自适性的搜索能力以及内在的隐并行性渗透到了人工生命、组合优化、自适应控制、信号处理以及机器学习等领域，并取得了较好的成果。遗传算法是一种启发式迭代搜索技术。问题的潜在解决方案被编码为染色体，这些染色体形成群体。适应度函数使用在群体中的评价分析。在此基础上选择研究对应的群体，适者生存。通过遗传操作，例如交叉和突变，优胜者有更好的机会被选择和复制后代。重复该过程，群体通过代代进化。经过多代，种群收敛于质量好的解决方案，最好的个体有很好的机会成为最优或接近最优的解决方案[25-26]。一个典型遗传算法有如下要求：（1）解决方案域基因的表示。（2）一个适应度函数来评估解决方案域。当编码和适应度函数确定后，遗传算法就会对解进行初始化操作，然后通过重复应用突变，交叉，倒置和选择算子来改进。遗传算法的求解过程如图2-1所示：图2SEQ图\*ARABIC\s11遗传算法发的求解步骤(1)个体(individual)与种群(population)在遗传算法中，问题可能潜在的解集形成一个集合，集合中的元素，即问题的一个潜在解决方案称为个体，这个集合就叫种群。遗传算法是从这个初代种群开始搜索解的。在不断地进化过程中，种群中的个体是不断变化的，同时种群的规模保持不变，最终得到最优的个体。(2)基因(Gene)与染色体(chromosome)基因是染色体特征的表达，是个体各项特征的基础。染色体往往都是按照编码的形式存在，是重要的遗传物质载体，基因组合组合在一起就是构成个体行为特征的主要基础，通过在个体内部的组合，实现对个体特征的表达。(3)基因位点(Locus)基因位点就是基因位，通过对基因位的研究可以找出其在基因中的位置信息。一般在计算的过程都是按照从左向右的方式完成编号。(4)适应度(Fitness)适应度表示个体在环境中的生存能力。为更好的实现对种群的评价，这里会引入一个遗传算法的概念，通过函数对种群中的个体进行评价分析，即适应度函数，已实现对数据的收集整理，确保对特征信息的准确采集。但是适应度函数的研究在很多时候存在不足，这就需要借助模拟方案实现对特征的掌握收集，确立自适应函数，交互式遗传算法也是很好的计算方式。(5)编码（Coding）遗传算法的编码就是将研究对象按照一定的方式进行编码转化为遗传空间中可被识别的染色体信息。编码的方式很多，常见的为二进制编码，实数编码，整数编码等。完备性、健全性和非冗余性是判断编码好坏的主要依据。不同的编码方式造成的计算成本也是不同。在实际的问题中，应根据问题的特点和复杂程度，设计较好的编码方式。(6)遗传算子（geneticoperator）（a）选择算子（SelectOperator）遗传算法在对群体中的个体特征进行研究分析的过程中主要是借助遗传算子完成。因此研究对象是下一代的主要遗传载体，所以这一过程中也叫做再生(Reproduction)。个体在自适应评价的过程中可以优化自己的选择方案。（b）交叉算子（CrossoverOperator）交叉算子可以对不同染色体上的基因位置进行两两交换。这些过程最终产生与第一代不同的下一代染色体群体。选择来自第一代的最佳个体以及小比例的适应度低的个体，通过交叉处理，群体平均适合度将增加。这些适应度低的个体确保了父一代遗传库内的遗传多样性，并因此确保随后一代种群的遗传多样性。（c）变异算子（MutationOperator）变异算子表示对目标个体的特征进行异化转向。变异是随机的无序的，因此无法判断变异的好坏。但是变异的过程就是一个进化的过程这一点可以通过算子进行研究。当所有的个体保持一致性时，新个体的出现就必须在变异的基础上完成。也可以理解为变异就是对全局多样性的维护，是保证个体差异化特征的基础，正是在变异的基础上才能实现全局优化。2.3.2算法特点（1）自适应性:遗传算法在自适应调节的过程中需要结合各项数据信息对自适应的环境进行调节，在此过程中适应度高的个体将会存活下来，而自适应低就会被自然淘汰。因此在对种群的规模进行评价的过程中需要结合客观的优化评价体系进行，创建函数完成评价。（2）全局最优性:遗传算法最优解的求解是从全局出发，所以其搜索的范围更加广泛，是在整体的基础上完成对最佳数据的分析，找出最佳问题解决方案。算法执行交叉和变异就是对全局最佳方案的选择，避免出现算法上的混乱。（3）并行性:遗传算法在搜索的过程中其目标的选择对象可以是多个，也就是在多个个体特征上进行处理，实现对不同自适应度的评价分析，提高算法的计算效率，降低计算成本。（4）不确定性:遗传算法的选择、交叉和变异操作算子都是在一定概率的基础上完成，对计算的方式方法进行指导，因此可以理解为遗传算法具有随机性和不确定性。（5）通用性:遗传算法在求解的过程中可以在单一信息的支持下完成对问题的分析，将问题解决方案转化为潜在的染色体，通过染色体完成对自适应的调节和使用，完成个体的评价。遗传算法在问题的解决处理上具有通用性，适应能力强。2.4本章小结本章对车辆路径规划问题展开介绍分析，通过对NP-hard难题的分析指出本文的研究思路，结合本文研究问题创建相关模型，列举了VRP问题各类算法，重点对遗传算法的路径规划思想展开介绍分析。第三章总体设计与建模3.1总体架构根据路径规划算法的实际应用场景，物流配送车路径规划程序的总体架构分为三层，从左到右分别为：数据采集汇聚层、算法规划层、表现层。系统总体架构如图3-1所示。图3SEQ图\*ARABIC\s11系统架构图数据采集汇聚层：主要通过RFID智能标签与车载GPS对路网信息，车辆运输及分布特点，客户货物需求量等数据进行采集。对采集到的数据进行预处理，构建CVRP数学模型，确定车辆的数量等。算法规划层：把车辆路线规划的潜在解决方案编码成染色体，生成初始种群。评价种群，遗传进化操作，直到得到适应度最好的个体。通过遗传算法的处理来实现物流配送车最优路线方案的输出，是系统处理中最重要一环表现层：由适应度最高的个体映射出车辆最优派遣方案，为相关物流配送作业提供决策支持。3.2CVPR数学模型定义如下：假设有运输车辆为m辆，每辆车的载货量都是Q；面向的服务客户数量为n，对客户进行编号i(i=2,Lni=0表示为配送中心，客户i对货物的需求数量为qi(i=2,Lnq0=0，并且任意客户的货物需求量qi要小于每辆车的额定载货量Q；客户i与客户j之间的路程为dij，若客户i、j之间不能连通则dij=0；车辆k从客户i驶向客户j到达之前车上配送物品的重量为wijk，若客户i¹j&j=0wijk=1。若车辆k访问客户i后访问客户j(i¹jxijk=xijk=0；若客户i的需求可以由车辆k满足则yik=1yik=0。(3-1)约束条件为：(3-2)(3-3)(3-4)(3-5)(3-6)(3-7)其中，式（3-1）代表车辆运输过程中付出的油耗最小，式（3-2）表示客户需要运输的货物不得超过车辆的最大承载量，式（3-3）表示可以运输的车辆为m辆，客户的运输要求只能由一辆车服务，也即是客户的货物通过一辆车运输，式（3-4）和式（3-5）表示在运输的过程中中间只能停靠一次，式（3-6）和（3-7）表示对变量的约束。3.3基于遗传算法的CVPR设计流程车辆路径问题需要考虑到车辆的数量和路线的选择，在方案的确定上充满随机性和不确定性。遗传算法（GA）属于自然选择的原启发式方法，可以生成一些质量比较高的解决方案，通过选择、交叉以及突变等生物启发运算操作对问题进行搜索和优化，在对CVRP问题进行求解时，遗传算法的运算流程详见下图4-2。图3SEQ图\*ARABIC\s12基于遗传算法的车辆路径规划流程图第一步：信息收集，对路网信息和货物量数据进行采集。第二步：要解决问题的特征以及信息完成相应数学模型的构建，也就是目标函数的构造。第三步：明确编码方式，明确遗传算子、最大遗传代数，以及种群个体数量等相关参数之后，对潜在解决方案进行编码，形成各种基因的染色体。第四步：获取研究初期的种群，按照研究的要求和设计的标准，获取最大容量的种群染色体，作为研究的初始种群。第五步：评价种群，由目标函数以及惩罚函数对研究的群体特征进行评价，然后在自适应的基础上完成对个体特征的分析，结合适应度值完成对个体的分析研究。第六步：遗传操作，主要是对交叉、选择和变异的分析研究。其中选择算子能够提高选择适应度值更大的个体的概率，能够提高淘汰数值较小的个体的概率。交叉算子的存在可以按照确定的交叉概率对两个个体进行交叉操作。变异算子能够按照变异概率进行变异操作。第七步：终止条件判断，通过不断的进化，最终符合终止条件，找到了适应值最大的个体，若是没有，则继续执行第五步。第八步：基于运算结果对问题的最优路径进行求解。3.4本章小结本章首先根据VRP问题的实际应用场景介绍了设计车辆路径规划程序的总体架构，然后根据第二章的相关技术的介绍和构建了基于遗传算法的路径规划原理和工作流程，结合研究对象特征，依据带约束能力的要求创建研究模型。第四章算法实现4.1编码设计遗传搜索的基础就是编码，通过科学的编码可以实现对遗传搜索的科学性和完整性。针对车辆路径优化组合的研究中，能够完成编码的方式有很多，这里经常使用到的就是二进制编码。整数编码就是在整个基因值的基础上通过整数进行表达，整数的数值对应个体的数量。本文使用的是整数编码实现对车辆整体信息的表达。对于物流配送车路径问题，用整数编码，染色体的长度与车辆数和客户数有关，当有客户数量为n，各客户编号用i(i=1,2,...,n)表示。车辆数为m，则存在m条运输配送路径。每条路径都是从配送中心开始直到货物配送目的地结束。这里使用0表示配送中心，整数编码染色体的开始和最后都是0，为实现染色体在车辆信息的表达上更加科学准确，在第1,2,3,...,n客户中间插入m1个虚拟配送中心，这里也使用0表示，那么就可以得出：i12,Li1p,i21,i22,L,i2v,0,L,0,im1,im2,L,imw,0)，其中p+v+w=n，染色体的长度为n+m+1。这n个相互独立的自然数彼此相加，m+1个0组成的n+m+1在整数编码基础上随机排列就可以构成一条染色体，也就是配送路径的选择依据。在对任意路径的研究过程中，也就是在有效染色体的研究过程中需要满足下面的条件：1）任意一条染色体的首尾必须为0。2）任意一条染色体中的两个0不得相邻。实例：在对物流配送的研究过程中，假设这里的车辆数为2，客户数为7，设其随机构造的染色体为0215307640，那么对应的长度为7+2+1=10，此时总路径在2辆车的选择上为：第一辆车路线：0→2→1→5→3→0；第二辆车路线：0→7→6→4→0；染色体中子路线之间可以是无序的，但是在每条子路线上访问客户点是有序的，改变子路线上客户节点的访问顺序会导致目标函数发生变化。针对路径的规划过程中，首先需要明确车辆的数量为m。车辆的约束条件也是研究的重点，为提高效率就需要降低车辆的运输成本。在对车辆数量的研究中公式如下所示：(4-1)其中，m表示当前的车辆数量，qi代表客户i需要运输的货物总量，Q表示车辆的最大载货量，a(0<a<1)的值结合约束条件的限制得出，在约束条件减小的情况下，a取值增加，反之变小，这里的数值设置0.85，本文a=0.85。û表示数值下调。4.2初始种群生成本文研究中使用的是随机但是具有约束的研究方式，这样可以最大程度的保证收敛效果，提高种群的丰富性和多样性，增加样本中有效个体的数量。路径规划中的初始种群在最初的研究中都是建立在节点的基础上，通过对车辆路径的分析完成整体路径的规划。结合本文的研究完成编码整理信息，详细的操作方式如下所示：第一步：对客户信息进行编码，用i(i=1,2,…,n)表示；第二步：根据客户编号随机产生一次客户的排列，排列后重新编号e(e=1,2,…,n)，其对应的货物量为；第三步：从客户对应的第一个编号元素开始计算客户点对应的货物累计需求量，若h满足则针对客户的排序进行到h后就可以插入虚拟中心，以此内推，直至插入(m-1)个0为止，然后在排列的开始和结束设置为0，这就是染色体形成的过程；第四步：重复上述步骤，直到满足种群规模。4.3评价种群4.3.1定义惩罚函数以遗传算法编码为基础设计的染色体，在进行选择、交叉和变异的过程之后，染色体的构造形式就会发生变化，在实际的研究中每辆车的载货量可能不满足设计要求，这就需要使用到惩罚函数对系统进行调整，惩罚函数的定义如下所示：(4-2)其中，T表示达不到约束条件车辆的惩罚值。这里为便于对惩罚函数进行研究，在数值的选择上往往较大。当车辆的承载最大时，惩罚值为0；随着车辆的载货量提高，惩罚数值也会相应的增加。4.3.2适应度计算通过对种群中个体适应度的计算分析，可以完成遗传算法中的种群评价。针对本文的研究对象，为在最短时间内将货物送达制定地点，降低运输成本，需要对车辆的使用进行合理的安排，设计出全局最优规划路径，在车辆运输距离基础上，对载货量也要科学分析，实现成本的降低。因此本文的研究是在（3-1）式和（4-2）式组成得：(4-3)(4-4)其中，目标函数为F，研究个体的适应度值为f，在符合约束模型条件的基础上，随着f数值的增加，表示个体的适应度也在不断提高，个体在进化的过程中具有更强的适应能力，反之则在进化的过程中更容易被自然淘汰。4.4遗传算子设计4.4.1选择算子选择操作是在个体自适应研究基础上得出。这对于优秀个体的遗传和保留具有重要的作用，只有优秀的个体才会被最大程度的保留下来。算子的选择众多，轮盘赌选择、精英保留策略和确定式采样等都是常见的方式。轮盘赌是在概率的基础上将概率最大的个体保留下来，在算子的设计研究中扮演着重要的角色。精英保留策略是在遗传个体中找出最佳的个体，并将其直接保留下来，然后和选择之后的个体进行比较，将表现优异的个体保留下来，也就是不断的用最好的替代最差的。确定式采样就是在人为因素的干扰下对选择的方式方法进行设计明确。本文采用轮盘赌和精英保留策略组合的方式。相比其他方法具有高效、实用的特点。个体被选中的概率公式为：(4-5)其中，表示第i个个体被选择的几率，表示第i个个体适应度数值。4.4.2交叉算子交叉算子，表示遗传中的精子和卵子相互结合产生受精卵的过程，在生物遗传上具有重要的研究价值，是分析生命起源的重要途径。交叉算子在研究的过程中需要考虑双方的联系，就像是孩子出生之后，有的地方像父亲，有的地方像母亲，但是在个体的选择上都是随机的。本文算法中交叉概率pc=0.85。由于染色体中车辆的信息都是按照一定的顺序排列，但是车辆的路径都是随机的。车辆的数量在染色体群定的情况下也是明确的，也就是当染色体的数量为0时不得改变。所以这里介绍一种新的两点交叉法。详细的研究思路为：交叉点的出现是随机的，如果此时出现的两点交叉在数值上满足，那么在此情况下出现的交叉点是有效的，反之则是无效的，那么就需要重新对两点交叉点进行生成；在交叉点出现的过程中子串的数值不得为0，如果存在0，就需要对子串的位置进行移动，直到该0消失为止；然后对子串的位置进行交换；完成交换之后的基因必然会存在重复的信息，这里需要对其进行清除。如果不存在子串0，就可以进行交叉操作。例如：P1：（06830|521|0740）P1：（01680|273|0450）其中“|”表示交叉点，若交叉点的子串不含0，则可进行交叉操作得到如下字串：Q1：（06830|273|0740）Q2：（01680|521|0450）交叉后发现Q1有重复的基因点3,7，Q2的重复基因点为1,5，保持两个交叉点之间的基因不变，对其他重复位置的基因进行操作，将基因点两两反向交换，得到：Q1：（06850|273|0140）Q2：（07680|521|0430）如果染色体交叉点子串中存在0，就需要对子串的位置进行移动，直到该0消失为止；然后进行交叉操作。例如：P1：（06803|520|1740）P2：（01680|273|0450）将染色体P1中的交叉点向左移动一位，得到：P1：（0680|352|01740）P2：（01680|273|0450）用上述方法进行交叉运算后得到：Q1：（0680|273|01540）Q2：（01680|352|0470）4.4.3变异算子变异是随机的，变异的过程会产生节点用来替代之前的节点，在变异的过程中往往会出现更多的方案，对问题的解决提供研究思路，因为这也是解决方案的有效途径。在突变的过程中观察染色体的变化，选择更好的对象，每个基因的突变概率为pm（通常在0.001〜0.3内），这里研究中设置pm=0.25。突变和交叉是相互作用的，其目的是保证重要信息的完整性和科学性。但是突变的信息保留非常短暂，这样可以避免对下一代遗传的破坏。在对染色体结构的分析过程中，本文使用的是互换变异算子完成对路径的分析研究。互换变异算子的本质就是在随机变异基础上完成对基因的分析和研究，为了提高变异效率，两个基因需为非零且基因位置在不同子路径实现。例如：P1：（06|8035201|740）其中“|”表示变异位，子路径0680对应的变异位为6，子路径01740对应的变异位为7，将两者进行交换变异得到：Q1：（078035201640）4.5本章小结整合现有第五章本章重点阐述了遗传算法在求解该问题的几个关键步骤，设计整数编码的方式对染色体进行编码；本文研究中使用的是随机但具有约束的研究方式，这样可以最大程度的保证收敛效果，提高种群的丰富性和多样性，增加样本中有效个体的数量；算法在函数评价的过程中需要关注两点：运输的总路程和车辆的运输能力，目的是降低成本；对遗传算子进行优化，保证收敛效果。第五章仿真5.1实验数据本次实验的数据来源于某大型连锁物流中心，配送中心周边分布着12个客户节点，根据这12个客户点的货物需求量，由公式（4-8）可确定完成这些任务需要车辆数目m=4，其中每辆车的最大载重为70。客户货物需求量如表5-1所示。其中算法的控制参数设置：交叉概率为Pc=0.25，变异概率为Pm=0.25，种群规模N为600，进化代数Gen为400。表5SEQ表\*ARABIC\s11客户货物需求量客户编号i123456789101112货物需求量qi121816291517112325211927路网信息记录着任意两个不同节点的连通性以及路程，如果两个节点不能连通，则用路程0表示，如表5-2所示。表5SEQ表\*ARABIC\s12配送中心（i=0）及各客户之间的路程客户编号012345678910111200151317167.18.310.212.37.913.814.615.211509.1218.613.61016.825.52128.62730.12139.1012.4177.31419.719.22123.927.227.13172112.402810.82327.214.32520.730.5264168.616.528018.27.812.128.21929.423.429.257.1147.310.81801216.512.21516.621.52068.31013.522.87.812.206.920.61121.617.121.67101719.727.21216.56.9021.37.420.111.318.38122619.214.32812.22121.30156.519.212.297.92120.524.51914.9117.415.20136.710.910142923.920.72916.62220.16.513014.8611152727.230.52321.51711.319.26.714.801012153027.12629202118.312.2116100配送中心和客户点的分布图如图5-7所示，用黑色的三角形表示配送中心，用黑色的圆点表示客户点。图5SEQ图\*ARABIC\s11配送中心和客户点的分布图5.2实验结果为了确定所得到的解科学有效，对以上数据集进行多次测试得到最优的实验结果如图5-8和如表5-3所示：图5SEQ图\*ARABIC\s12最优路径轨迹图表5SEQ表\*ARABIC\s13车辆派遣方案路径编号车辆停靠顺序10 7 4 6 020 8 3 5 030 2 11 9 040 1 10 12 0车辆派遣方案具体如下：第一辆车的配送路线：配送中心→客户节点7→客户节点4→客户节点6→配送中心第二辆车的配送路线：配送中心→客户节点8→客户节点3→客户节点5→配送中心第三辆车的配送路线：配送中心→客户节点2→客户节点11→客户节点9→配送中心第四辆车的配送路线：配送中心→客户节点1→客户节点10→客户节点12→配送中心第六章总结6.1完成的工作本文围绕物流配送车在路径选择规划上存在的各类问题展开分析。首先对本文的研究背景进行介绍，通过查找大量资料文献，对比国内在现阶段的发展现状，深入剖析物流配送方面的知识，对车辆路径规划上常见的各类算法进行介绍分析，通过对各种优化算法的分析和比较，并根据车辆路径问题的特点，明确提出遗传算法在本次研究中的重要性和意义，然后对该算法的相关理论和特征展开论述。通过建立数学模型，使用遗传算法规划物流路径，满足物流运输成本最小化。本文的主要研究内容：(1)建立带能力约束的车辆路径问题模型，确定了以车辆行驶的总油耗成本最少作为目标函数。(2)改进优化遗传算法中的遗传算子与适应度函数，以及染色体编码等，用遗传算法解决物流配送路径规划问题。(3)完成模型创建和数据分析，实现对物流配送问题的仿真实验。6.2存在的问题及下一步工作文章主要对车辆路径规划问题进行了简单的研究，在实践中可能会存在约束条件或者需求增加等一些不确定性因素，所以今后的研究可以从以下几方面进行：（1）文章主要是对CVRP模型中的静态因素进行分析，在实践中，配送中心和客户数量往往是变化的，在今后的研究中需要考虑这些动态因素。（2）虽然对算法的遗传算子进行了优化，但在算法遗传进化过程中，具体的交叉概率、变异概率是固定的，而不是自适应，不会动态调整。所以在下一步中应该建立更加智能的算法改进。（3）文章构建CVRP模型过程中进行了理想化处理，没有考虑复杂的约束条件。在实际的应用中还需要更多研究。（4）本文围绕物流配送问题展开研究，首先设置物流配送中心，企业规模壮大之后，其物流配送中心的数量也会增加，如何将这些配送中心有效的联合在一起，结合VRP问题成为当前研究的重点。参考文献崔沪.“大和”的秘密武器—解读日本大和运输公司配送模式及其特点[J],中国物流与采购,2003,3:26-27刘有鹏.我国城市信息化与物流现代化的关系及发展道路[J],上海经济研究,2006,8:72-76ClarkeG,WrightJ.W..Schedulingofvehiclesfromacentraldepottoanumberofdeliverypoints[J].OperationalResearch,1964,12:568-581.ElhassaniaM,JaouadB,AhmedEA.Solvingthedynamicvehicleroutingproblemusinggeneticalgorithms[C]//LogisticsandOperationsManagement(GOL),2014InternationalConferenceon.IEEE,2014:62-69.KarakatičS,PodgorelecV.Asurveyofgeneticalgorithmsforsolvingmultidepotvehiclerouting