车辆路径问题的混合遗传粒子群算法

车辆路径问题的混合遗传一粒子群算法—HFUT论文翻译作业摘要：通常的遗传算法，具体的解并不在他们的生命周期内进化：它们被创建，评估，可能被选作为新解决方案的父代，然后被销毁。然而对Memetic算法和墓因局部搜索的研究表明，如果解能够被允许在其生命周期內迸行演化，性能可能会提高。我们逹议，解的提高可以通过对父代解的知识存储来获取帮助，以有效地让父代教他们的后代如何改善适应性。本文中，具体解通过应用粒于群算法来进化，即每个解都要按照PS()的基本原则进行物理运动，直到被要求去作为一个父代。因此，每个父代的知识，特别是一个非常适台父代，就有可能被捷移到其后代以及整个群体的于代中去，通过这种方式提出的算法有可能更有效的搜索解空间。这种想法被应用到一个经典的组合优化问题，即车辆路径问题，当应用于两个经典的基准实例集台时具有很好的效果。1•简介在过去的十几年中，由于先迸的信息系统设计智能范例利用，自然启发智力变得越来越流行。其中晨流行的自然启发方法是对动物和微生物的团队行为的表示，如群智能(鸟群或鱼群启发粒于群优化)、人工免疫系统、蜂群的性能优化、蚁群等等。但自然启发方法最流行的是遗传算法，它的应用十分广泛，在遗传算法和更普遍的进化计算的背景下，也实现丁许多新的思想。通常的遗传算法，我们有一些离散的阶段，即群的初始化，父代的选择，交叉算于，变异算于和每一代的更换。但两代之间又发生什么呢？如果我们想有一个完整的迸化算法,我们将要观察每个个体在其生命周期内的行为。在父代试图帮助他们的于女来学习和发展,而使其变得更具有竞争性，并有更多的可能性生存，来成为下一代的父代。有许多不同的方法可以用来完成一个进化算法，一种方法是独立的观察每个个体，个体间无任何交流与影响。在遗传算法的情况下，其实现是使用单一或更复杂的局部搜索策晒。另一种方法是让个体之间有一个相互作用。在本文中，这种互动利用粒于群优化算法来实现。在每一代中，所有的个体(父代和于女)被视为一个单一的群体，他们通过向群的最优部分运动来努力提高自己的解决方案(即后代学习他们的父代)。因此，在本文中我们着重于每个个体如何利用粒于群来进化。在每次的粒于群优化阶段结束时，整个群适者生存，并转移到下一阶段的遗传算法，即遗传算法的父代选择阶段。在算法的迸化部分应用PS()算法的优势是，与其他超启发式算法相比，对于群体中的每个个体只有两种变長在迭代中雷要计算，即位直和速度。经常用Memetic算法(带有局部搜索阶段的遗传算法)来代替典型的遗传算法使用的原因是，纯粹的遗传算法很碓有效的探索解空间。全局优化算法与局部优化算法的结台往往能够提高算法的性能。在本文中，我们用丁一个全局搜索算法即PS()代替局部搜索算法来分别改迸每个个体。因此每个个体并不通过自身来改善解，而是利用整个群体的解的知识。我们的另一个目标是在较短的计算时间内得到进可能好的结果。这个目标使我们使用两个不同的程序，一是加速技术(扩张邻域搜索七NS),另一个用于产生尽可能奸的初始解(MPNS-GRASP)。因此，遗传算法和一个非常快的局部搜索策珀的PSO算法相结台，如扩大邻域搜索策珀(［Marinakis等，2005］和［Marinakis等，2005年)，将产生非常快速和有效的算法，并将减少解决大规模的车辆路径算法的计算时间，以及更多的圉难的组台优化问题。本文下面的组织结构为：下一节将具体描述车辆路径问题，第三部分中，算法hybridgeneric-PS()-GRASP-ENS(HybGENPSO)被提出并详细描述。实验结果将在第四部分

