时间窗约束下的车辆路径问题遗传算法外文翻译

时间窗约下的车辆路问题遗传算法文翻译外文翻译原文GeneticAlgorithmsfortheRoutingProblemwithTimeWindowsMaterialSource:SpecialissueonBioinformaticsandGeneticAlgorithmsAuthor:OlliBr?ysy1IntroductionVehicleRoutingProblemsVRPareallaroundusinthesensethatmanyconsumerproductssuchassoftdrinks,beer,bread,snackfoods,gasolineandpharmaceuticalsaredeliveredtoretailoutletsbyafleetoftruckswhoseoperationfitsthevehicleroutingmodel.Inpractice,theVRPhasbeenrecognizedasoneofthegreatsuccessstoriesofoperationsitwidelysincethefifties.Publicservicescanalsotakeadvantageofthesesystemsinordertoimprovetheirlogisticschain.Garbagecollection,ortowncleaning,takesaneverincreasingpartofthebudgetoflocalauthoritiesAtypicalvehicleroutingproblemcanbedescribedastheproblemofdesigningleastcostroutesfromonedepottoasetofgeographicallyscatteredstores,schools,etc.Theroutesbedesignedisvisited

byexactlyonevehicle,allroutesstartandendatthedepot,andthetotaldemandsofallpointsononeroutemustnotexceedthecapacityofthevehicleTheVehicleRoutingProblemwithTimeWindowsVRPTWisageneralizationoftheVRPinvolvingtheaddedcomplexitythateverycustomershouldbeservedwithinagiventimewindow.AdditionalcomplexitiesencounteredintheVRPTWarelengthofrouteconstraintarisingfromtimeofiswhenaataofproblemswithtimeincludedeliveries,deliveries,industrialschool-busroutingandsituationswherecustomermustprovideaccess,verification,orpaymentupondeliveryoftheproductorservice[SolomonandDesrosiers,1988].Besidesbeingoneofthemostimportantproblemsofoperationsresearchinpracticalterms,thevehicleroutingproblemisalsooneoftheofthefamouscombinatorialoptimizationproblems,theTravelingSalespersonProblemTSP,whereonlyonepersontovisitthecustomers.TheTSPisanNP-hardproblem.Itisbelievedthatonemayneverfindacomputationaltechniquethatwillguaranteeoptimalsolutionstolargerinstancesforsuchproblems.Thevehicleroutingproblemisevenmorecomplicated.Evenforsmallfleetsizesandamoderatenumberoftransportationrequests,theplanningtaskishighlycomplex.Hence,it

ishumanplannerssoongetoverwhelmed,mustturntosimple,localrulesforvehiclerouting.Nextwewilldescribebasicprinciplesofgeneticalgorithmsandsomeapplicationsforvehicleroutingproblemwithtimewindows.2GeneralprinciplesofgeneticalgorithmsTheGeneticAlgorithmGAisanadaptiveheuristicsearchmethodbasedonaredeveloped1975],whilethepracticalityofusingtheGAtosolvecomplexproblemsisdemonstratedin[DeJong,1975]and[Goldberg,1989].Referencesanddetailsalgorithmscanfoundforin[Alander,2000]and[Mühlenbein,1997]respectively.Thecreationofanewgenerationofindividualsinvolvesfourstepsorrepresentation,selection,recombinationandmutation.Therepresentationofthesolutionspaceconsistsofencodingsignificantfeaturesofaachromosome,defininganindividualofapopulation.Typicallypicturedbyabitstring,achromosomeismadeupofasequenceofgenes,whichcapturethebasiccharacteristicsofasolution.TherecombinationorreproductionprocessmakesuseofgenesofselectedformnextItcombinescharacteristicsofchromosomestopotentiallycreateoffspringwithbetterfitness.Asformutation,itconsistsofrandomly

