遗传算子在VRP中的应用综述

郝友文，刘 烨

（天津工业大学 管理学院；天津 300387）

物流业与一个国家的经济发展水平是正相关关系，经济发展程度越高，对物流业的依赖程度也会越高。而近些年来无论是我国经济发展的规模、速度、样式，还是从社会物流总费用占GDP的比重在我国与发达国家之间存在巨大差距的形势来看，提高物流业发展速度和水平都已是迫在眉睫。

运输费用在我国物流总费用中所占的比重是最大的，而车辆路径问题（VRP）无论是在提高顾客满意度方面还是在缩减物流成本方面都在物流运输中起着最为重要的作用。这也就是VRP近些年来成为管理科学、交通运输、物流管理等学科研究的一个热点的原因所在。

鉴于传统的精确算法在求解VRP时，在求解效率、速度、求解规模等方面所表现出的不足，启发式算法成为目前解决VRP时最为合适的算法。国内外学者们在解决VRP时用到的启发式算法有遗传算法、禁忌搜索算法等等，这些算法相较传统精确算法在求解效率、求解速度、求解问题规模等方面，均表现出了更优越的性能，而应用最为广泛的当属遗传算法。本文在国内外采用遗传算法解决VRP的研究成果基础上，对遗传算法的三种算子选择算子、交叉算子和变异算子在VRP中的不同应用情况进行了较为全面的综述。

一、选择算子

选择又称复制，就是从种群中选择生命力强（适应度高）的个体来产生新群体的过程。选择算子的好坏会直接影响到遗传算法的计算结果。好的选择算子能够提高全局的收敛性和计算效率，避免有用遗传信息的丢失，而不好的选择算子就会导致遗传进化停滞不前，产生早熟问题和丧失遗传的多样性。

姜大立等人在解决带软时间窗的物流配送中心车辆路径问题时采用了比例选择算子［1］（轮盘赌选择算子），该算子是一种随机回访式采样方法，旋转轮盘赌pop-size（种群规模）次，每次旋转选一个进入下一代种群。曹［2］在求解物流配送VRP时运用了精华模型和比例选择相结合的选择策略（即最佳染色体保留及轮盘赌选择法相结合的选择策略）。具体来说就是，将每代种群种群的pop_size个个体按照它们的适应度大小进行排序，把适应度最大的个体直接复制到下一代的种群中，剩余的pop_size-1个个体按照轮盘赌选择的策略选择若干进入到下一代。肖天国［3］在求解带软时间窗的开放式车辆路径问题时，采用了基于排序法的轮盘赌选择法和最佳保留策略相结合的选择算子。基于排序的轮盘赌选择法的中心思想就是：为了使得选择个体时所产生的随机数字能够更均匀的分布在选择区间内（此区间一般是［0，1］ ），就先把该区间划分成大小相等的若干个子区间，之后再随机产生该选择数，该法有利于保持种群的多样性。最佳保留策略有利于遗传算法能够依概率收敛到全局最优解。但是最佳保留策略在具体的实施过程中会有一些差异，而这些差异一般体现在：哪个或哪几个染色体不参与交叉运算和变异运算、哪个染色体取代哪个染色体等方面，详细情况在此不作赘述。占书芳［4］在求解带软时间窗车辆路径问题时，运用了精英策略（即最佳保留策略）和随机联赛选择机制的混合法来作为选择个体的依据。随机联赛选择机制的基本思想就是，每次选取联赛规模（一般取2）个个体进行适应度值的比较，取适应度最大的一个个体来作为遗传到下一代群体中的对象。该方法的操作过程较为简单，只有个体适应度间的大小比较运算而无个体适应度间的算术运算。随机联赛选择机制的意义还在于较优的个体就会有较大的优先权来产生自己的后代。范月林等［5］在解决带时间窗的车辆路径问题时，采用了基于基因库的跨世代精英选择算子。基本做法是：建立世代基因库以用来存储遗传进化过程中适应度相对较高的精英染色体，设置好基因库的大小（比如20）并将库中的染色体按适应度大小排好序，每次更新基因库时将新染色体插入库中并剔除掉库中适应度最小的染色体，这样整个基因库的平均适应度就会越来越高，在染色体的选择过程中要把基因库的染色体与其他普通染色体混合，用于进一步的进化。周艳聪［6］在解决物流配送路径优化问题时，采用了小生境选择机制与最优个体保留、轮盘赌选择相结合的策略。该策略主要是用于摆脱以适应度为引导的选择机制所产生的“近亲繁殖”现象，用在交叉前两个父本的选择上，通过设置一个阀值来避免相似个体间的交配与再出现情况。经过试验也验证了，在该选择策略的配合下，的确能够提高算法的收敛速度、增强种群的多样性以及全局寻优能力。

二、交叉算子

