時間窗約束下的車輛路徑問題遺傳算法外文翻譯外文翻譯原文GeneticAlgorithmsfortheVehicleRoutingProblemwithTimeWindowsMaterialSource:SpecialissueonBioinformaticsandGeneticAlgorithmsAuthor:OlliBr?ysyIntroductionVehicleRoutingProblemsVRPareallaroundusinthesensethatmanyconsumerproductssuchassoftdrinks,beer,bread,snackfoods,gasolineandpharmaceuticalsaredeliveredtoretailoutletsbyafleetoftruckswhoseoperationfitsthevehicleroutingmodel.Inpractice,theVRPhasbeenrecognizedasoneofthegreatsuccessstoriesofoperationsresearchandithasbeenstudiedwidelysincethelatefifties.Publicservicescanalsotakeadvantageofthesesystemsinordertoimprovetheirlogisticschain.Garbagecollection,ortowncleaning,takesaneverincreasingpartofthebudgetoflocalauthoritiesAtypicalvehicleroutingproblemcanbedescribedastheproblemofdesigningleastcostroutesfromonedepottoasetofgeographicallyscatteredpointscities,stores,warehouses,schools,customersetc.Theroutesmustbedesignedinsuchawaythateachpointisvisitedonlyoncebyexactlyonevehicle,allroutesstartandendatthedepot,andthetotaldemandsofallpointsononeroutemustnotexceedthecapacityofthevehicleTheVehicleRoutingProblemwithTimeWindowsVRPTWisageneralizationoftheVRPinvolvingtheaddedcomplexitythateverycustomershouldbeservedwithinagiventimewindow.AdditionalcomplexitiesencounteredintheVRPTWarelengthofrouteconstraintarisingfromdepottimewindowsandcostofwaitingtime,whichisincurredwhenavehiclearrivestooearlyatacustomerlocation.Specificexamplesofproblemswithtimewindowsincludebankdeliveries,postaldeliveries,industrialrefusecollection,school-busroutingandsituationswherethecustomermustprovideaccess,verification,orpaymentupondeliveryoftheproductorservice[SolomonandDesrosiers,1988].Besidesbeingoneofthemostimportantproblemsofoperationsresearchinpracticalterms,thevehicleroutingproblemisalsooneofthemostdifficultproblemstosolve.Itisquiteclosetooneofthemostfamouscombinatorialoptimizationproblems,theTravelingSalespersonProblemTSP,whereonlyonepersonhastovisitallthecustomers.TheTSPisanNP-hardproblem.Itisbelievedthatonemayneverfindacomputationaltechniquethatwillguaranteeoptimalsolutionstolargerinstancesforsuchproblems.Thevehicleroutingproblemisevenmorecomplicated.Evenforsmallfleetsizesandamoderatenumberoftransportationrequests,theplanningtaskishighlycomplex.Hence,itisnotsurprisingthathumanplannerssoongetoverwhelmed,andmustturntosimple,localrulesforvehiclerouting.Nextwewilldescribebasicprinciplesofgeneticalgorithmsandsomeapplicationsforvehicleroutingproblemwithtimewindows.GeneralprinciplesofgeneticalgorithmsTheGeneticAlgorithmGAisanadaptiveheuristicsearchmethodbasedonpopulationgenetics.Thebasicconceptsaredevelopedby[Holland,1975],whilethepracticalityofusingtheGAtosolvecomplexproblemsisdemonstratedin[DeJong,1975]and[Goldberg,1989].Referencesanddetailsaboutgeneticalgorithmscanalsobefoundforexamplein[Alander,2000]and[Mühlenbein,1997]respectively.Thecreationofanewgenerationofindividualsinvolvesprimarilyfourmajorstepsorphases:representation,selection,recombinationandmutation.Therepresentationofthesolutionspaceconsistsofencodingsignificantfeaturesofasolutionasachromosome,defininganindividualmemberofapopulation.Typicallypicturedbyabitstring,achromosomeismadeupofasequenceofgenes,whichcapturethebasiccharacteristicsofasolution.Therecombinationorreproductionprocessmakesuseofgenesofselectedparentstoproduceoffspringthatwillformthenextgeneration.Itcombinescharacteristicsofchromosomestopotentiallycreateoffspringwithbetterfitness.Asformutation,itconsistsofrandomlymodifyinggenesofasingleindividualatatimetofurtherexplorethesolutionspaceandensure,orpreserve,geneticdiversity.Theoccurrenceofmutationisgenerallyassociatedwithlowprobability.Anewgenerationiscreatedbyrepeatingtheselection,reproductionandmutationprocessesuntilallchromosomesinthenewpopulationreplacethosefromtheoldone.Aproperbalancebetweengeneticqualityanddiversityisthereforerequiredwithinthepopulationinordertosupportefficientsearch.AlthoughtheoreticalresultsthatcharacterizethebehavioroftheGAhavebeenobtainedforbit-stringchromosomes,notallproblemslendthemselveseasilytothisrepresentation.Thisisthecase,inparticular,forsequencingproblems,likevehicleroutingproblem,whereanintegerrepresentationismoreoftenappropriate.Weareawareofonlyoneapproachby[Thangiah,1995]thatusesbitstringrepresentationinvehicleroutingcontext.Inallotherapproachesforvehicleroutingproblemwithtimewindowstheencodingissueisdisregarded.Applicationsforvehicleroutingproblemwithtimewindows[Thangiah,1995]describesamethodcalledGIDEONthatassignscustomerstovehiclesbypartitioningthecustomersintosectorsbygeneticalgorithmandcustomerswithineachformedsectorareroutedusingthecheapestinsertionmethodof[GoldenandStewart,1985].Inthenextsteptheroutesareimprovedusingλ-exchangesintroducedby[Osman,1993].Thetwoprocessesareruniterativelyafinitenumberoftimestoimprovethesolutionquality.Thesearchbeginsbyclusteringcustomerseitheraccordingtotheirpolarcoordinateangleorrandomly.Theproposedsearchstrategyacceptsalsoinfeasibilitiesduringthesearchagainstcertainpenaltyfactors.IntheGIDEONsystemeachchromosomerepresentsasetofpossibleclusteringschemesandthefitnessvaluesarebasedoncorrespondingroutingcosts.Thecrossoveroperatorexchangesarandomlyselectedportionofthebitstringbetweenthechromosomesandmutationisusedwithaverylowprobabilitytorandomlychangethebitvalues.[PotvinandBengio,1996]proposeageneticalgorithmGENEROUSthatdirectlyappliesgeneticoperatorstosolutions,thusavoidingthecodingissues.Theinitialpopulationiscreatedwithcheapestinsertionheuristicof[Solomon,1987]andthefitnessvaluesoftheproposedapproacharebasedonthenumberofvehiclesandtotalroutetime.Theselectionprocessisstochasticandbiasedtowardthebestsolutions.Forthispurposealinearrankingschemeisused.Duringtherecombinationphase,twoparentsolutionsaremergedintoasingleone,soastoguaranteethefeasibilityofthenewsolution.Twotypesofcrossoveroperatorsareusedtomodifyarandomlyselectedrouteortoinsertarouteintotheotherparentsolution.Aspecialrepairoperatoristhenappliedtotheoffspringtogenerateanewfeasiblesolution.Mutationoperatorsareaimedatreducingthenumberofroutes.Finally,inordertolocallyoptimizethesolution,mutationoperatorbasedonOr-optexchanges[Or,1976]isincluded.[Bergeretal.,1998]proposeamethodbasedonthehybridizationofageneticalgorithmwithwell-knownconstructionheuristics.Theauthorsomitthecodingissuesandrepresentasolutionbyasetoffeasibleroutes.Theinitialpopulationiscreatedwithnearestneighborheuristicinspiredfrom[Solomon,1987].Thefitnessvaluesoftheindividualsarebasedonthenumberofroutesandtotaldistanceofthecorrespondingsolutionandforselectionpurposestheauthorsusethesocalledroulette-wheelscheme.Inthisschemetheprobabilityofselectinganindividualisproportionaltoitsfitness;fordetailssee[Goldberg,1989].Theproposedcrossoveroperatorcombinesiterativelyvariousroutesr1ofparentsolutionP1withasubsetofcustomers,formedbyr2nearest-neighborroutesfromparentsolutionP2.Aremovalprocedureisfirstcarriedouttoremovesomekeycustomernodesfromr1.Thenaninsertionheuristicinspiredfrom[Solomon,1987]coupledtoarandomcustomeracceptanceprocedureislocallyappliedtobuildafeasibleroute,consideringthepartialrouter1asaninitialsolution.Themutationoperatorsareaimedatreducingthenumberofroutesofsolutionshavingonlyafewcustomersandlocallyreorderingtheroutes.[Br?ysy,1999a]and[Br?ysy,1999b]extendedtheworkof[Bergeretal.,1998]byproposingseveralnewcrossoverandmutationoperators,testingdifferentformsofgeneticalgorithms,selectionschemes,scalingschemesandthesignificanceoftheinitialsolutions.Whenitcomestorecombination,anapproachwherecustomerswithinrandomlygeneratedsegmentsinparentsolutionP1arereplacedwithsomeothercustomersonthenearroutesofparentsolutionP2isfoundtoperformbest.Thebest-performingmutationoperatorselectsrandomlyoneoftheshortestroutesandtriestoeliminateitbyinsertingthecustomersintootherlongerroutes.Regardingdifferentformsofgeneticalgorithmsitisconcludedthatitisimportanttocreatemanynewoffspringeachgenerationanditisenoughtomaintainonlyonepopulation.Forselectionpurposesso-calledtournamentselectionisfoundtoperformbest.Inthefirstphasetwoindividualsareselectedwitharandomprocedurethatisbiasedtowardsbetterfitnessscores.Inthesecondphase,theindividualwithbetterfitnessisselected.Howeverthedifferencesbetweendifferentschemeswereminor.Anewscalingschemebasedonaweightedcombinationofnumberofroutes,totaldistanceandwaitingtimeisfoundtoperformparticularlywell.Finallytocreatetheinitialpopulation,severalstrategies,suchusheuristicsof[Solomon,1987]andrandomlycreatedroutesweretriedanditwasconcludedthatthebeststrategyistocreateadiverseinitialpopulationthatalsocontainssomeindividualswithbetterfitnessscores.[HombergerandGehring,1999]proposetwoevolutionarymetaheuristicsforVRPTW.TheproposedalgorithmsarebasedontheclassofevolutionaryalgorithmscalledEvolutionStrategies.DifferencestoGAexistwithregardtothesuperiorroleofmutationcomparedtotherecombinationoperators.Heretheindividualrepresentationalsoincludesavectorofsocalledstrategyparametersinadditiontothesolutionvectorandbothcomponentsareevolvedbymeansofrecombinationandmutationoperators.IntheproposedapplicationforVRPTWthesestrategyparametersrefertohowoftenarandomlyselectedlocalsearchoperatorisappliedandtobinaryparameterusedtoalternatethesearchbetweenminimizingthenumberofvehiclesandtotaldistance.Selectionoftheparentsisdonerandomlyandonlyoneoffspringiscreatedthroughtherecombinationofparents.Thiswayanumberλ?μoffspringiscreated,whereμisthepopulationsize.Attheendfitnessvaluesareusedtoselectμoffspringtothenextpopulation.Becausetheparentsarenotinvolvedintheselectionprocess,deteriorationsduringthesearcharepermitted.Thefirstoutofthetwoproposedmetaheuristics,evolutionstrategyES1,skipstherecombinationphase.ThesecondevolutionstrategyES2usesuniformorder-basedcrossovertomodifytheinitiallyrandomlycreatedmutationcodesofthetwoparentsandtriestoimprovethesolutionvectorofathirdrandomlyselectedparentusingthemodifiedcode.ThemutationcodeisusedtocontrolasetofremovalandinsertionoperatorsperformedbyOr-optoperator[Or,1976].Thefitnessvaluesarebasedonnumberofroutes,totaltraveldistanceandonacriterionthatdetermineshoweasilytheshortestrouteofthesolutionintermsofthenumberofcustomersontheroutecanbeeliminated.Theindividualsofastartingpopulationaregeneratedbymeansofastochasticapproach,whichisbasedonthesavingsalgorithmof[ClarkeandWright,1964].[Br?ysyetal.,2000]describeatwo-phasehybridevolutionaryalgorithmbasedonthehybridizationofageneticalgorithmandanevolutionaryalgorithmconsistingofseverallocalsearchandrouteconstructionheuristicsinspiredfromthestudiesof[Solomon,1987]and[Taillardetal.,1997].Inthefirstphaseageneticalgorithmbasedonthestudies[Bergeretal.,1998]and[Br?ysy,1999a]isusedtoobtainafeasiblesolution.Theevolutionaryalgorithmusedinthesecondphasepickseverypairofroutesinrandomorderandappliesrandomlyoneoutofthefourlocalsearchoperatorsorrouteconstructionheuristics.Finally,offspringroutesgeneratedbythesecrossoveroperatorsaremutatedaccordingtoauser-definedprobabilitybyselectingrandomlyoneoutoftwooperators.Selectingeachpossiblepairofroutes,matingandmutationoperatorsarerepeatedlyappliedforacertainnumberofgenerationsandfinallyafeasiblesolutionisreturned.Toescapefromlocalminimum,arcslongerthanaveragearepenalized,iftheyappearfrequentlyduringthesearch.譯文時間窗約束下的車輛路徑問題遺傳算法資料來源:生物信息和遺傳算法特刊作者:奧利布瑞賽1簡介車輛路徑問題(VRP)對我們身邊許多消費(fèi)品都很有意義,例如軟性飲料,啤酒,面包,小吃,汽油和藥品通過一個車隊走合適的運(yùn)輸路線,運(yùn)送至零售網(wǎng)點(diǎn)。在實踐中,VRP被認(rèn)為是一個非常成功的運(yùn)行研究故事,自五十年代后期以來,它已被的廣泛研究。公共服務(wù)也利用這些系統(tǒng)的優(yōu)點(diǎn),來提高物流鏈。垃圾收集,城鎮(zhèn)的清潔,也需要地方當(dāng)局需要增加預(yù)算的部分。一個典型的車輛運(yùn)輸路徑問題可以被描述為,設(shè)計一個最少成本的路線,即從一個倉庫,到一系列地理上分散的點(diǎn)(城市,商店,倉庫,學(xué)校,客戶等)。這些路線的設(shè)計必須遵循每一個點(diǎn)被一輛運(yùn)輸車訪問一次,所有路線起點(diǎn)和終點(diǎn)在一個倉庫,所有點(diǎn)的總需求量,不得超過車輛的運(yùn)輸能力。在時間窗約束下的路徑問題(VRPTW)是VRP的概括,規(guī)定應(yīng)在一個客戶給定的時間窗內(nèi)送達(dá),增加了復(fù)雜性。在VRPTW中遇到的額外復(fù)雜過程是,從一個倉庫時間窗的路線長度限制提高,以及等待時間的成本,這是發(fā)生在車輛到達(dá)客戶點(diǎn)太早所造成的。時間窗的具體問題結(jié)合實例,包括銀行交付,郵遞,工業(yè)垃圾收集,校巴路線和路況,這些客戶必須在運(yùn)輸物品或提供服務(wù)后,提供通道,證明,或者付款[所羅門和戴斯洛賽斯,1988]。在實際操作中,除了是一個最重要的操作研究問題外,車輛路徑問題也是最難解決的問題之一。它非常接近于最著名的組合優(yōu)化問題??旅行商問題,即一個商人必須訪問所有客戶,則拜訪路線要怎么選擇。旅行商問題是一個非常難的問題。它被認(rèn)為是一個永遠(yuǎn)找不到計算結(jié)束去保證這是最佳解決方案的問題,而這些運(yùn)輸路徑問題則更為復(fù)雜。即使是小型車型和中型數(shù)量的運(yùn)輸要求,需規(guī)劃的任務(wù)也是非常復(fù)雜。因此,若策劃者很快就會不堪重負(fù),也是并不奇怪的,必須將其轉(zhuǎn)化為簡單的,適應(yīng)本地規(guī)則的運(yùn)輸路徑。下一步,我們將介紹遺傳算法的基本原理和一些時間窗約束下的車輛路徑問題。2遺傳算法的一般原則遺傳算法(GA)是一種在人口遺傳基礎(chǔ)上,適應(yīng)啟發(fā)式的探訪方法。基本概念是發(fā)展于[荷蘭,1975],而實際上將遺傳算法用于解決復(fù)雜的問題,被證明是在[德容,1975]和[哥德堡,1989]中。文獻(xiàn)和遺傳算法的細(xì)節(jié)也在[阿蘭德,2000]和[穆棱貝,1997]中找到。新的一代獨(dú)立創(chuàng)作,主要涉及四個步驟或階段:代表,選擇,重組和突變。解決方案的代表由顯著特點(diǎn)的染色體編碼組成,確定為一個獨(dú)立的個體。通常染色體有一系列的基因組成,這就抓住了一個解決方案的最基本特征。重組或者再生產(chǎn)過程可以使父母選擇使用的基因,并形成下一代。它結(jié)合染色體特征,能使創(chuàng)造出的后代更具有適應(yīng)性。至于突變,它由一個獨(dú)立的隨機(jī)更改的基因組成,能進(jìn)一步探索解決方案和確保,或保存遺傳多樣性。這個突變的發(fā)生通常概率很低。新一代的創(chuàng)建,通過復(fù)制選擇,再生產(chǎn)和突變過程,直到所有新的染色體在人類中產(chǎn)生,取代舊的。在遺傳質(zhì)量和多樣性之間的適當(dāng)?shù)钠胶?是需要在人群中,用來支持高效的搜索。雖然理論結(jié)果表明,遺傳算法的獨(dú)特已經(jīng)獲得染色特的位串,但并不能簡單地代表所有問題。這樣的話,特別是,對于時常發(fā)生的問題,如車輛路徑問題,一個整數(shù)就代表更正確。我們知道只有一個方式[衫葛,1995],在車輛路徑文件中運(yùn)用位串代表。在其他時間窗約束下的路徑問題中,可以忽視編碼問題。3時間窗約束下的路徑問題的應(yīng)用[衫葛,1995]描述了一個叫做基甸分配的方法,即運(yùn)送指定客戶,通過遺傳算法將客戶分割成幾個部分,客戶之間路線的形成要用最低級的插入方式[戈登和斯圖沃特,1985]。在下一步中,路線用λ轉(zhuǎn)變得到改善[奧斯曼,1993]。這兩個進(jìn)程是有限次數(shù)的迭代運(yùn)行,能提高解決方案的質(zhì)量。探索從聚類的客戶開始,根據(jù)他們的極坐標(biāo)角度或隨機(jī)都可以。這個探索策略建議的接受,對于探索中的反抗特定懲罰因素是不可行的。在基甸系統(tǒng)中,根據(jù)相應(yīng)的路徑成本,每一個染色體代表了一系列聚類計劃以及適應(yīng)價值的可能。交叉操作與隨機(jī)選擇部分在染色體和變異之間交換,被用于隨機(jī)的價值的概率是非常低的。[波文和班戈,1996]提出了一種遺傳算法,即直接使用遺傳操作去解決問題,從而避免了編碼問題。最初的人口計算是最低級的插入啟發(fā)式創(chuàng)建的[所羅門,1987],適應(yīng)價值的接受方法是基于路線總共的車輛數(shù)和總的所用時間。選擇過程是隨機(jī)的并偏向最好的解決方案。為此,使用線性排名計劃。在重組階段,兩個起始方法,合并為一個,因此能保證新方案的可行性。兩種交叉運(yùn)行用來修飾隨機(jī)選擇路徑,或在其他起始方案中插入一種路徑。一個特約維修商,是將其運(yùn)用到產(chǎn)生下一代的新的可行方案。變異算子的目的在于減少路徑的數(shù)量。最終,為了