modifyinggenesofasingleindividualatatimetofurtherexplorethesolutionspaceandorpreserve,geneticdiversity.Theofisiscreatedbyrepeatingtheselection,reproductionandmutationprocessesallinfromtheoldone.Aproperbalancebetweengeneticqualityanddiversityisthereforerequiredwithinthepopulationinordertosupportefficientsearch.AlthoughthattheoftheGAhavebeenobtainedforbit-stringchromosomes,notallproblemslendthemselvestothisinforsequencingproblems,likevehicleroutingproblem,whereanintegerrepresentationismoreoftenappropriate.Weareawareofonlyoneapproachby[Thangiah,1995]thatusesbitstringrepresentationinvehicleroutingcontext.Inallotherapproachesforvehicleroutingproblemwithtimewindowstheencodingissueisdisregarded.3Applicationsforvehicleroutingproblemwithtimewindows[Thangiah,1995]describesamethodcalledGIDEONthatassignscustomerstovehiclesbypartitioningthecustomersintosectorsbygeneticthecheapestinsertionof[GoldenStewart,1985].Inthenextsteptheroutesareimprovedusing-exchangesintroducedby[Osman,

1993].Thetworuniterativelyafinitenumberofoimprovethesolutionquality.Thesearchbeginsbyclusteringcustomerseithertosearchstrategyacceptsalsoinfeasibilitiesduringthesearchagainstcertainpenaltyfactors.IntheGIDEONsystemchromosomerepresentsasetofschemesandthefitnessarebasedoncorrespondingoperatoraselectedportionofthebitstringbetweenthechromosomesandmutationisusedwithaverylowprobabilitytorandomlychangethebitvalues.[PotvinandBengio,1996]proposeageneticalgorithmGENEROUSthatdirectlyappliesgeneticoperatorstosolutions,thusavoidingthecodingissues.Theinitialpopulationcreatedwithcheapestinsertionheuristicof[Solomon,1987]andthefitnessvaluesoftheproposedapproacharebasedonthenumberofvehiclesandtotalroutetime.TheselectionandForthispurposealinearrankingschemeisused.Duringtherecombinationphase,twoparentsolutionsaremergedintoasingleone,soastoguaranteethefeasibilityofthenewsolution.Twotypesofcrossoveroperatorstomodifyarandomlyroutearouteintosolution.repairappliedtotoanewareaimedatnumberroutes.Finally,ordertolocally