交叉是指以较大的概率从群体中选择两个个体，交换两个个体的某个或某些基因位，从而形成两个新个体的过程。它在遗传算法中起着关键作用，是产生新个体的主要方法，也是遗传算法区别于其他进化运算的重要特征。交叉算子的设计和实现与具体问题密切相关，主要涉及到交叉点的位置和如何交换部分基因等。交叉算子的设计一定要与编码的设计一同考虑，而国内外学者在VRP上一般都采用了自然数编码方式。以下便综述了遗传算法在VRP的应用中交叉算子的设计情况：

对于VRP，由于虚拟节点基因（配送中心）“0”的存在，普通的交叉算子很容易会产生一些不可行解。为了提高遗传算法的收敛速度，保留好双亲的优良染色体序列，杨爱梅［7］在其论文中采用了2—交叉算子。为了不丢失优良基因，在交叉操作过程中保留一部分优良的父代个体的优良基因段，钟石泉［8］在其论文中运用了改进的最大保留交叉算子。曹［7］运用遗传算法解决带时间窗的同时取送货车辆路径问题时设计了前置交叉算子，该交叉算子的引入能够解决即使选取的双亲染色体序列相同的情形，进而继续搜索问题的优化解、跳出局部最优、克服“早熟”现象。受生成最小代价树的普莱姆算法的启发，罗勇等［9］等人提出了基于最小代价树的交叉算子。关丽霞［10］根据带时间窗和同时取送货的车辆路径问题的特点以及启发式交叉方法求解的角度，运用了以基于路程最优的启发式交叉方法为主，单亲遗传作为交叉方法为辅的策略来实现交叉操作。启发式交叉算子的应用会使交叉操作后产生不同于父代的新个体，但同时也会使较优的个体大量繁殖以致于后续参与交叉的父本的基因相似度太高甚至完全一样，而单亲遗传操作利用一个阀值的操作便巧妙地解决了这个问题。汪秋云等［11］在求解带软时间窗车辆路径问题时采用的是多点交叉算子。针对传统交叉算子（如：部分匹配交叉（PMX）、顺序交叉（OX）、循环交叉（CX）等）效率较低、适用性受限等不足之处，Oguz［12］在结合了PMX、OX和OBX等算子思想的基础上提出了交叉算子A。谢秉磊等［13］在用遗传算法解决有时间窗的非满载车辆调度问题时运用了最大保留交叉。Soojung Jung［14］等人在解决带时间窗车辆路径问题时采用了部分匹配交叉算子。带软时间窗的车辆路径问题（VRPSTW）是一类基于次序的组合优化问题，该问题模型的目标函数一般要考虑到路程和时间两方面的因素，因此运用遗传算法解决VRPSTW问题时所运用的交叉算子也要考虑这两个因素。占书芳［4］在应用并行遗传算法解决VRPSTW时采用了合并交叉方法与启发式交叉方法的混合策略来实现交叉操作，该混合策略在其文中表现效果较好。Heung-Suk Hwang［15］在求解带时间约束的车辆路径问题时，对传统的重组交叉做了改进提出了2-边缘重组交叉算子，该交叉算子是利用一个边缘表作为邻接表来巡回对双亲染色体序列基因进行挑选形成子代基因序列的。对于多节点周期性的车辆路径问题，Vidal T［16］等人为实现对整个解空间的广度搜索和对优化解的进一步精炼提出了插入周期交叉算子（PIX），该交叉算子在进化过程各代间能够传递良好的基因序列，对节点、路线、路网的组合联系以及解决周期性路线问题方面都能发挥很好的效果。

三、变异算子

遗传算法中的变异是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成新个体的过程。变异运算是产生新个体的辅助方法，但也是不可或缺的一个环节。它与交叉算子的配合可实现对整个解空间的局部搜索和全局搜索；它与选择算子和交叉算子的配合可避免由选择和交叉运算而造成的某些信息丢失，确保遗传算法的有效性。变异算子在遗传算法中的意义有，可改善遗传算法的局部搜索能力、维持群体的多样性以及防止早熟现象的产生。具体针对于遗传算法在VRP中的应用，研究者们所采用的变异算子也有许多种类。

