基于遗传算法的车辆路径问题研究

基于遗传算法的车辆路径问题研究中文摘要：近些年,物流作为“第三利润源泉〞受到国内各行业的极大重视并得到较大的开展。物流的目标就在于以最少的费用满足消费者的需求。配送作为物流中一种特殊的、综合的活动形式,在当今社会经济开展中发挥着越来越重要的作用。配送的核心为配送车辆的调度、货物配装及送货过程。进行配送系统优化,主要是配送车辆调度的优化。对配送车辆进行优化调度,有利于提高物流经济效益、实现物流科学化。本文主要对单车场非满载无时间窗的车辆路径问题和动态车辆路径问题进行了研究。论文首先对现有车辆优化调度问题归类分析。然后对车辆路径问题的传统求解算法的根本思想、性能、适用性进行了分析,在此根底上提出了采用扫描法和遗传算法相结合的启发式算法来求解物流配送车辆优化调度问题的思想。在对遗传算法中的选择操作、邻域结构操作进行改良的根底上,提出了一种求解车辆路径问题的自适应遗传算法。应用C语言编程进行实例计算,结果说明改良的遗传算法明显增强了群体演化的质量,提高了算法的收敛速度,得到了问题的满意解。与传统遗传算法相比,扫描法和改良遗传算法的结合,其优化能力、运行效率、可靠性均有一定的提高。最后论文在对动态行驶时间车辆路径问题进行建模的根底上,尝试采用扫描法和改良遗传算法相结合的方法对此类问题进行求解,在保证客户效劳水平的要求下,取得了比拟好的结果。关键词：物流车辆路径问题;扫描法;遗传算法Abstract:Recentyears,logistics,takenas"thethirdprofitresource",hasbeendevelopingrapidly.Theobjectoflogisticsistosatisfytherequirementsofconsumerswithleastcost.Asanespecialandintegratedactivityoflogistics,physicaldistributionplaysanimportantroleinmodernsociety.VehicleRoutingProblem(VRP)isthemainpartofthedistributionsystemoptimizing.Itisbenefitstomakeeconomicbenefits.Thispapermainlystudiedatypeofvehicleroutingproblemwithsingledepot,non-fullloadandwithouttimewindowsandadynamicvehicleroutingproblem.Therestrictionsandmathmodelsofvehicleroutingproblemisanalyzed.Thispaperalsocomparedandanalyzedthebasicideas,capabilitiesandapplicabilityoftraditionmethodheuristicsofVRP.Basedonthis,thispaperputforwardanimprovedgeneticalgorithmforvehicleroutingproblem,throughchangingitsselectoperationandneighborhoodstructureoperation,anadaptivegeneticalgorithmwaspresentedforsolvingthisproblem.ComputationalresultsbasedonClanguageprogrammingdemonstratedthattheadaptativealgorithmimprovedthequalityoftheresultsandcansolvetheproblemeffectively.Exemplificationsprovedthatthisalgorithmcanenhancecapabilityofoptimization,solvingefficiencyandreliabilityofrunning.Finally,adynamicvehicleroutingproblemwithrandomtimewindowismodeled.Thisproblemisalsosolvedbysweepandgeneticalgorithmsmethod.Themethodhavemadegoodeffectinensuringcustomerservicelevel.Keyword:VehicleRoutingProblem;sweepmethod;geneticalgorithm1引言车辆路径问题〔VehicleRoutingProblem，VRP〕是一类在物流配送调度中具有广泛应用的优化组合问题，在现代物流中居于中心地位。本文首先介绍了遗传算法在解决简单约束车辆路径问题上的应用，改良了交叉算子，为研究有时间窗装卸问题的遗传算法作了充分准备。本文详细分析了有时间窗装卸问题的数学模型，深入研究解决此问题的分组编码遗传算法，将禁忌思想用于产生可行解的启发式插入搜索算法之中，并构造出适用于多目标的适应度函数，设计新的数据结构，对分组编码遗传算法进行有效实现。在分组编码遗传算法中提出路径调整思想，设计出一种多策略分组编码遗传算法。采用多组通用算例测算，将多策略分组编码遗传算法与其它算法进行比拟，其求解结果和计算时间都有明显改良，验证了多策略分组编码遗传算法能够有效稳定地收敛到所求问题的解。VRP最早由Dantzig和Ramser于1959年提出，引起运筹学、应用数学、组合数学、图论与网络分析、物流科学、计算机应用等学科研究人员的极大重视，成为运筹学与组合优化领域的热点问题。各国研究人员对该问题进行了大量的理论研究及实验分析，取得了重大进展，其研究成果在运输系统、公交车辆路线设计、快递收发系统、物资调配系统中都已得到了广泛应用。研究车辆路径问题的特点及算法具有重要的实际意义。本文重点研究解决有时间窗装卸问题〔PDPTW〕的遗传算法，作为前期准备，本文作者对遗传算法解决具有简单约束条件的VRP〔包括有容量约束的车辆路径问题CVRP和有时间窗的车辆路径问题VRPTW〕进行了初步研究。有容量约束的车辆路径问题〔CapacitatedVehicleroutingproblem，CVRP〕是由一个效劳中心〔或车场〕的假设干车辆向多个客户点进行配送效劳，在待效劳客户点和出发点的位置、客户需求及车辆最大负载的前提下，设计车辆配送路径，规划设计方案，使运输本钱最小化，即总代价最小〔使用车辆尽量少，行车总距离尽量短〕。CVRP实际是多目标组合优化问题，一般以派出车辆最少〔运输路线条数最少〕为首要目标，行车总距离最短，即总代价最小为次要目标。CVRP要求满足以下条件及假设：〔1〕所有的配送车辆以配送中心为起点并最终回到配送中心；〔2〕每条配送路径上各客户点的需求量之和不超过车辆的负载量；〔3〕每个客户点的需求仅由一辆车一次满足。2选题的目的物流已被认为是继降低原材料消耗和提高劳动生产率之后的“第三利润源〞。通过优化物流系统,可以降低物流本钱,从而增强企业的市场竞争能力。因此,研究物流系统中的优化问题,具有十分重要的意义,是国内外研究的一个热点。库存本钱与配送本钱是物流系统的核心本钱,在物流总本钱中占据了很大的比例。如果能降低库存本钱与配送本钱,就能有效地降低物流本钱。遗传算法是一种应用很广泛的智能优化算法,本文对遗传算法进行了分析研究,针对遗传算法的一些缺陷提出了相应的改良方法。在上述研究根底上,本文基于遗传算法,研究了物流系统中的库存优化问题及车辆路径问题。本文将库存仿真优化问题与车辆路径问题都看作是组合优化问题,并应用遗传算法进行求解。本文的主要研究工作及奉献可归纳如下:(1)对随机库存系统建立了基于离散事件系统的计算机仿真模型。用系统仿真方法求解最优库存策略时,其难点之一在于仿真的优化。为此,本文将计算机仿真技术和遗传算法相结合,应用遗传算法来优化模型的控制参数,即获得最优的库存控制策略。针对随机系统的特点,设计了候选解收集器,它能够收集在仿真优化过程中产生的Pareto解;提出了M精英选择算子,用于保护潜在的最优个体,使它们在交叉、变异算子中不被破坏。针对两种常用的库存控制策略进行了仿真优化的实验,结果说明本文提出的仿真优化方法是有效的。(2)旅行商问题(TSP)是车辆路径问题的子问题。为了求解TSP问题,研究了常用于TSP问题的三种交叉算子的优化效果,提出了一种求解TSP问题的高效混合遗传算法HGA-TSP。在该算法中以变形的OX算子作为交叉算子,以2-opt算法作为遗传算法的变异算子;提出了K近邻点集的概念以缩减搜索空间并提高算法的时间效率。(3)将单配送中心,多辆运输车且无约束的车辆路径问题建模成具有总路径长度最短、子路径长度均衡性好这两个目标的双目标多旅行商问题(MTSP),并基于HGA-TSP算法,研究了三种求解上述问题的解决方案。(4)对于带能力约束的车辆路径问题(CVRP),提出了一种新的双层染色体编码方案和一种子路径交换算法。双层染色体编码方案不需要预先知道最优解所需要的车辆数,并能确保染色体不违反能力约束,这更适合求解实际物流配送系统中的车辆路径问题。此外,相对于常用的单层染色体编码方案,该编码方案还能降低搜索空间的大小,从而提高搜索效率并降低计算时间。子路径交换算法可以有效提高遗传算法的求解精度。基于上述双层染色体编码方案和子路径交换算法,设计了两种求解CVRP问题的混合遗传算法,分别是HGA-CVRP算法和HGA-SE-CVRP算法。(5)对于带时间窗约束的车辆路径问题(VRPTW,首先改良了双层染色体编码方案,以便在编程实现时更方便地进行子路径的处理。然后研究了遗传算法与邻域搜索算法的结合方式,在遗传算法中引入了带克隆操作的邻域搜索算子。最后提出了一种求解VRPTW问题的新型混合遗传算法HGA-VRPTW。(6)综合应用了面向对象分析与设计、多线程、UML等先进的软件开发方法与技术,设计并开发了VRP仿真实验室,这是一个用于研究车辆路径问题的软件包,具有使用简便、界面美观的特点。VRP仿真实验室在本文的研究中发挥了重要的作用,是研究车辆路径问题的有力工具。本文对大量的基准测试实例(Benchmark)进行了仿真计算,计算结果说明,本文所提出的一系列算法能有效求解物流系统中的库存优化问题与车辆路径问题。3问题描述3.1车辆路径问题定义车辆路线问题〔VRP〕最早是由Dantzig和Ramser于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，到达诸如路程最短、本钱最小、消耗时间最少等目的。由此定义不难看出，旅行商问题〔TravelingSalemanProblem,TSP〕是VRP的特例，由于Gaery。已证明TSP问题是NP难题，因此，VRP也属于NP难题。车辆路线问题自1959年提出以来，一直是网络优化问题中最根本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下〔如图1〕：图1路径问题描述设有一场站〔depot〕，共有M辆货车，车辆容量为Q，有N位顾客〔customer〕，每位顾客有其需求量D。车辆从场站出发对客户进行配送效劳最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。3.2车辆路径问题的类型一般而言车辆路线问题大致可以分为以下三种类型〔Ballou，1992〕：1、相异的单一起点和单一终点。2、相同的单一起点和终点。3、多个起点和终点。3.3车辆路线问题研究现状经过几十年的研究开展，车辆路线问题研究取得了大量成果。下面从车辆路线问题的现有研究型态和求解方法两个方面介绍车辆路线问题的研究现状。3.3.1车辆路线问题型态在根本车辆路线问题〔VRP〕的根底上，车辆路线问题在学术研究和实际应用上产生了许多不同的延伸和变化型态，包括时窗限制车辆路线问题〔vehicleroutingproblemswithtimewindows，VRPTW〕、追求最正确效劳时间的车辆路线问题〔VRPDT〕、多车种车辆路线问题〔fleetsizeandmixvehicleroutingproblems，FSVRP〕、车辆屡次使用的车辆路线问题〔vehicleroutingproblemswithmultipleuseofvehicle，VRPM〕、考虑收集的车辆路线问题〔vehicleroutingproblemswithbackhauls，VRPB〕、随机需求车辆路线问题〔vehicleroutingproblemwithstochasticdemand，VRPSD〕等。3.3.2解决方法1、求解方法演进综合过去有关车辆路线问题的求解方法，可以分为精确算法〔exactalgorithm〕与启发式解法〔heuristics〕，其中精密算法有分支界限法、分支切割法、集合涵盖法等；启发式解法有节约法、模拟退火法、确定性退火法、禁忌搜寻法、基因算法、神经网络、蚂蚁殖民算法等。1995年，Fisher\o""曾将求解车辆路线问题的算法分成三个阶段。第一阶段是从1960年到1970年，属于简单启发式方式，包括有各种局部改善启发式算法和贪婪法〔Greedy〕等；第二阶段是从1970年到1980年，属于一种以数学规划为主的启发式解法，包括指派法、集合分割法和集合涵盖法；第三阶段是从1990开始至今，属于较新的方法，包括利用严谨启发式方法、人工智能方法等。2、启发式算法由于VRP是NP-hard问题，难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法。简单启发式方法包括节省法或插入法、路线内/间节点交换法、贪婪法和局部搜索法等方法。节省法或插入法〔savingsorinsertion〕是在求解过程中使用节省本钱最大的可行方式构造路线，直到无法节省为止。交换法那么是依赖其他方法产生一个起始路线，然后以迭代的方式利用交换改善法减少路线距离，直到不能改善为止。1960年，Clarke和Wrigh首先提出一种启发式节省法〔savingsmethods〕来建立车队配送路线。简单启发式方法简单易懂、求解速度快，但只适合求解小型、简单的VRP问题。两阶段方法包括先分组后定路线〔clusterfirst-routesecond〕和先定路线后分组〔routefirst-clustersecond〕两种启发式策略。前者是先将所有需求点大概分为几个组，然后再对各个组分别进行路线排序；后者那么是先将所有的需求点建构成一条路线，再根据车辆的容量将这一路线分割成许多适合的单独路线。1990年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。禁忌搜索法〔TS〕根本上是属于一种人工智能型〔AI〕的局部搜寻方法，Willard首先将此算法用来求解VRP，随后亦有许多位学者也发表了求解VRP的TS算法。西南交通大学的袁庆达等设计了考虑时间窗口和不同车辆类型的禁忌算法，这种算法主要采用GENIUS方法产生初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，Osman对VRP的模拟退火算法进行了研究，他提出的模拟退火方法主要适合于解决路线分组。遗传算法具有求解组合优化问题的良好特性，Holland首先采用遗传算法〔GA〕编码解决VRPTW问题。现在多数学者采用混合策略，分别采用两种人工智能方法进行路线分组和路线优化。Ombuk提出了用遗传算法进行路线分组，然后用禁忌搜索方法进行路线优化的混合算法。Bent和VanHentenryck那么首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法〔largneighborhoodsearch〕将运输费用降到最低。总结几种人工智能方法可以看出，TS算法所得到的解最接近最优解，但其运算时间也最长，是GA算法的2～3倍，SA算法的近20倍；由于GA算法也能较好的逼近最优解，同时使运算时间大大缩短，所以GA算法能兼顾运算时间和效率两方面，是具有较好的开展前途的方法；SA算法求解速度非常快，也能提供一定程度上的优化方案在求解较小规模问题上具有较好效果。4遗传算法介绍遗传算法简称GA(GeneticAlgorithm)，在本质上是一种不依赖具体问题的直接搜索方法。它是根据生物进化思想而启发得出的一种全局优化算法。遗传算法的概念最早是由BagleyJ.D在1967年提出的；而开始遗传算法的理论和方法的系统性研究的是1975年，这一开创性工作是由Michigan大学的J.H.Holland所实行。当时，其主要目的是说明自然和人工系统的自适应过程。遗传算法是受生物进化学说和遗传学说启发而开展起来的，基于适者生存思想的一种较通用的问题求解方法。利用遗传算法进行寻优时，编码、选择、交叉、变异是四个重要步骤。遗传算法作为一种全局优化搜索方法，具有简单、通用普适性强，适用于并行处理和应用范围广等优点。遗传算法在优化领域表现出了其强大的能力，遗传算法仿照生物进化和遗传的规律，利用复制、交换和突变等操作，使优胜者繁殖，劣败者消失，一代代重复同样的操作，最终找出最优解。具有如下特点：

(1)遗传算法运算的是解集的编码，而不是解集本身；

(2)遗传算法的搜索始于解的一个种群，而不是单个解；

(3)遗传算法只使用报酬信息〔适值函数〕，不使用导数或其他辅助知识；

(4)遗传算法采用概率的，而不是确定的状态转移规那么。

遗传算法特别适用于传统搜索方法难以解决的复杂的和非线性的问题，可广泛用于组合优化、自适应控制、规划设计和人工生命等领域。作为一种随机优化技术在解优化问题中显示了优于传统优化算法的性能，遗传算法的一个显著优势是不需要目标函数明确的数学方程和导数表达式，同时又是一种全局寻优算法，不会象某些传统算法易于陷入局部最优解。

遗传算法是具有“生成+检测〞(generate-and-test)的迭代过程的搜索算法。遗传算法中包含了如下5个根本要素：1)参数编码；2)初始群体的设定；3)适应度函数的设计；4)遗传操作设计；5〕控制参数设定(主要是指群体大小和使用遗传操作的概率等)。这5个要素构成了遗传算法的核心内容。4.1遗传算法的根本思想遗传算法是受生物进化学说和遗传学说启发而开展起来的，基于适者生存思想的一种较通用的问题求解方法。利用遗传算法进行寻优时，编码、选择、交叉、变异是四个重要步骤。遗传算法作为一种全局优化搜索方法，具有简单、通用普适性强，适用于并行处理和应用范围广等优点。遗传算法在优化领域表现出了其强大的能力，遗传算法仿照生物进化和遗传的规律，利用复制、交换和突变等操作，使优胜者繁殖，劣败者消失，一代代重复同样的操作，最终找出最优解。具有如下特点：