optimizethesolution,mutationoperatorbasedonOr-optexchanges[Or,1976]isincluded.[Bergeretal.,ofageneticalgorithmwithwell-knownconstructionheuristics.Theauthorsomitthecodingissuesandrepresentasolutionbyasetoffeasibleroutes.Theinitialiscreatedwithnearestneighborheuristicinspiredfrom[Solomon,1987].Thefitnessvaluesoftheindividualsarebasedonthenumberofroutesandtotaldistanceofthecorrespondingusesocalledroulette-wheelscheme.Inthisschemetheselectingan1989].Theproposedcrossoveroperatorcombinesiterativelyvariousroutesr1ofparentsolutionP1withasubsetofcustomers,formedbyr2nearest-neighborroutesfromparentsolutionP2.Aremovalprocedureisfirstcarriedouttoremovesomekeycustomernodesfromr1.Thenaninsertionheuristicinspiredfrom[Solomon,1987]coupledtoarandomcustomerconsideringthepartialrouter1asaninitialsolution.Themutationoperatorsareatreducingtheroutesofsolutionsonlyafewcustomersandlocallyreorderingtheroutes.[Br?ysy,1999a]and[Br?ysy,1999b]extendedtheworkof[Bergeretal.,

testingofgeneticalgorithms,selectionschemes,schemesandthesignificanceoftheinitialsolutions.Whenitcomestorecombination,anapproachwherecustomerswithinrandomlygeneratedsegmentsinparentarewithsomeotherthenearroutesofparentsolutionP2isfoundtoperformbest.Thebest-performingmutationoperatorselectsrandomlyoneoftheshortestroutesandtriestoeliminateitbyinsertingthecustomersintootherlongerroutes.Regardingdifferentformsofgeneticalgorithmsitisconcludedthatitisimportanttocreatemanynewoffspringeachgenerationitistoonepopulation.selectionpurposesInfirstphaseindividualsarewitharandomisbiasedwithbetterfitnessisselected.Howeverthedifferencesbetweendifferentschemeswereminor.Anewscalingschemebasedonaweightedcombinationofnumberandwaitingtimeisfoundtoperformparticularlywell.Finallytocreatetheinitialpopulation,severalstrategies,suchusheuristicsof[Solomon,1987]andrandomlycreatedrouteswereitwasconcludedthebeststrategytoaalsowithbetterfitnessscores.[HombergerandGehring,1999]proposetwoevolutionary

metaheuristicsontheclassofevolutionaryalgorithmscalledEvolutionStrategies.DifferencestoGAexistwithregardtothesuperiorroleofmutationcomparedtotherecombinationoperators.Heretheindividualrepresentationalsoincludesavectorofsocalledstrategyparametersinadditiontothesolutionbothbyofandmutationoperators.IntheproposedapplicationforVRPTWthesestrategyparametersrefertohowoftenarandomlyselectedlocalsearchoperatorisappliedbinaryusedtothesearchbetweenminimizingthenumberofvehiclesandtotaldistance.Selectionoftheparentsisdonerandomlyandonlyoneoffspringiscreatedthroughtherecombinationparents.waynumberλ?μoffspringiscreated,μisthepopulationsize.Atthefitnessvaluesareusedtoselectμoffspringtothenextpopulation.Becausetheparentsarenotinvolvedintheselectionprocess,deteriorationsduringthesearcharepermitted.Thefirstoutofthetwoproposedmetaheuristics,evolutionstrategyES1,skipstherecombinationphase.ThesecondevolutionstrategyES2usesuniformorder-basedcrossovertomodifytheinitiallyrandomlycreatedmutationcodesofthetwoparentsandtriestoimprovethesolutionvectorofathirdrandomlyselectedparentusingthemodifiedcode.Themutationcodeisusedtocontrolasetofoperator

1976].Thefitnessvaluesarebasedonnumberofroutes,totaltraveldistanceonathatrouteofthesolutionintermsofthenumberofcustomersontheroutecanbeeliminated.Theindividualsofastartingpopulationaregeneratedbymeansofastochasticapproach,whichisbasedonthesavingsalgorithmof[ClarkeandWright,1964].[Br?ysyetal.,2000]describeatwo-phasehybridevolutionaryalgorithmbasedonthehybridizationofageneticalgorithmandanevolutionaryalgorithmconsistingofseverallocalsearchandrouteconstructionheuristicsinspiredfromthestudiesof[Solomon,1987]and[Taillardetal.,thefirstageneticalgorithmonthestudies[Bergeretal.,1998]and[Br?ysy,1999a]isusedtoobtainapickseverypairofroutesinrandomorderandappliesrandomlyoneoutofthefourlocalsearchoperatorsorrouteconstructionheuristics.Finally,offspringroutesgeneratedbythesecrossoveroperatorsaremutatedaccordingtoaprobabilityselectingrandomlyoneoutoftwooperators.Selectingeachpossibleofroutes,matingandmutationoperatorsarerepeatedlyappliedforacertainnumberofgenerationsandfinallyafeasiblesolutionisreturned.Toescapefromlocalminimum,arcslongerthanaveragearepenalized,iftheyappearfrequentlyduringthesearch.

译文时间窗约束下的车辆路径问题遗传算法资料来源:生物信息和遗传算法特刊1简介

作者:奥利布瑞赛车辆路径问(VRP)我们身边许多消费品都很有意义,例如软性饮,啤酒,面包,小吃,汽油和药品通过一个车队走合适的运输路线运送至零售网点。在实践中,VRP被认为是一个非常成功的运行研究故,自五十年代后期以来它已被的广泛研究。公共服务也利用这些系统的优点来高物流链。垃圾收集,城镇的清洁,也需要地方当局需要增加预算的部分。一个典型的车辆运输路径问题可以被描述,设计一个最少成本的路线,即从一个仓库到一系列地理上分散的点(城市,商店,仓库,校,客户等)。这些路线的设计必须遵循每一个点被一辆运输车访问一,所有路线起点和终点在一个仓库,所有点的总需求量,不得超过车辆的运输能力。在时间窗约束下的路径问题VRPTW)是VRP的概括,规定应在一个客户给定的时间窗内送达,增加了复杂性VRPTW中遇到的额外复杂过程是,从一个仓库时间窗的路线长度限制提高,以及等待时间的成,这是发生在车辆到达客户点太早所造成的。时间窗的具体问题结合实,包括银行交付,邮递,工业垃圾收集,校巴路线和路况,这些客户必须在运输物品或提供服务提供通道,证明,或者付款[所罗门和戴斯洛赛斯,1988]。在实际操作,除了是一个最重要的操作研究问题外,车辆路径问题也是最难解决的问题之一。它非常接近于最著名的组合优化问??行商问题,即