为保持群体内个体的多样化以及使个体在排列顺序上有较大的变化，郎茂祥［17］采用了连续多次对换的变异技术，变异操作是在变异概率Pm下进行的，只要进行变异操作，就会用随机方式产生交换次数k，然后就对待变异操作的个体染色体序列进行k次对换（基因对换的位置也是随机的）。杨爱梅［7］采用的是互换变异算子，该变异的操作方式是在染色体序列中随机选择两个不同位置上的基因，然后将这两个基因的位置进行相互交换。而钟石泉等［18］虽然也采用了互换变异算子，但其又加入了判断，即采用互换交叉操作后所得到的染色体序列，其适应度与前代染色体的作比较，若有提高则接受，反之就会放弃，如此循环下去，直到交换后产生了相对最好的染色体为止，显然加入该判断后会大大加快遗传算法的收敛速度。关丽霞［10］针对带软时间窗和同时取送货的车辆路径问题（VRPSPDTW）的具体特征，尝试采用了倒位变异（即反转变异）的变异算子，该变异是在染色体序列上随机选取两点，然后将两点间的子串反转过来的过程。汪秋云等［11］在求解软时间窗车辆路径问题时采用的是多点换位法的变异操作，多点换位变异就是在变异概率发生时随机选取两个及以上基因，并任意交换它们的位置的操作过程。沈玲［19］运用混合遗传算法求解带时间窗车辆路径优化问题时采用了k-交换变异。Gen M［20］等人在传统的多点变异的基础上做了改进形成了局部爬山变异，该变异的设计如下：在染色体序列中随机产生n个基因位（非0的基因位），这n个位置的基因任意交换位置会产生中组合，然后计算这种组合对应染色体序列的适应度值，将适应度值最高的染色体留下来作为变异算子产生的结果，如此便使得变异算子具有了局部的爬山能力，该局部爬山变异算子会使种群向着更为有利的方向变异，显然会加快算法的收敛速度。

四、结 语

综上述，受附加条件、约束条件和现实条件的影响，VRP分为很多种类；遗传算法自提出以来经历了40年的发展，目前已相当成熟，遗传算子在不同的环境下存在各种相应的设计策略和方法。不同的策略和方法决定了各遗传算子具有不同的性能和特征。针对这两方面的情况，如何根据每一种具体的VRP，去选择相适应的遗传算子现有方法，亦或是提出一种新的、相适应的遗传算子的新方法，才是能够快而准的寻找到VRP最优解的关键。也是用遗传算法求解VRP能相较目前研究成果革命性前进一步的关键。

［1］ 姜大立，杨西龙，杜文.车辆路径问题的遗传算法研究［J］ .系统工程理论与实践，1999，（6）：43-44.

［2］ 曹二保.物流配送车辆路径问题模型及算法研究［D］ .长沙：湖南大学，2008，92-95.

［3］ 肖天国.带软时间窗的开放式车辆路径问题研究［D］ .长沙：中南大学，2009，35-37.

［4］ 占书芳.并行遗传算法在带软时间窗车辆路径问题中的应用研究［D］ .武汉：武汉理工大学，2006，36-37.

［5］ 范月林，周素萍.基于改进遗传算法的带时间窗VRP问题研究［J］ .电脑知识与技术，2011，7（10）：2412-2413.

［6］ 周艳聪，孙晓晨，余伟翔.基于改进遗传算法的物流配送路径优化研究［J］ .计算机工程与科学，2012，34（10）：119-121.

［7］ 杨爱梅.带软时间窗的车辆路径问题研究［D］ .合肥：合肥工业大学，2009，11-13.

［8］ 钟石泉.物流配送车辆调度智能优化方法研究［D］ .天津：天津大学，2004，21-28.

［9］ 罗勇，陈治亚.基于改进遗传算法的物流配送路径优化［J］ .系统工程，2012，30（8）：119-120.

［10］ 关丽霞.带软时间窗和同时取送货的车辆路径问题研究［D］ .中南大学，2010.

［11］ 汪秋云，蒋文保.带软时间窗车辆路径问题的求解算法研究［J］ .北京信息科技大学学报，2013，28（4）：57-62.

［12］ OGUZ，B Cheung.A Genetic Algorithm for Flow-shop Scheduling Problems with Multiprocessor Tasks［J］ .Proceed-ing of 8th Internation-al Workshop in Project Management and Scheduling，Spain，2002.

［13］ 谢秉磊，李军，郭耀煌.有时间窗的非满载车辆调度问题的遗传算法［J］ .系统工程学报，2000，15（3）：291-294.

［14］ SOOJUNG JUNG.A genetic algorithm for the vehicle routing problemwith time dependent travel times［J］ .ProQuest Information and Learning，2000：66-68.

［15］ HEUNG-SUK HWANG.An improved model for vehicle routing problem with time constraint based on genetic algorithm［J］ .Computers&Ind-ustrial Engineering，2002：362-364.

［16］ VIDAL T，CRAINIC T G，GENDREAU M et al.A hybrid genetic algorithm for multi-depot and periodic vehicle routing problems.Operations Research 2012；60（3）：611–624.

［17］ 郎茂祥，胡思继.用混合遗传算法求解物流配送路径优化问题的研究［J］ .中国管理科学，2002，10（5）：51-54.

［18］ 钟石泉，王雪莲.多车场集送一体化车辆调度问题及其遗传算法研究［J］ .西安电子科技大学学报（社会科学版），2009，19（1）：63-65.

［19］ 沈玲.基于混合遗传算法的带时间窗车辆路径优化问题研究［J］ .物流工程与管理，2009，31（2）：80-81.

［20］ GEN M，CHENG R.Genetic Algorithms and Engineering Design［M］.New York：A Wiley-Interscience Publication，266-271.