(1)遗传算法运算的是解集的编码，而不是解集本身；

(2)遗传算法的搜索始于解的一个种群，而不是单个解；

(3)遗传算法只使用报酬信息〔适值函数〕，不使用导数或其他辅助知识；

(4)遗传算法采用概率的，而不是确定的状态转移规那么。4.2遗传算法流程图图2遗传算法流程图5模型建立求解及实例应用5.1车辆调度模型根据上述对问题的描述，可以采用混合整数规划方法对车辆调度进行建模"设N为最小本钱，那么目标函数为满足约束条件1：式中：K为所有车辆的集合，；G为所有客户的集合，，，其中{0}代表配送中心；为由车辆k效劳的客户的集合；为车辆到达客户i的时间；为惩罚函数，车辆在时间到达客户i时所对应的惩罚本钱；为车辆从客户i到客户j的所有运输本钱；为车辆从客户i到客户j的行车时间；为客户i的需求量；Q为车辆k的最大装载量；为车辆在客户i处的停留的时间。另外，变量和的值为0或1。假设车辆k为客户i效劳，那么1，否那么为0，即：此变量表示车辆分配方案，可用布尔矩阵表示；假设车辆k经由客户i到客户j，那么为1，否那么为0，即：，表示车辆路线安排。约束条件2：保证每个客户均被效劳，而且每辆车都从配送中心出发；约束条件3：表示每辆车负责的客户点的货物需求量总和不超过该车辆的最大装载量；约束条件4、5：表示对任一由k效劳的客户点j必定有另一(而且只有一个)由k效劳的客户点(包括配送中心)I,车辆k从客户点i到达客户点j,而对由k效劳的客户点i同样存在由k效劳的另一客户点,车辆k是从该客户点到达客户点i的,依次类推；约束条件6：保证每辆车的行车路线的总耗时不超过一个事先定下的数值；约束条件7：对某个客户点，车辆到达时间限制在某一时间段内。根据实际情况，本文采用软限制时间窗，其惩罚函数如图2所示。其中，为客户所要求的送货时区，为时间窗，超过该范围客户将拒绝收货，因此设定一个极大的惩罚本钱以防止此情况的发生。图3惩罚函数5.2带时间窗的物流配送问题优化问题带时间窗VRP〔VRPwithTimeWindows，VRPTW〕是带装载能力约束的CVRP(CapacitatedVRP，CVRP)的扩展。在该类问题中，有车辆装载能力约束，且每个客户i都有一个与之相联系的时间区间[ai,bi]，称为时间窗。客户的效劳必须在相应的时间窗内开始，车辆必须在客户点停留的时间长度为si。按客户对物流中心违反时间窗约束规定时的接受程度，可分为硬时间窗、软时间窗和混合型时间窗。硬时间窗(HardTimeWindows)：指配送车辆必须在特定时间区段，将货物送达顾客手中，不管是迟到或早到都完全不予接受；软时间窗(SoftTimeWindows)：允许效劳的开始时间有所偏离时间窗，那么必须按照违反时间的长短施以一定的罚金或其他惩罚法那么；混合型时间窗〔MixedTimeWindows〕：是指系统中有些客户只接受硬时间窗效劳，有些客户接受软时间窗效劳，或者同一客户，往往软、硬两种时间窗效劳混合使用。如问题为硬时间窗问题，那么必须满足到客户i的时间要比承诺到达时间早，即到达i的时间≤到达i的最晚时间限制；如有紧急货物〔高优先级客户〕时，那么自动将优先级高的货物按优先级顺序排入队列前端，然后将其它普通货物再进行优化；即如有N个客户，其中有一个为紧急运单，那么自动将其放在队首，其他N-1个客户进行优化，即将问题降为N-1阶的路径优化问题；任一客户只由一台运输车辆提供效劳，即算法解决的是任一客户的货物需求均小于车辆最大负载〔容积〕的情况。如出现某客户需求量大于车辆负载〔容积〕的情况时，需要先派车为其运输，直至该客户剩余货物需求量小于车辆最大负载〔容积〕即可参加优化调度。5.3带时间窗的物流配送路径问题的遗传算法染色体结构编码根据物流配送路径优化问题的特点，本文采用了简单直观的自然数编码方法，用0表示配送中心，用1、2、…、L表示各需求点。由于在配送中心有m辆汽车，那么最多存在m条配送路径，每条配送路径都始于配送中心，也终于配送中心。为了在编码中反映车辆配送的路径，采用了增加m－1个虚拟配送中心的方法，分别用L＋1、L＋2、…、L＋K－l表示。这样，l、2、…、L＋m－l这L＋m－l个互不重复的自然数的随机排列就构成一个个体，并对应一种配送路径方案。例如，对于一个有6个需求点，用2辆汽车完成配送任务的问题，那么可用0、2、…、6(0表示配送中心)这7个自然数的随机排列表示物流配送路径方案。如个体0l26354表示的配送路径方案为：路径1：0-1-2-6，路径2：3-5-4共有2条配送路径；5.3.2种群的初始化群体初始化时，采用两种机制，一种是随机生成个体，一种是按前相插入启发式算法。本文采用随机产生一种l～L＋m－l这L＋m－l个互不重复的自然数的排列，即形成一个个体。设群体规模为M，那么通过随机产生M个这样的个体，即形成初始群体。5.3.3适应度分析初始种群形成以后，需要通过种群的适应度函数，对种群中的每个染色体进评价，并以此为标准选择最优解。由于适应度函数通常越大越好，而物流车辆路径优化问题那么是求最小经济本钱，为了便于计算且增大区分度，算法采用的是目标函数的倒数乘以区分度系数β作为适应度函数，即maxF=1/S*β(3-2-3-1)遗传算子1.遗传选择选择是用来确定重组或交叉个体，以及被选个体将产生多少个子代个体。新种群的产生是在上一代的根底上对原有的各染色体按其适应度大小进行保存，并将其进行交叉和变异形成新一代的个体；适应度计算之后是实际的选择，按照适应度进行父代个体的选择，本文由轮盘赌算法进行种子的选取；计算每个个体的相对适应度值，以之作为概率，将[0,1]空间划分成n份。生成一个[0,1]范围内的随机数，看它落在哪个区域，那么选择该个体。2.遗传基因的交叉对通过选择操作产生的新群体，需要进行配对交叉重组。简单的说就是人为选取较好的一对染色体作为新染色体的父母，按染色体按长度分为前后两段，取其中一个染色体的前半局部放在另一个染色体的前边，再顺序遍历新染色体的基因并剔除重复基因，从而得到新的染色体child1。同理，可以得到另一个新染色体child2。在得到新的两个染色体后，为了使下一代染色体具有更高的适应度，算法参加了淘汰机制，即比拟两个新染色体，保存较好的一个进入下一代，同时将较差的一个舍弃。在此引入新的CX交叉算子。实施交叉操作。其操作方法如下：首先，随机在父代染色体中选择一个交配区域，如两个父代染色体及交配区域选定为：A=35|6298|471B=83|2954|167其次，将B的交配区域加到A的前面，A的交配区域加到B的前面，得到：'A=2954|356298471'B=6298|832954167最后在'A，'B中自交配区域后依次删除与交配区域相同的自然数，得到最终的两个后代：C1=295436871C2=6298384173.遗传基因的变异基因的变异是在选出的染色体中按其变异概率随机找出假设干基因位置，再随机产生一个基因替换原有位置基因，并查找因替换基因产生的此基因的另一重复位置，修改使之成为一个不重复基因染色体。为了使后代继承更多的父代的基因信息，本文取变异概率Pm为0.02左右。5.3.5函数控制的终止条件优化算法的结束条件是系统设定的最大遗传代数。即事先设置一个最大代数，如当前代数大于最大代数时，算法停止。判断迭代的代数是否为要求代数maxt，假设是，停止进化，选性能最好的染色体所对应的路径集合，作为问题的优化解输出。5.3.6步骤Step1：t=0，利用自然数编码方式，采用前相插入启发式算法和随机的方式产生初始种群，并输入控制参数；Step2：计算个体适应度；Step3：t<maxt，t=t+1，那么转Step4；否那么停止计算，并输出结果；Step4：采用基于个体浓度的群体多样性保持策略来选择个体；Step5：对个体进行CX交叉重组；Step6：按照变异方法对个体进行变异；Step7：重复步骤2-6；6算法的建立和求解车辆优化调度问题由车辆分配和路线安排这两个相互关联的子问题组成，但关键是确定优化的车辆分配方案〔即求解变量〕。一旦车辆分配方案确定，那么路线安排问题也就比拟容易求解〔即求解变量〕。可以采用遗传算法的思想作为总体框架对该问题进行求解，用遗传算法求解变量，而变量那么用启发式算法求解。6.1编码操作遗传算法的关键之一是确定染色体并对它进行编码处理。对于车辆调度问题，可将求解变量看作染色体，因此，一条染色体就代表一种可能的车辆分配方案，然后可用布尔矩阵对该染色体的基因链进行编码。对于m辆车、n个客户的车辆分配,可表示成mn矩阵。例如，图1的布尔矩阵为即车辆1负责客户1和2，车辆2负责客户3、4和5.6.2定义适配值计算函数适应度函数是遗传算法中评价解集好坏的依据,适配值高的个体优先培养。在本问题中，对于种群数目为N的染色体群，其个体染色体i的适配值的值越小,那么表示个体适配值越高。个体适配值为式中，所以，目标函数生成初始染色体种群初始化遗传世代；每一代的染色体群的种群数目；交叉概率，变异概率等参数。随机产生初始车辆分配方案，并淘汰不符合约束条件的染色体,直到染色体群的种群数达N条。N的取值不宜过大或过小。过大不但增加计算量，而且不能有效地获得迭代解。过小将不能保证分配方案的多样性，本算法中取种群大小，交叉概率,变异概。6.3用启发式算法求解单一车辆排序问题对变量的求解实质上是一个带时间约束的单一车辆排序问题，即对中的元素进行排序，求解最小的，以满足约束条件。该子问题可表示为满足约束条件：本文采用文献[3]中的启发式方法进行求解。首先对中的元素按照客户要求到达的时间从小到大进行排序，如果有两个以上的客户要求到达的时间相同，那么对这些客户按照配送区域〔时区〕从小到大进行排序。淘汰不符合约束条件的解，调整次序重新搜索，直到找到较佳的可行解为止。对每一条染色体，求解变量，并计算每一条染色体的适配值：!6.4种群的选择与复制本算法采用与适配值成比例的概率方法，对种群的个体进行选择与复制。首先根据前面计算的计算个体i在下一代中应复制自身的比例；定义选择概率为个体适配值所占比例的反向排序$即适配值最小的车辆分配方案其选择概率最大；依据选择概率对种群中的个体进行复制，选择概率大的个体被重复复制的时机大，而选择概率小的个体那么趋向于减少或淘汰，直到复制N条染色体。6.5交叉操作由于复制操作并没有产生新的车辆分配方案，因此种群中最好的个体的适配值并没有降低。对染色体群实施交叉操作crossover〔〕可以产生新的体。以概率对染色体群随机地交换两个个体的某些片段产生新的个体染色体，即对选定的需进行交叉运算的每一组布尔矩阵随机设定交叉位置$通过交换布尔矩阵中的某些行或列的局部信息〔二进制位〕，其他位不变，从而生成两个新的布尔矩阵。交叉概率对算法的收敛有较大的影响，越大，优秀的个体出现的几率也越大，新旧个体替换快，算法收敛也快。的经验值为,效果较佳。6.6变异操作变异操作mutation〔〕以概率对染色体群中的某些染色体的某些位进行变异，产生新的个体染色体、作为交叉运算的补充，变异操作可增加车辆分配方案的多样性，克服求解可能出现的早熟和陷入局部最优解的现象。变异概率取不同的值对算法性能的影响很大；过大，求解时间明显增加$但算法收敛于局部最优的可能性减少。本文中，取,0.3变异操作mutation〔〕采用反顺序变异法改变布尔矩阵中的某些位〔1变成0,0变成1〕，产生新的布尔矩阵。算法停止准那么的设计淘汰不符合约束条件2〕、3〕的染色体。如果，那么转启发式算法求解，否那么在染色体群中选择最小的染色体，作为该问题的求解变量值；与该变量相对应的变量就是优化的路线安排。由于该算法属于种群非重叠&遗传操作重叠结构的SGA(simplegeneticalgorithm),并在选择操作前保存当前最好解:因此以概率收敛到全局最优解。6.7实例分析本文仍采用的经典测试集。用上述的带时间窗的遗传算法，对一个有8个客户和1个配送中心，两辆车〔容量均为8吨〕的配送系统的车辆路径问题进行求解。各客户的需求和各客户之间的距离如表1(其中0表示配送中心)，要求合理安排车辆的行驶路线，使总的运距最短。表1客户间距离表设置车辆数为3，最大负载10，车辆容积30，最大行驶距离为200，运输本钱系数4，平均时速为40，不考虑装卸及休息时间。种群设为40，最大代数为400，运输本钱参数设为3，时间惩罚参数设为6，并且第4次及第7次实验中人为设置较高变异率〔分别为0.089和0.100〕,以到达人为增加变异次数防止局部最优解的出现，共进行了八次运算，得到测试结果如下：表2优化结果表最终优化结果为需要调度两台车，得到的优化路径为O-A-C-E-H-B-O和O-F-G-D-O,运输长度为67.5，本钱为202.5。可经验证，该解正是问题的最优解。此实例引用了参考文献2中的经典案例，通过上面的具体实例，可以让我们对遗传算法在物流配送中的具体应用有了更深的理解。在物流配送业务中，合理确定配送路径是提高效劳质量、降低配送本钱、增加经济效益的重要手段。由于物流配送路径优化问题是一个NP难题，因此，采用启发式算法求解是一个重要的研究方向。所构造的物流配送路径优化的遗传算法，包括设计个体编码方法、个体适应度值的计算方法以及选择、交叉和变异算子，对解决类似的组合优化问题具有一定的参考价值。7结束语随着毕业日子的到来，毕业设计也接近了尾声。经过几周的奋战我的毕业设计终于完成了。在没有做毕业设计以前觉得毕业设计只是对这几年来所学知识的单纯总结，但是通过这次做毕业设计发现自己的看法有点太片面。毕业设计不仅是对前面所学知识的一种检验，而且也是对自己能力的一种提高。通过这次毕业设计使我明白了自己原来知识还比拟欠缺。自己要学习的