一个商人必须访问所有客户则拜访路线要怎么选择。旅行商问题是一个非常难的问题。它被认为是一个永远找不到计算结束去保证这是最佳解决方案的问,而这些运输路径问题则更为复杂。即使是小型车型和中型数量的运输要,需规划的任务也是非常复杂。因此策划者很快就会不堪重负也是并不奇怪的,必须将其转化为简单的,适应本地规则的运输路径一步我们将介绍遗传算法的基本原理和一些时间窗约束下的车辆路径问题。2遗传算法的一般原则遗传算法(GA)是一种在人口遗传基础上,适应启发式的探访方法本概念是发展于荷兰,1975],实际上将遗传算法用于解决复杂的问,证明是在[德容,1975][哥德堡1989]中。文献和遗传算法的细节也[阿兰德,2000]和[穆棱贝,1997]中找到。新的一代独立创作,要涉及四个步骤或阶段代表,选择,重组和突变。解决方案的代表由显著特点的染色体编码组,确定为一个独立的个体。通常染色体有一系列的基因组成,这就抓住了一个解决方案的最基本特征。重组或者再生产过程可以使父母选择使用的基因并形成下一代结合染色体特征,能使创造出的后代更具有适应性于突变它由一个独立的随机更改的基因组成,能进一步探索解决方案和确保或保存遗传多样性个突变的发生通常概率很低。新一代的创建,通过复制选择,再生产和突变过程,直到所有新的染色体在人类中产生,取代旧的遗传质量和多样性之间的适当的平衡,是需要在人群中,用来支持高效的搜索。虽然理论结果表明,传算法的独特已经获得染色特的位,并不能简单地代表所有问题。这样的话,特别,对于时常发生的问,如车辆路径问,

一个整数就代表更正确们知道只有一个方式衫葛,1995],在车辆路径文件中运用位串代表。在其他时间窗约束下的路径问题中可以忽视编码问题。3时间窗约束下的路径问题的应用[衫葛,1995]描述了一个叫做基甸分配的方法,即运送指定客,通过遗传算法将客户分割成几个部分,客户之间路线的形成要用最低级的插入方式[戈登和斯图沃特,1985]在下一步中,路线用λ转变得到改善[奥斯曼,1993]这两个进程是有限次数的迭代运行,能提高解决方案的质量索从聚类的客户开始,根据他们的极坐标角度或随机都可以。这个探索策略建议的接,对于探索中的反抗特定惩罚因素是不可行的基甸系统中,根据相应的路径成本,每一个染色体代表了一系列聚类计划以及适应价值的可能叉操作与随机选择部分在染色体和变异之间交换,被用于随机的价值的概率是非常低的。[波文和班戈,1996]提出了一种遗传算法,即直接使用遗传操作去解决问题从而避免了编码问题初的人口计算是最低级的插入启发式创建的所罗,1987],适应价值的接受方法是基于路线总共的车辆数和总的所用时间择过程是随机的并偏向最好的解决方案为此,使用线性排名计划在重组阶段两个起始方法,合并为一个,因此能保证新方案的可行性。两种交叉运行用来修饰随机选择路,或在其他起始方案中插入一种路径个特约维修商,是将其运用到产生下一代的新的可行方案。变异算子的目的在于减少路径的数量终,为了局部优化的解决方案,变异算子基于or-opt[尔,1976][格等,1998]提出基于良好构架的启发式的杂交遗传算法。作者省却了编码问题,并代表一系列可行路径的解决方案。带有近邻的初始种群的创建灵感来自于[所罗,1987]个人的适应价值基于路径数量,相应的总距离和选择目的,因此作者称其为赌轮计划这项计划中选择一个