展示和分析，最后一部分得出结论以尺对未来的展望。2•车辆站径问题VRP和CVRP问题经常被描述为，车辆墓于中心仓库，要求到达地理位直不同客户以满足客户的雷求。令G=（\\E）表示一个图，其中皓“丿2,…厶｝表示定点集台，01代表仓库客户位賣表示为i2,…,in）,E=｛（il,im）:iltimLV｝表示边的集合。每个客户必须被分配一个确切的车辆，每辆车分配的载長不能超过其容長（QQ,如果每辆车都是同质的则容長相等记为Q。需求M1以及服务时间si）分配给每个客户节点i.o仓库节点的雷求長M1和服务时间Sil设賣为0,h和讣之间的运输费用记为Gm。A表示车辆k被允许的路线上的舅大时间。该问题是建立一个低成本的，对每一辆车都可行的路线。一条路线是一个地点的序列，车辆必须根据它提供的服务来访问路线，如果边側/耐被车辆k经过则晝变星为1,否则为0。车辆必须在仓库处结束其行程。下面我们用数学公式来描述VRP问题。J=min^S5Z"sins.t.力9|£4|wa,k=1,s.t.力9|£4|wa,k=1,•…Klf-1b4-】 if-l4«-lJi〉］址”W1,k二31,•.-,上fcn-2nwi,K=i….,k—XeSxj,,=0or1forall(1)(2)⑶(4)(5)(6)⑺(8)⑼(10)目标函数（1）指出，总距商要尽星减少。等式（2）和（3）确保每个有需求的节点会得到一个车辆的服务。（4）表示路线的连续性，即一辆车进入壽求节点后必须从该节点出来。公式（5）表示车辆的容長约束，式于（(1)(2)⑶(4)(5)(6)⑺(8)⑼(10)VRP问题首先由丹捷格和拉姆瑟（1959）提出。由于这是一个NP-难问题，提出了大批近似技术。这些技术大体可分为两大类：一是经典启发式算法，主要发展于I960年至1990年，以及罠近15年才发展的超启发式算法，该算法可以根据使用的策略不同来分类。禁忌搜索策略是比较常用的技术，很多研究人员提出丁很多有效的禁忌搜索算法的变种。一些有趣的高效的算法也被提出，基于自适应记忆的概念，将高质長的VRP解存在里面，并在解得过程中用更好的解来代替它。模拟退火，贪婪随机自适应搜索过程和阈值接收算法也有效地应用于VRP求解。在过去10多年中，自然启发超启发式算法巳用于VRP问题的求解过程。黒常用的自然启发算法是遗传算法，蚁群优化，蜜蜂交配优化，以及其他进化技术。读者可以很容易从现存的论文书籍中找到对这些算法的详细描述。3.应用于VRP问题一种混台算法(Hybridgeneric-PSO-GRASP-ENS)Hybridgenetic-PSO-GRASP-ENS(HybGENPSO)的整体描述该算法结台了遗传算法，MPNS-GILASP算法，邻域扩张搜索策略和粒于群优化算法。接下来，将列出算法的提纲。初始化创建初始种群的P个个体，使用的多阶段邻域搜索-GRASP(MPNS-GRASP)0评价每个个体的适应性。运用粒于群优化策珀改善每个个体的适应性。主算法设直generations为0.如果不满足终止条件，继续循环2.1如果父代仍在选择和交配，继续循环2.1.1通过轮盘赌的方式从群体中选择两个作为父代2.1.2对两个父代迸行交叉操作，首先将两个父代的共同特征克隆到后代，然后使用ENS的算法完成后代。2.1.3通过突变操作(扩张邻域搜索)改进后代，并将其结果插入到群体中。ENDDO2.3通过粒于群优化策珀，提高新群体中每个个体(父代和后代)的适应性。2.4根据适应性函数对于代和父代迸行排序，然后选择与初始群体数目相等的个体作为新群体。2.5代的数目加一。ENDDO返回昼好的个体3.2路径表7JT在为某一问题设计遗传算法时，第一步就是设计合适的候选解的表示。例如Vrp情况下，每个个体(旅行)通过旅行的路径来表示，即通过一个特殊的点序列。有丁这种表示,有2n种方式来表示相同的旅行，其取决于哪个节点被放置在位直1和旅行走向哪个方向，其中n是节点数。该算法，与1号节点固定在了每一个人，总是克服代表性位直1,因此，同一旅游多种编码的障碍，克服了很多冗余的解决方案的代表性。在提出的算法中，表示每个个体时，1号节点就被固定于位直1,这样就可以克服相同旅行有多个编码的障碍，克服解表示的冗余。群初始化-MPNS-GRASP通常的遗传算法，随机产生初始化群，其中不能确保包含奸的候选解，为防止这种情况，一种贪心随机自适应搜索算法的修改版本，多阶段邻域搜索-GRASP被用于初始化群体。grasp是一种迭代的两阶段搜索算法。每次迭代由两个阶段构成，构逹阶段和局部搜索阶段，在构建阶段中，用一个随机贪心函教来构逹一个初始解。该随机技术每次迭代中都产生一个可行的解，该解通过经过局部搜索阶段来提高。最后的结果就是所有迭代过程中晨优的解。构建过程可被描述为一个逐步的过程，它一次増加一个元素到一个非完整解。下一个要被加入的元素通过排序所有元素来选择，根据贪心函数，将一个昱好的元素放于有限候选列表RCL中，然后从表中随机选择。这个RCL由可能是好的P元素构成。最后RCL每次迭代都通过用不属于RCL中的边替换掉包含在巡回中的边来调整，命君为第(D+m)条边，其中m表示目前迭代的次数。用于解决何P问题的贪心算法是一个简单的过程。在第二阶段，局部搜索从这些点初始化，最终结果是整个搜索过程的舅优解。MPNS-GRASP介绍丁应用多目标函数来替代经典方法中的简单贪心函数的灵活性，而且组台贪心算法也是可行的。算法开始于一个贪心算法，如果结果没有改善，则利用一个多目标贪心函数来替代。墓于这些贪心函数忽路VRP问题的边约束，可解决一个TSP问题。因此可以通过增加边约束来讲一个TSP问题捷化为VRP问题。更精确一点，第一辆车从代表仓库的节点出发，并基于TSP的解来移到下一个节点，检査车辆的容長或最大陷线长度是否满足约束。不满足任一约束则车辆返回仓库节点，开始一个新的路线。经典算法的第二阶段，简单局部搜索局受限于获得好解的机会，因此MPNS-C；RASP经常用扩张邻域搜索来代替，这是一种很灵活的局部搜索策晒。3.4适应度函数的计算在\EP中，每个个体初始适应度与每个旅行的路线长度有关。每个个体S的适应值由下式计算：FiuicsSs^Jnur.L+l其中Jx是群体中最大花费的个体的目标函数值，J,是当前个体的函数值。注意，选择个体去交配的可能性依翰于其适应值，并且花费昙高的个体的适应宜为0,它永远不会被选择，因此，加1来保证最坏的解不会完全剔除。3.5选择概率选择机制用于选择父代的染色体，并构逹杂交池。在以后的进化中更适应的染色体有较高的几率存活。本文中，我们使用简单常用的轮盘赌方式来作为选择机制。3.6交叉算于我们提出一个交叉操作来首先标示父代个体的共同待征，然后将其复制到后代。交叉操作是一种自适应记忆过程。开始时，自适应记忆被作为解决VRP问题禁忌搜索超启发算法的一部分提出来的。该过程存储了奸解的特征。每发现一个新的奸解，自适应记忆就会更新。对于我们来说，第一代的自适应记忆为空。为了向其中加入一个或部分解，有几种更可能行：加入其中的候选解是前面最好的解，但它的花费至少比目前景奸的解坏10%。加入其中的候选解是群体中的一员，其花费同样至少比最优解坏10%。一条路径与最优解及很多个体的相同详加分析，在交叉操作中，点是由自适应记忆各个个体以及最优解中随机选择的。因此首先选择两个交叉算于(C“，Cr2)来控制用于自适应记忆、个体和最优無的部分参数。如果解之间有相同的部分则相同的部分遗传与下一代，否则6、6的值与一个随机数产生器的输出比较，rand(0,l)。如果随机数不大与Cn,则相应的值从是好的解中遗传，若介于两者之间，遗传的值为自适应记忆中的随机的一个解，否则从其他个体的解中随机选择。因此如果于代解表示为()i(t),最优个体解bi.(t),自适应记忆解涸(t),一个其他个体的解p.(t)：(bij(t),ifrandj(O.l)冬Cr】Oj(t)=•<adj(t),ifCr,<randj(0.1)wCr2 (12)(otherwise.每次迭代自适应记忆基于最优解来更新，交叉操作后，计算于代的适应度函数，如果比父代好，变長被选择为下一代，否则父代至少多存活一代。3.7扩张邻域搜索本文用的局部搜索方法为扩张邻域搜索，ENS是一种超启发式算法，可以用来解决很多组合优化问题。该算法的主要特征：(a)运用圏限制局部搜索移动策瓠(b)有在不同局部搜索策晒间变动的能力。(c)运用扩张策晒。这些特征将在下面祥加介绍。圏受限局部搜索移动(CRLSM)策珀中，计算时间比其他启发算法或超启发算法要少，因为所有不能改善解得边都在搜索过程中剔除丁。它将搜索空间约束到侯选删除边的周围。在2r)pt局部搜索算法中，只有一种可能性来减少解得花费。即至少一条边花费比两边中的一个少，并且另一^的花费比两个旧边的总花费少。因此CRLSM策珀中，对所有的局部搜索策晒，翹在候选删除边的终节点周围产生，只有睡内的节点才被用干寻找更好解的过程中。为丁减少更多的计算时间，并且在候选删除边终结点附近很可能找到一个更好的解，我们开始不用最大的可行匱，而是用较小的圏来寻找更优解。例如，在2-opt算法中，如果候选删除边的长度为A,则圈初始半径为A/2,然后，局部搜索策菇按如下描述应用，并且如果解在圏内无法改善，圈按介％扩展后，该算法继续。直到魔达到最大可能直径，A+B,其中B是另一个候选删除边的长度。ENS算法有能力在不同局部搜索策略间变动。Garfinkcl和Ncmhauscr首先提出一种非常简单的方式来使用一个更大的邻域。通常来说，局部优化发现中使用一个邻域，然后一个更大的邻域在试图挣脱局部优化时使用。有人提出一个系统的方法来在不同的邻域间变换，叫做变种邻域搜索。在扩张邻域搜索中一些局部搜索策略被应用于匱内。工作过程如下：首先当前解的一条边被选中(例如昙差长度的边)并且应用第一种局部搜索策晒。如果用这种策菇没有发现一个更好的解，对同一条边就会选用另一种局部搜索策略。该过程一宜持续到有一个更奸的解被找到，或者所有的局部搜索策略都巳经用到了。第一种情况中，解得到更新，选出一个新的边，然后开始新一轮的扩张邻域搜索策路，第二种情况中，将圏扩大后再使用局部搜索策路，直到找到一个更奸的解或者圈巳经达到最大可能直径。如果巳经达到最大可能直径，则选择一个新的候选删除边。用于VRP的扩张邻域搜索的局部搜索策陪分为单一路线和多重跖线的局部搜索策晒。属于第一类的局部搜索算法是解决TSP的常用算法，2-opi和3-opt步操作。在单一路线交换中所有的路线在算法的初始阶段生成。单一站线交换的局部搜索策晒试图提高站由决策。多站由交换试图提高委派决策。这样自然会增加算法的复杂性，但能够更奸的改善解。多重站由交互策路允许上坡下坡动作，单路线交互局部搜索策略只允许下坡动作。所用的多重:路由交换局部搜索策路是1-0重新部詈,2-0重新部署,1-1交换,2-2交换。

