1、外文翻译原文GENETICALGORITHMSFORTHEVEHICLEROUTINGPROBLEMWITHTIMEWINDOWSMATERIALSOURCESPECIALISSUEONBIOINFORMATICSANDGENETICALGORITHMSAUTHOROLLIBRYSY1INTRODUCTIONVEHICLEROUTINGPROBLEMSVRPAREALLAROUNDUSINTHESENSETHATMANYCONSUMERPRODUCTSSUCHASSOFTDRINKS,BEER,BREAD,SNACKFOODS,GASOLINEANDPHARMACEUTICALSAREDELI
2、VEREDTORETAILOUTLETSBYAFLEETOFTRUCKSWHOSEOPERATIONFITSTHEVEHICLEROUTINGMODELINPRACTICE,THEVRPHASBEENRECOGNIZEDASONEOFTHEGREATSUCCESSSTORIESOFOPERATIONSRESEARCHANDITHASBEENSTUDIEDWIDELYSINCETHELATEFIFTIESPUBLICSERVICESCANALSOTAKEADVANTAGEOFTHESESYSTEMSINORDERTOIMPROVETHEIRLOGISTICSCHAINGARBAGECOLLECT
3、ION,ORTOWNCLEANING,TAKESANEVERINCREASINGPARTOFTHEBUDGETOFLOCALAUTHORITIESATYPICALVEHICLEROUTINGPROBLEMCANBEDESCRIBEDASTHEPROBLEMOFDESIGNINGLEASTCOSTROUTESFROMONEDEPOTTOASETOFGEOGRAPHICALLYSCATTEREDPOINTSCITIES,STORES,WAREHOUSES,SCHOOLS,CUSTOMERSETCTHEROUTESMUSTBEDESIGNEDINSUCHAWAYTHATEACHPOINTISVISI
4、TEDONLYONCEBYEXACTLYONEVEHICLE,ALLROUTESSTARTANDENDATTHEDEPOT,ANDTHETOTALDEMANDSOFALLPOINTSONONEROUTEMUSTNOTEXCEEDTHECAPACITYOFTHEVEHICLETHEVEHICLEROUTINGPROBLEMWITHTIMEWINDOWSVRPTWISAGENERALIZATIONOFTHEVRPINVOLVINGTHEADDEDCOMPLEXITYTHATEVERYCUSTOMERSHOULDBESERVEDWITHINAGIVENTIMEWINDOWADDITIONALCOMP
5、LEXITIESENCOUNTEREDINTHEVRPTWARELENGTHOFROUTECONSTRAINTARISINGFROMDEPOTTIMEWINDOWSANDCOSTOFWAITINGTIME,WHICHISINCURREDWHENAVEHICLEARRIVESTOOEARLYATACUSTOMERLOCATIONSPECIFICEXAMPLESOFPROBLEMSWITHTIMEWINDOWSINCLUDEBANKDELIVERIES,POSTALDELIVERIES,INDUSTRIALREFUSECOLLECTION,SCHOOLBUSROUTINGANDSITUATIONS
6、WHERETHECUSTOMERMUSTPROVIDEACCESS,VERIFICATION,ORPAYMENTUPONDELIVERYOFTHEPRODUCTORSERVICESOLOMONANDDESROSIERS,1988BESIDESBEINGONEOFTHEMOSTIMPORTANTPROBLEMSOFOPERATIONSRESEARCHINPRACTICALTERMS,THEVEHICLEROUTINGPROBLEMISALSOONEOFTHEMOSTDIFFICULTPROBLEMSTOSOLVEITISQUITECLOSETOONEOFTHEMOSTFAMOUSCOMBINAT
7、ORIALOPTIMIZATIONPROBLEMS,THETRAVELINGSALESPERSONPROBLEMTSP,WHEREONLYONEPERSONHASTOVISITALLTHECUSTOMERSTHETSPISANNPHARDPROBLEMITISBELIEVEDTHATONEMAYNEVERFINDACOMPUTATIONALTECHNIQUETHATWILLGUARANTEEOPTIMALSOLUTIONSTOLARGERINSTANCESFORSUCHPROBLEMSTHEVEHICLEROUTINGPROBLEMISEVENMORECOMPLICATEDEVENFORSMA
8、LLFLEETSIZESANDAMODERATENUMBEROFTRANSPORTATIONREQUESTS,THEPLANNINGTASKISHIGHLYCOMPLEXHENCE,ITISNOTSURPRISINGTHATHUMANPLANNERSSOONGETOVERWHELMED,ANDMUSTTURNTOSIMPLE,LOCALRULESFORVEHICLEROUTINGNEXTWEWILLDESCRIBEBASICPRINCIPLESOFGENETICALGORITHMSANDSOMEAPPLICATIONSFORVEHICLEROUTINGPROBLEMWITHTIMEWINDOW
9、S2GENERALPRINCIPLESOFGENETICALGORITHMSTHEGENETICALGORITHMGAISANADAPTIVEHEURISTICSEARCHMETHODBASEDONPOPULATIONGENETICSTHEBASICCONCEPTSAREDEVELOPEDBYHOLLAND,1975,WHILETHEPRACTICALITYOFUSINGTHEGATOSOLVECOMPLEXPROBLEMSISDEMONSTRATEDINDEJONG,1975ANDGOLDBERG,1989REFERENCESANDDETAILSABOUTGENETICALGORITHMSC
10、ANALSOBEFOUNDFOREXAMPLEINALANDER,2000ANDMHLENBEIN,1997RESPECTIVELYTHECREATIONOFANEWGENERATIONOFINDIVIDUALSINVOLVESPRIMARILYFOURMAJORSTEPSORPHASESREPRESENTATION,SELECTION,RECOMBINATIONANDMUTATIONTHEREPRESENTATIONOFTHESOLUTIONSPACECONSISTSOFENCODINGSIGNIFICANTFEATURESOFASOLUTIONASACHROMOSOME,DEFININGA
11、NINDIVIDUALMEMBEROFAPOPULATIONTYPICALLYPICTUREDBYABITSTRING,ACHROMOSOMEISMADEUPOFASEQUENCEOFGENES,WHICHCAPTURETHEBASICCHARACTERISTICSOFASOLUTIONTHERECOMBINATIONORREPRODUCTIONPROCESSMAKESUSEOFGENESOFSELECTEDPARENTSTOPRODUCEOFFSPRINGTHATWILLFORMTHENEXTGENERATIONITCOMBINESCHARACTERISTICSOFCHROMOSOMESTO
12、POTENTIALLYCREATEOFFSPRINGWITHBETTERFITNESSASFORMUTATION,ITCONSISTSOFRANDOMLYMODIFYINGGENESOFASINGLEINDIVIDUALATATIMETOFURTHEREXPLORETHESOLUTIONSPACEANDENSURE,ORPRESERVE,GENETICDIVERSITYTHEOCCURRENCEOFMUTATIONISGENERALLYASSOCIATEDWITHLOWPROBABILITYANEWGENERATIONISCREATEDBYREPEATINGTHESELECTION,REPRO
13、DUCTIONANDMUTATIONPROCESSESUNTILALLCHROMOSOMESINTHENEWPOPULATIONREPLACETHOSEFROMTHEOLDONEAPROPERBALANCEBETWEENGENETICQUALITYANDDIVERSITYISTHEREFOREREQUIREDWITHINTHEPOPULATIONINORDERTOSUPPORTEFFICIENTSEARCHALTHOUGHTHEORETICALRESULTSTHATCHARACTERIZETHEBEHAVIOROFTHEGAHAVEBEENOBTAINEDFORBITSTRINGCHROMOS
14、OMES,NOTALLPROBLEMSLENDTHEMSELVESEASILYTOTHISREPRESENTATIONTHISISTHECASE,INPARTICULAR,FORSEQUENCINGPROBLEMS,LIKEVEHICLEROUTINGPROBLEM,WHEREANINTEGERREPRESENTATIONISMOREOFTENAPPROPRIATEWEAREAWAREOFONLYONEAPPROACHBYTHANGIAH,1995THATUSESBITSTRINGREPRESENTATIONINVEHICLEROUTINGCONTEXTINALLOTHERAPPROACHES
15、FORVEHICLEROUTINGPROBLEMWITHTIMEWINDOWSTHEENCODINGISSUEISDISREGARDED3APPLICATIONSFORVEHICLEROUTINGPROBLEMWITHTIMEWINDOWSTHANGIAH,1995DESCRIBESAMETHODCALLEDGIDEONTHATASSIGNSCUSTOMERSTOVEHICLESBYPARTITIONINGTHECUSTOMERSINTOSECTORSBYGENETICALGORITHMANDCUSTOMERSWITHINEACHFORMEDSECTORAREROUTEDUSINGTHECHE
16、APESTINSERTIONMETHODOFGOLDENANDSTEWART,1985INTHENEXTSTEPTHEROUTESAREIMPROVEDUSINGEXCHANGESINTRODUCEDBYOSMAN,1993THETWOPROCESSESARERUNITERATIVELYAFINITENUMBEROFTIMESTOIMPROVETHESOLUTIONQUALITYTHESEARCHBEGINSBYCLUSTERINGCUSTOMERSEITHERACCORDINGTOTHEIRPOLARCOORDINATEANGLEORRANDOMLYTHEPROPOSEDSEARCHSTRA
17、TEGYACCEPTSALSOINFEASIBILITIESDURINGTHESEARCHAGAINSTCERTAINPENALTYFACTORSINTHEGIDEONSYSTEMEACHCHROMOSOMEREPRESENTSASETOFPOSSIBLECLUSTERINGSCHEMESANDTHEFITNESSVALUESAREBASEDONCORRESPONDINGROUTINGCOSTSTHECROSSOVEROPERATOREXCHANGESARANDOMLYSELECTEDPORTIONOFTHEBITSTRINGBETWEENTHECHROMOSOMESANDMUTATIONIS
18、USEDWITHAVERYLOWPROBABILITYTORANDOMLYCHANGETHEBITVALUESPOTVINANDBENGIO,1996PROPOSEAGENETICALGORITHMGENEROUSTHATDIRECTLYAPPLIESGENETICOPERATORSTOSOLUTIONS,THUSAVOIDINGTHECODINGISSUESTHEINITIALPOPULATIONISCREATEDWITHCHEAPESTINSERTIONHEURISTICOFSOLOMON,1987ANDTHEFITNESSVALUESOFTHEPROPOSEDAPPROACHAREBAS
19、EDONTHENUMBEROFVEHICLESANDTOTALROUTETIMETHESELECTIONPROCESSISSTOCHASTICANDBIASEDTOWARDTHEBESTSOLUTIONSFORTHISPURPOSEALINEARRANKINGSCHEMEISUSEDDURINGTHERECOMBINATIONPHASE,TWOPARENTSOLUTIONSAREMERGEDINTOASINGLEONE,SOASTOGUARANTEETHEFEASIBILITYOFTHENEWSOLUTIONTWOTYPESOFCROSSOVEROPERATORSAREUSEDTOMODIFY
20、ARANDOMLYSELECTEDROUTEORTOINSERTAROUTEINTOTHEOTHERPARENTSOLUTIONASPECIALREPAIROPERATORISTHENAPPLIEDTOTHEOFFSPRINGTOGENERATEANEWFEASIBLESOLUTIONMUTATIONOPERATORSAREAIMEDATREDUCINGTHENUMBEROFROUTESFINALLY,INORDERTOLOCALLYOPTIMIZETHESOLUTION,MUTATIONOPERATORBASEDONOROPTEXCHANGESOR,1976ISINCLUDEDBERGERE
21、TAL,1998PROPOSEAMETHODBASEDONTHEHYBRIDIZATIONOFAGENETICALGORITHMWITHWELLKNOWNCONSTRUCTIONHEURISTICSTHEAUTHORSOMITTHECODINGISSUESANDREPRESENTASOLUTIONBYASETOFFEASIBLEROUTESTHEINITIALPOPULATIONISCREATEDWITHNEARESTNEIGHBORHEURISTICINSPIREDFROMSOLOMON,1987THEFITNESSVALUESOFTHEINDIVIDUALSAREBASEDONTHENUM
22、BEROFROUTESANDTOTALDISTANCEOFTHECORRESPONDINGSOLUTIONANDFORSELECTIONPURPOSESTHEAUTHORSUSETHESOCALLEDROULETTEWHEELSCHEMEINTHISSCHEMETHEPROBABILITYOFSELECTINGANINDIVIDUALISPROPORTIONALTOITSFITNESSFORDETAILSSEEGOLDBERG,1989THEPROPOSEDCROSSOVEROPERATORCOMBINESITERATIVELYVARIOUSROUTESR1OFPARENTSOLUTIONP1
23、WITHASUBSETOFCUSTOMERS,FORMEDBYR2NEARESTNEIGHBORROUTESFROMPARENTSOLUTIONP2AREMOVALPROCEDUREISFIRSTCARRIEDOUTTOREMOVESOMEKEYCUSTOMERNODESFROMR1THENANINSERTIONHEURISTICINSPIREDFROMSOLOMON,1987COUPLEDTOARANDOMCUSTOMERACCEPTANCEPROCEDUREISLOCALLYAPPLIEDTOBUILDAFEASIBLEROUTE,CONSIDERINGTHEPARTIALROUTER1A
24、SANINITIALSOLUTIONTHEMUTATIONOPERATORSAREAIMEDATREDUCINGTHENUMBEROFROUTESOFSOLUTIONSHAVINGONLYAFEWCUSTOMERSANDLOCALLYREORDERINGTHEROUTESBRYSY,1999AANDBRYSY,1999BEXTENDEDTHEWORKOFBERGERETAL,1998BYPROPOSINGSEVERALNEWCROSSOVERANDMUTATIONOPERATORS,TESTINGDIFFERENTFORMSOFGENETICALGORITHMS,SELECTIONSCHEME
25、S,SCALINGSCHEMESANDTHESIGNIFICANCEOFTHEINITIALSOLUTIONSWHENITCOMESTORECOMBINATION,ANAPPROACHWHERECUSTOMERSWITHINRANDOMLYGENERATEDSEGMENTSINPARENTSOLUTIONP1AREREPLACEDWITHSOMEOTHERCUSTOMERSONTHENEARROUTESOFPARENTSOLUTIONP2ISFOUNDTOPERFORMBESTTHEBESTPERFORMINGMUTATIONOPERATORSELECTSRANDOMLYONEOFTHESHO
26、RTESTROUTESANDTRIESTOELIMINATEITBYINSERTINGTHECUSTOMERSINTOOTHERLONGERROUTESREGARDINGDIFFERENTFORMSOFGENETICALGORITHMSITISCONCLUDEDTHATITISIMPORTANTTOCREATEMANYNEWOFFSPRINGEACHGENERATIONANDITISENOUGHTOMAINTAINONLYONEPOPULATIONFORSELECTIONPURPOSESSOCALLEDTOURNAMENTSELECTIONISFOUNDTOPERFORMBESTINTHEFI
27、RSTPHASETWOINDIVIDUALSARESELECTEDWITHARANDOMPROCEDURETHATISBIASEDTOWARDSBETTERFITNESSSCORESINTHESECONDPHASE,THEINDIVIDUALWITHBETTERFITNESSISSELECTEDHOWEVERTHEDIFFERENCESBETWEENDIFFERENTSCHEMESWEREMINORANEWSCALINGSCHEMEBASEDONAWEIGHTEDCOMBINATIONOFNUMBEROFROUTES,TOTALDISTANCEANDWAITINGTIMEISFOUNDTOPE
28、RFORMPARTICULARLYWELLFINALLYTOCREATETHEINITIALPOPULATION,SEVERALSTRATEGIES,SUCHUSHEURISTICSOFSOLOMON,1987ANDRANDOMLYCREATEDROUTESWERETRIEDANDITWASCONCLUDEDTHATTHEBESTSTRATEGYISTOCREATEADIVERSEINITIALPOPULATIONTHATALSOCONTAINSSOMEINDIVIDUALSWITHBETTERFITNESSSCORESHOMBERGERANDGEHRING,1999PROPOSETWOEVO
29、LUTIONARYMETAHEURISTICSFORVRPTWTHEPROPOSEDALGORITHMSAREBASEDONTHECLASSOFEVOLUTIONARYALGORITHMSCALLEDEVOLUTIONSTRATEGIESDIFFERENCESTOGAEXISTWITHREGARDTOTHESUPERIORROLEOFMUTATIONCOMPAREDTOTHERECOMBINATIONOPERATORSHERETHEINDIVIDUALREPRESENTATIONALSOINCLUDESAVECTOROFSOCALLEDSTRATEGYPARAMETERSINADDITIONT
30、OTHESOLUTIONVECTORANDBOTHCOMPONENTSAREEVOLVEDBYMEANSOFRECOMBINATIONANDMUTATIONOPERATORSINTHEPROPOSEDAPPLICATIONFORVRPTWTHESESTRATEGYPARAMETERSREFERTOHOWOFTENARANDOMLYSELECTEDLOCALSEARCHOPERATORISAPPLIEDANDTOBINARYPARAMETERUSEDTOALTERNATETHESEARCHBETWEENMINIMIZINGTHENUMBEROFVEHICLESANDTOTALDISTANCESE
31、LECTIONOFTHEPARENTSISDONERANDOMLYANDONLYONEOFFSPRINGISCREATEDTHROUGHTHERECOMBINATIONOFPARENTSTHISWAYANUMBEROFFSPRINGISCREATED,WHEREISTHEPOPULATIONSIZEATTHEENDFITNESSVALUESAREUSEDTOSELECTOFFSPRINGTOTHENEXTPOPULATIONBECAUSETHEPARENTSARENOTINVOLVEDINTHESELECTIONPROCESS,DETERIORATIONSDURINGTHESEARCHAREP
32、ERMITTEDTHEFIRSTOUTOFTHETWOPROPOSEDMETAHEURISTICS,EVOLUTIONSTRATEGYES1,SKIPSTHERECOMBINATIONPHASETHESECONDEVOLUTIONSTRATEGYES2USESUNIFORMORDERBASEDCROSSOVERTOMODIFYTHEINITIALLYRANDOMLYCREATEDMUTATIONCODESOFTHETWOPARENTSANDTRIESTOIMPROVETHESOLUTIONVECTOROFATHIRDRANDOMLYSELECTEDPARENTUSINGTHEMODIFIEDC
33、ODETHEMUTATIONCODEISUSEDTOCONTROLASETOFREMOVALANDINSERTIONOPERATORSPERFORMEDBYOROPTOPERATOROR,1976THEFITNESSVALUESAREBASEDONNUMBEROFROUTES,TOTALTRAVELDISTANCEANDONACRITERIONTHATDETERMINESHOWEASILYTHESHORTESTROUTEOFTHESOLUTIONINTERMSOFTHENUMBEROFCUSTOMERSONTHEROUTECANBEELIMINATEDTHEINDIVIDUALSOFASTAR
34、TINGPOPULATIONAREGENERATEDBYMEANSOFASTOCHASTICAPPROACH,WHICHISBASEDONTHESAVINGSALGORITHMOFCLARKEANDWRIGHT,1964BRYSYETAL,2000DESCRIBEATWOPHASEHYBRIDEVOLUTIONARYALGORITHMBASEDONTHEHYBRIDIZATIONOFAGENETICALGORITHMANDANEVOLUTIONARYALGORITHMCONSISTINGOFSEVERALLOCALSEARCHANDROUTECONSTRUCTIONHEURISTICSINSP
35、IREDFROMTHESTUDIESOFSOLOMON,1987ANDTAILLARDETAL,1997INTHEFIRSTPHASEAGENETICALGORITHMBASEDONTHESTUDIESBERGERETAL,1998ANDBRYSY,1999AISUSEDTOOBTAINAFEASIBLESOLUTIONTHEEVOLUTIONARYALGORITHMUSEDINTHESECONDPHASEPICKSEVERYPAIROFROUTESINRANDOMORDERANDAPPLIESRANDOMLYONEOUTOFTHEFOURLOCALSEARCHOPERATORSORROUTE
36、CONSTRUCTIONHEURISTICSFINALLY,OFFSPRINGROUTESGENERATEDBYTHESECROSSOVEROPERATORSAREMUTATEDACCORDINGTOAUSERDEFINEDPROBABILITYBYSELECTINGRANDOMLYONEOUTOFTWOOPERATORSSELECTINGEACHPOSSIBLEPAIROFROUTES,MATINGANDMUTATIONOPERATORSAREREPEATEDLYAPPLIEDFORACERTAINNUMBEROFGENERATIONSANDFINALLYAFEASIBLESOLUTIONI
37、SRETURNEDTOESCAPEFROMLOCALMINIMUM,ARCSLONGERTHANAVERAGEAREPENALIZED,IFTHEYAPPEARFREQUENTLYDURINGTHESEARCH译文时间窗约束下的车辆路径问题遗传算法资料来源生物信息和遗传算法特刊作者奥利布瑞赛1简介车辆路径问题（VRP）对我们身边许多消费品都很有意义，例如软性饮料，啤酒，面包，小吃，汽油和药品通过一个车队走合适的运输路线，运送至零售网点。在实践中，VRP被认为是一个非常成功的运行研究故事，自五十年代后期以来，它已被的广泛研究。公共服务也利用这些系统的优点，来提高物流链。垃圾收集，城镇的清洁，也需
38、要地方当局需要增加预算的部分。一个典型的车辆运输路径问题可以被描述为，设计一个最少成本的路线，即从一个仓库，到一系列地理上分散的点（城市，商店，仓库，学校，客户等）。这些路线的设计必须遵循每一个点被一辆运输车访问一次，所有路线起点和终点在一个仓库，所有点的总需求量，不得超过车辆的运输能力。在时间窗约束下的路径问题（VRPTW）是VRP的概括，规定应在一个客户给定的时间窗内送达，增加了复杂性。在VRPTW中遇到的额外复杂过程是，从一个仓库时间窗的路线长度限制提高，以及等待时间的成本，这是发生在车辆到达客户点太早所造成的。时间窗的具体问题结合实例，包括银行交付，邮递，工业垃圾收集，校巴路线和路况，
39、这些客户必须在运输物品或提供服务后，提供通道，证明，或者付款所罗门和戴斯洛赛斯，1988。在实际操作中，除了是一个最重要的操作研究问题外，车辆路径问题也是最难解决的问题之一。它非常接近于最著名的组合优化问题旅行商问题，即一个商人必须访问所有客户，则拜访路线要怎么选择。旅行商问题是一个非常难的问题。它被认为是一个永远找不到计算结束去保证这是最佳解决方案的问题，而这些运输路径问题则更为复杂。即使是小型车型和中型数量的运输要求，需规划的任务也是非常复杂。因此，若策划者很快就会不堪重负，也是并不奇怪的，必须将其转化为简单的，适应本地规则的运输路径。下一步，我们将介绍遗传算法的基本原理和一些时间窗约束下
40、的车辆路径问题。2遗传算法的一般原则遗传算法（GA）是一种在人口遗传基础上，适应启发式的探访方法。基本概念是发展于荷兰，1975，而实际上将遗传算法用于解决复杂的问题，被证明是在德容，1975和哥德堡，1989中。文献和遗传算法的细节也在阿兰德，2000和穆棱贝，1997中找到。新的一代独立创作，主要涉及四个步骤或阶段代表，选择，重组和突变。解决方案的代表由显著特点的染色体编码组成，确定为一个独立的个体。通常染色体有一系列的基因组成，这就抓住了一个解决方案的最基本特征。重组或者再生产过程可以使父母选择使用的基因，并形成下一代。它结合染色体特征，能使创造出的后代更具有适应性。至于突变，它由一个独
41、立的随机更改的基因组成，能进一步探索解决方案和确保，或保存遗传多样性。这个突变的发生通常概率很低。新一代的创建，通过复制选择，再生产和突变过程，直到所有新的染色体在人类中产生，取代旧的。在遗传质量和多样性之间的适当的平衡，是需要在人群中，用来支持高效的搜索。虽然理论结果表明，遗传算法的独特已经获得染色特的位串，但并不能简单地代表所有问题。这样的话，特别是，对于时常发生的问题，如车辆路径问题，一个整数就代表更正确。我们知道只有一个方式衫葛，1995，在车辆路径文件中运用位串代表。在其他时间窗约束下的路径问题中，可以忽视编码问题。3时间窗约束下的路径问题的应用衫葛，1995描述了一个叫做基甸分配的
42、方法，即运送指定客户，通过遗传算法将客户分割成几个部分，客户之间路线的形成要用最低级的插入方式戈登和斯图沃特，1985。在下一步中，路线用转变得到改善奥斯曼，1993。这两个进程是有限次数的迭代运行，能提高解决方案的质量。探索从聚类的客户开始，根据他们的极坐标角度或随机都可以。这个探索策略建议的接受，对于探索中的反抗特定惩罚因素是不可行的。在基甸系统中，根据相应的路径成本，每一个染色体代表了一系列聚类计划以及适应价值的可能。交叉操作与随机选择部分在染色体和变异之间交换，被用于随机的价值的概率是非常低的。波文和班戈，1996提出了一种遗传算法，即直接使用遗传操作去解决问题，从而避免了编码问题。最
43、初的人口计算是最低级的插入启发式创建的所罗门，1987，适应价值的接受方法是基于路线总共的车辆数和总的所用时间。选择过程是随机的并偏向最好的解决方案。为此，使用线性排名计划。在重组阶段，两个起始方法，合并为一个，因此能保证新方案的可行性。两种交叉运行用来修饰随机选择路径，或在其他起始方案中插入一种路径。一个特约维修商，是将其运用到产生下一代的新的可行方案。变异算子的目的在于减少路径的数量。最终，为了局部优化的解决方案，变异算子基于OROPT奥尔，1976。贝格等，1998提出基于良好构架的启发式的杂交遗传算法。作者省却了编码问题，并代表一系列可行路径的解决方案。带有近邻的初始种群的创建灵感来自
44、于所罗门，1987。个人的适应价值基于路径数量，相应的总距离和选择目的，因此作者称其为赌轮计划。在这项计划中，选择一个个体的概率是与它的适当价值成正比；详情参见哥德堡，1989。建议的解决方案是，交叉算子与迭代不同路径R1想结合，母体方案P1连带客户子系统，形成从母体方案P2中的近邻路径R2。一个删除过程是首先从R1中消除一些关键客户节点。然后插入一个启发式灵感所罗门，1987连接一个随机的客户接受程序，是建立一个可行路径，考虑部分路径R1作为一个初始解决方案。该变异算子的目的是减少那些只有一点客户并且局部的重新安排路线的解决方案。布瑞赛，1999A和布瑞赛，1999B将工作伯格等，1998通
45、过提出一些新的交叉和变异算子，测试不同形式的遗传算法，选择计划，缩放计划和重要的初始方案。当涉及到重组，用起始方案P1中的随机遗传环节的客户取代另外一些在起始方案P2上的靠近路线的客户效果是最好的。最佳的变异算子随机选择是最短路径，并尝试通过插入客户到其他较长路径中，以消除它。对于不同形式的遗传算法，它被断定对创造许多新后代非常重要，它也足以维持一族人群。选择的目的，即所谓锦标赛选择是最好的形式。在第一阶段，两个个体的随机选择，偏向更好的健康分数。在第二阶段，更适合的个体被选择。然而，不同计划之间的差异是次要的。一个新的拉伸计划，是基于路线数目，总距离和等待时间结合的一个加重量，总被发现进行的
46、特别好。最后为了创建初始人群，一些策略，例如启发式所罗门，1987和尝试随机创建路线，它被认定是创建多样化初始人群的最好策略，并且包含了更好的健康分数。厚堡葛和格瑞，1999提出两个VRPTW的进化启发式。这个算法的提出是基于进化算法的一种叫做进化策略。与重组运营相比，不同于遗传算法在异性方面存在突变的优越地位。在这里，个人代表还包括一种向量叫做策略参数，将其加入到方案向量，这两个组成部分往往都是公司重组和突变的手段。在为VRPTW这些策略参数所提出的应用中，提供随机选择局部研究的频率和二进制参数用于替代最少车辆和最短距离的研究。随机的母体选择，只有一个后代是通过母体重组得到的。后代的创造是这
47、样一个数据，其中表示人口规模。最终的健康价值被用于选择中后代至下一代人口。由于母体不涉及选择过程，退化是被允许的。首先得出的是两个启发式建议，进化策略ES1，跳过重组阶段。第二个进化策略ES2用于统一以秩序为基础的交叉算子，修改初始创建的随机突变代码，这些代码是两个母体和试图提高解决第三次随机向量，并用随机选择母本修改代码。突变代码是用来控制一系列的清楚和插入操作，这些是通过OROPT奥尔，1976实现的。健康价值是基于路径数量，总距离和用什么标准来决定如何容易地选择最短路径，客户数量在路径方案上可以被除去。人群中开始产生个体是通过随机方式形成的，这是基于储存算法克拉克和赖特，1964。布瑞赛等，2000描述了一个两阶段混合进化算法，这是基于杂交遗传算法和进化遗传。其中进化遗传包括一些局部研究和路线结构的启发式灵感所罗门，1987和泰拉德等，1997。在第一阶段，基于伯格等，1998的遗传算法和布瑞赛，1999A用于获得一个可行的解决方案。第二阶段的进化算法在随机顺序中选取每对路线，适用于随机的四个局部搜索营运商或启发式路径结构。最后，这些后代路径所产生的交叉算子突变，是根据通过一两个营运商的用户定义概率来判定。选择每一个可能配对的路线，交配和突变的运营商一再申请了确定的后代数量和最终返回的可行方案。为了逃避局部最小，如果在搜索中平凡出现，弧线则长于平均处罚。