aA+BnopossibleimprovememincostFig.I.expandingneighborhoodsearchaA+BnopossibleimprovememincostFig.I.expandingneighborhoodsearchmethod.3.8群演化-粒于群优化粒于群优化(PSO)是一种基于群的群体智能算法。它最初是作为社会有机体的社会行为由肯尼迪和埃伯哈特提出的。利用粒于薛中个体的物理运动，具有灵活的平衡机制，以提高全局适应性和局部探测能力。由于其易于实现和廉价的计算，编码性能的一致性和简单性，粒于群已被证明是一个为在连续空间优化问题的有效、有竞争力的算法。PS()算法的大多数应用程序都集中于连续空间的优化，同时，最近对于商散优化问题也有所研究。自推出以来，PS()算法巳得到迅速普及，通过与其他超启发式演算法比较，被证明是有竞争力和有效的优化算法。粒于群优化算法首先随机初始化粒于群。在问题空间(i=i,2,..N;N为人口数目)中每个个体(叫做粒于)用一个d维的变長表示，并且通过预定义的适应度函数来进行评价。因此，每个粒于随机的分布在d维空间中作为一个候选解。第i个粒于的速度W定义为其位直的变化。每个粒于的飞行方向，通过个体和整体的飞行经验来动态交互确定。该算法通过个体最优無和全局最优無完成优化。每个粒于的运动轨迹根据自己先前的最奸位直和全局的景好位直来调整，分别记为pg和Pr,每次迭代中群通过下式来更新。(13)(14)Vid(t+l)=yd(t)+cinindl(Hd-Sid(t))+c2rand2(P护-(13)(14)Sjd(t+l)=Sjd(t)+Vj<|(t+l)其中t表示迭代次数,cl和c2加速系数，randl和rand2是【0,1】之间产生的随机数。加速系数cl和c2决定了粒于一次迭代移动的距离。低值允许粒于在被拽回来之前能够在远商目标区域的地方漫游，反之则要求迅速移向过去悬奸位直或目标位直。典型的值为2.0,亘然分配不同的值绐加速系数有时会提高性能。基础PS()算法及其变种已经成功运用于连续优化函数。为了将应用扩展到商散空间，肯尼迪和埃伯哈特提出了商散二进制版本的PSO,其中粒于群的状态空间每个维局限于1和0,w表示速度变为1的概率。粒于的轨迹定义为可能性的变化，W度長目前个体直为1的可能性。速度越大，越可能选择1,越低越可能选择0。应用一个sig函数将速度从实数空间转化到概率空间。

sig(g=l+exp(-v.J(15)sig(g=l+exp(-v.J(15)在二进制版本的pso中，粒于的速度和位宣根据下式更新:vyrf(/+l)=\Wjd⑴十c"dl(PM-Sjd(t))+c2rand2(pqd_%〃(/)) (16)(17)F仃+H=,如果rand3<^g(t”jdU丁》_S,如果“M3Nsig(Vjd)(17)其中sjd属于{0,1},vjd表示速度，sig(vjd)根据15式计算，rand3是0到1间随机分配的一个数。在基本的PS(),—个参数Umax用来限制vjd,这样sig(vjd)就不会过于秦近0或1。这种机制可以保证二迸制数积极地在0和1之间转换，Umax经常设宣为4。本文提出的算法是基于标准PS()的，君为带惯性权重的基本PSO,其中歳为惯性权重。惯性松重用以控制先前的速度对目前速度的影响，通常作为一个控制平衡的参教。粒于根据其历史最优和其他粒于的最优信息来调整其运动轨迹。惯性权重弱也被用来控制PSO的收敛行为。为了随着迭代而改变权重歳，以允许算法探索细节区域，权重弱可按下式更新：%n(18)%n(18)其中Wmax,VCmin是惯性权重可以取的景大最小值，i是目前迭代的次数，itcrnw:是最大的迭代的次数。其中一个要处理的主要问题是如何将粒于从目前的解，移动到全局最优(整个群的果优解)或局部最佳(每个粒于的最佳解)。通常在一个离散粒于群中使用(17)式。混台遗传粒于群算法，使用路径重新链接策珀代替这个公式。路径重新连接是加强战略，作为一个在优秀解之间探索轨迹的方式使用。因此，每个粒于当前解使用这一战晒与全球或局部最优解结台。这种方法通过连接高品质解来探索轨迹，并生成新的解。从一个初始解出发,在邻域空间生成路径得到另一个解，称为目标解。初始無和目标解的角色可以交换。首先,选两个解黒差的为初始解，另一个为目标解。其次，角色发生变化。有两个途径同时探索的可能性。以粒于群优化粒于可以继续自己的方式，或返回到其以前的最佳解，或靠近全局最优解(到在群是好的粒于)。因此，在混台遗传粒于群中，粒于无论跟随以往的最优解或全局黒优解的路径，当当前解作为初始解，最优無作为目标解时，应用了站径重新连接的策晒。两个解之间的轨迹探测通过简单的交换初始解得两个节点，直到与目标解相同。如果一些重新连接中产生一个新的最优解，无论是粒于或全体群，则目前景优铮被代替，算法继续。3.9群体替换和进程终止就如上一节提到的，所有粒于在交叉变异后，并通过PSO算法来演化。然后更适应环境的个体将有更大的生存和繁喳机会，否则就会被淘汰。开始所有个体按照适应值排序，然后选P个晨好的个体替代旧的群体。当达到预定的最大迭代次数或收敛时，算法中止。4•计算结果整个算法用Fortrai^O语言执行，并使用处理器为1.86GHz的运行SUSELinux9.1的雷希f95编译器来编译。该算法的参数选择经过充分的测试。对一组不同值的数据迸行丁测试,并选择那些解质長较奸和计算所雷的时间较少的计算结果。因此，所选的参数见表1。最终

参数选定后，根据不同的参教运行5()次。该算法在两类基淮问题上进行丁测试。赫里斯托菲等人提出的14个基准问题，金等人提出20个大型车辆站由问题。第一组的每个实例包含51到200个节点，包括仓库节点。每个问题包括能力限制的问题，同时问题6-10.13、14有最大路线约束以及非零服务次数。第二组的实例包含200到483个节点，每个问题实例包括容長约束，同时前8个有最长路线约束，以及0服务次数。产生的解得质長为=^KS/C；其中cHybGENPSO表示由HybGENPSO算法找到的解的成本，cBKS表示知道的呈优解的成本。Table1Parametervalues.ParameterValueNumberofgenerarionsforPSO20Numberofgeneradonsforgeneticalgorithm50Populationsizeofgeneticalgorithm100Numberofswarms1Numberofparticlesequaltopopulationsize100Probabilityofcrossover0.8Probabilityofmutarion0.25G2C22Wmn0.01Wg0.9SizeofR.CL50910%Table2Resultsofhybridgenetic-PSO-GR.^P-ENS:HybGENPSO：inrhe14Chrincfidesbenclmarkins^nces.CRJ(min)Nod.Cep.m.t.1.s.tHyb Hyb BKSCRJ(min)GENPSOaverageGEXrPSObest51601Io・nJ1ooo400122o1ADIBIAvn加5710:520c:220016014020020020020086030800X2I222X10o0022101J12002005090524.61524.61835.2651601Io・nJ1ooo400122o1ADIBIAvn加5710:520c:220016014020020020020086030800X2I222X10o0022101J12002005090524.61524.61835.26835.26826.25S26.141029.171028.421295381294.21555.43555.43909.68909.68866.76865.941164.211163.411398.271397.511043.211042.11820.01819.561545.171544.57866.37856.37524.61RochatandTaillard；1995)835.26RochatandTaiLaid(1995)RochatandTaillard(1965)1028.42RochatandTail'-ard(1995)1291.29RochatandTaiLard:：1995)555.43RochatandTaiLardf1995)909.68RoctiacandTaiBard(1995)865.94RochatandTaillard(1995)1162.55RochatandlaiLard[1995；1395.85RochatandTailard(1995}1042.11RochatandTaillard(1995)819.56RochatandIail：ard(1995)RbchatandTailkid(1S85)86637RochatandTailiardU995)0.00§172009471DD3ooo111CSQQaQaQaaQ05

ao60.2aDO0.000.000.000.00牆0.000.000.070.120.000.0020.20.C071UH.2462553400030$62Q1h3Qft1*1AuQ5..51ft40IMc3RrsuksofHybndGene::c-PSO-GRASP-ESS(H>tGESP50)inthe20benchmarkGoldeninstancri.CMJ(min)CMJ(min)CENPSOjveugeCENPSObes:8521357328495-46I348S445I434378966S71284512.6.7.11乙6.1Z3.&3.8521357328495-46I348S445I434378966S71284512.6.7.11乙6.1Z3.&3.乙7.oi2.z3.5.6B94093107741359287I-,•••352639667677756846QQaQOQQaaaaQQaaaaaaQ55065005673.21567Q385627.54MesterandBrapy(20078444.50Pans(20C€)7009C008466.268459.739001200011112.34H10I.12H03&22Rc;mannetd.：2004)10001600013696.1713698.17□624.52Pdns(2(XM)90018000646U98646U98M60.98 andxuanoudls(2002900150008473JI847Q648412.8Prins(2001；9001300010Q18J310215.1410181.75Pisit^crandRapkc：2OO7)H64190Pans(20C€)9001200011765JI11750.381000X0586.B7586,875fi3.39Me«er2ndBrapy(2007)10002C0747.18746.56741.56Mester2ndBrapy(2007)1000X0926.01925.32918.45MencrendBrjpy(2007)1000X01115.7811)4.31】107.19Mesterand盯aysy(2007)1000X0866.38865.19&S9.11Mester2ndB：aysy(2007)1000X01O9U231C69.2】1C€1.31Mester2ndB；aysy(2007)!000X01355.28□55^S1345.23Mester2ndIkaysy(2007)!000X01634.49163271622.69\fcterindDpysv(2007)200X0713.72712.16707.79Mester«ndBwysy(2007)2002C01007.391006.31997.52MesterandBpysy(2005)200X01375.291373.24；36686M«【erandBays>-(2007)200X01832.291831.171820.09Ws⑹andBraysy(2007)4020g80oo8060MO552399835220968040360M2344223423342334233巾在表2和表3的第一列表示每个实例节点数，而在第二，第三和第四列是重要的特征,即车辆最大容長、最大长度以及每辆车的服务时间。后面的6个栏目，对算法（第5栏）的50次运行的平均结果，算法的最好结果（第6栏），是好巳知解（BKS-第7栏），平均运行质長（oav-8栏）最好的质旻（3-9栏）和最好运行时间（列10）。从表2可以看出，该算法，在第一组的情况下的14个中10个已达到巳知最优解。至于其他四个实例的最佳解,运行质長介于0.07%和0.23%,而14个实例的平均质長是0.046%o对于20个大型路由问题（表3）,该算法的车辆已经找到了其中一个最知若的解，为其余的质長介于0.26%和1-04%,而为20情况下的平均运行质旻是0.60%o此外，在这些表中也需要计算所雲的时间。所需的CPU时间是很少的，只有第一组的两个实例5和10有点增加，但仍然是非常有效的。在第二组的情况下，问题更复杂，因此，计算时间有所增加，但所有的实例仍低于10分钟。这些结果表明了该算法的有效性。在9个在所有50个运行实例都设貫算法找到了景有效的解。在大長实例情况下算法只在一个或两个上没有找到最佳解。然而，即使是晨好的解并非在所有运行中发现，但找到的解与最佳無时非常接近的。应当指出，我们想提出一个非常快速和有效的算法，因而，参教的选择要在得到尽可能奸的结果下，结台考虑收敛速度。这个问题有时会导致该算法找不到是佳解。如果我们增加了粒于数和迭代数提高丁算法的解，但随后会发现找到这些解雷要更多的计算时间。为了证明HybGENPSO的贡献，我们分别执行主要阶段并与HybGENPSO的结果进行比较。有两个非进化算法，扩展邻域搜索（ENS）（表4和表5的第1列和第2列）和多阶段邻域搜索-GRASP（MPNS-GRASP）（表4和表5的3、4列）和3个进化算法，混台遗传巨猿-ENS的（HybGEN）（第5和第6列），遗传-粒于群优化-算法（第7、8列）和GEN-PSO-ENS算法（第9、10列）。HybGEN和HybGENPSO之间的唯一的区别是在于群是否通过粒于群优化算法实现进化，而GEX-PSO和HybGENPSO不同的是，在GEN-PSO中MPNS-GRASP和ENS根本没用到。呈后，GEN-PSO-ENS和HybGENPSO不同的是，GEN-PSO-ENS中初始化阶段的MPNS-GRASP根本没有使用。在所有的实现中，这些参数都以这样一种方式选择，即在所有算法作出相同教目的评估函数。该参数不影响评价函数的教目，如RCL等。设直参数和局部搜索策珀与HybGENPSQ相同。为了使HybGEN和HybGENPSO的评价函教肃穆相同，我们在HvbGEN中增加了个体和迭代数目。

!abk4ConparisencftheproposeddlgohthmwithEAS.MPSS-GRAS?,H>bGEN.CEN-PSD”dGIN-PSO-ENSinthe14Christofid«benchmarkmsunces.ENS a MFNS eu H>t> a GEN m GEN a H>t gGRASP GEN PSO PSO GENENS PSO524.610.00324524.610.00324血aoo324.61837.5602?S)639anS35.26mi40.00626.14aoo826.141034.48Q58101224037102S421316.181.911114251.781299.21555.430.0055543aoo55543909.680.00909A8aoo909.68883.27Q26865S4aoo865.411178.861.401175861.141165.131416.H1.451412.111.161402.271043.53ai31042.11aoo1042.11824.57a^iS21.Uai9H19M1531.24Q63154830XJ71545.0?872.14066$68“02SS66.37OJOO鴛腊OJOOOJOOOJOO粽s?2524.6!aoo324.61aoo524^1835J6aooS35.26aoo⑷26ai4827.100.12826.141033.370.481029.37ao91026^21321.282321297380.47129421555.43aoo555.43aoo55543909.68aoo909.68aoo9旳朋E65.94aoo865.94aoo865941174.121.001165.010.211163^11395.2!Q24139821ai71397.511042.11aoo11M2.11aoo1042.11822.21anS2U360.121345.26a271544X)80.231544.57S67.2Iaio■66.”aa286637IableSComparisonMiheproposedalgoiunmwithENS.MPNS-GRASP.HybGEN.CEX-PSOandCEN-PSO-ENSnthe20Golden^stances.Dis IableSComparisonMiheproposedalgoiunmwithENS.MPNS-GRASP.HybGEN.CEX-PSOandCEN-PSO-ENSnthe20Golden^stances.Dis w MPNS £ Hyb » GEN : GENGRASP GEN PSO PSOESSC2JHyb

GENPSO5740.455715.191.565740.455715.191.5656E9581.105721.178518.21849Q15Q548459.73ai88489.21111852411144.39Q981110).12as911221.12137852313752.24加13698.17a5413701.2864B5.986475.190.22646O.$d0.006474.21&50335849228QM8470X54Q6984893210296」810275.17Cl9210215.14Q331027721)202).18H9I&152.3611878212.0111909.255952758931.1258637060587.2175938749.151XE746.56067748.21937.18935.231.B392552Q779144S1151.B1137.172.71I1332S236H3&21M2.17875.141.87868.171.05871.281101.121098.951.6310M371.251095.21082341369.161.78136428M21366J31GS82116S1.141.751644.171.321645.2471926713.161XM712.1SQ62721.28102S.1S1011171.571(Xd.l91.0?10ia2!1395.161384.181J7137821Q83BBQ0!1843251S35.18M31835.170831815.171.66a531.6Ba56a20a91z2.28a65ol901.7迪1.41.21.55皿A1Ja96083569921