带有路线平衡的生产线路问题的一种计算方法外文翻译.docx
- 文档编号:18096377
- 上传时间:2023-08-13
- 格式:DOCX
- 页数:11
- 大小:91.58KB
带有路线平衡的生产线路问题的一种计算方法外文翻译.docx
《带有路线平衡的生产线路问题的一种计算方法外文翻译.docx》由会员分享,可在线阅读,更多相关《带有路线平衡的生产线路问题的一种计算方法外文翻译.docx(11页珍藏版)》请在冰点文库上搜索。
带有路线平衡的生产线路问题的一种计算方法外文翻译
带有路线平衡的生产线路问题的一种计算方法外文翻译
外文翻译
原文
Analgorithmforthecapacitatedvehicleroutingproblemwithroutebalancing
MaterialSource:
SpringerLinkAuthor:
IstvánBorgulya
Abstract:
Inthispaper,wepresentamulti-objectiveevolutionaryalgorithmforthecapacitatedvehicleroutingproblemwithroutebalancing.Thealgorithmisbasedonaformerlydevelopedmulti-objectivealgorithmusinganexplicitcollectivememorymethod,namelytheextendedvirtualloserEVL.WeadaptedandimprovedthealgorithmandtheEVLmethodforthisproblem.Weachievedgoodresultswiththissimpletechnique.Incaseofthisproblemthequalityoftheresultsofthealgorithmissimilartothatofotherevolutionaryalgorithms.
Keywords:
Evolutionaryalgorithm;Multi-objectiveoptimization;Explicitcollectivememory;Combinatorialoptimization;CVRP
1Introduction
ThevehicleroutingproblemVRPisawell-knownandfrequentlyanalyzedmodelandoftenusedinreallifeapplications,liketransportation,logistics,andscheduling.OneofthesimplestversionsoftheVRPistheCapacitatedVehicleRoutingProblemCVRP.TheCVRPisagraphproblemthatcanbedescribedasfollows:
thequantityqishouldbedeliveredtocustomerii1,,nfromasingledepotusingafleetofvehicleswithcapacityC.AsolutionoftheCVRPisacollectionoftourswhereeachcustomerisvisitedonlyonceandthetotaltourdemandisatmostC,withtheobjectiveofminimizingthetotaldistancetraveledbyallthevehicles.
TheVRPhasbeenprovedtobeNP-hardLaporte1992andthesolutionmethodsappliedarangefromexactmethodstospecificheuristicsandmeta-heuristics.ThebranchandboundorbranchandcutmethodsprovideoptimalsolutionsHadjiconstantinouandChristofides1995however,someproblemswith75nodesarenotsolvedyetPrins2004.Therefore,heuristicalgorithmsarehighlywelcometosolvelargeproblems.Intherealmofheuristicswecanmentionspecificheuristicsliketheneuralnetworkandmeta-heuristicslikesimulatedannealing,tabusearch,evolutionaryalgorithmsEA,antcolonyoptimization,particleswarmoptimizatione.g.Sunetal.2005;VanBreedam2001;BergerandBarkaoui2003;CordeauandLaporte2002;MazzeoandLoiseau2004;Chenetal.2006;El-Sherbeny2001;Tavaresetal.2003.
InreallifeapplicationstherearemanyversionsofCVRP.Forexample,wecanmentionVRPwithtimewindowconstraints,dynamicvehiclerouting,orsomemultiobjectiveversionsoftheVRP.Inthemulti-objectiveversionstheadditionalobjectivescanbe,e.g.theminimumnumberofthevehicles,thebalanceoftheroutes,orindynamiccases,theminimumtotalmeantransittimeandtheminimumtotalvarianceintransittime,andevenmoreobjectivescanbeincluded.
Inthispaper,weconsiderthecapacitatedvehicleroutingproblemwithroutebalancingCVRPRB.Thefollowingtwoobjectivesareconsidered:
f1:
Minimizationofthedistancetraveledbythevehicles.
f2:
Minimizationofthedifferencebetweenthelongestroutelengthandtheshortestroutelength.
ReferencesJozefowiezetal.2002,2006;Pasiaetal.2007a,balreadycontainsolutionsforthisproblem.InJozefowiezetal.2002,2006,therearetwodifferentsolutionswithEAs:
anislandmodelwithtabusearch,andanislandmodelwiththeNSGAIImethodDebetal.2002.Pasiaetal.2007a,bdescribeamethodwithpopulation-basedlocalsearch,andanotheronewithantcolonyoptimization.
Inthispaper,wepresentanewEAforthemulti-objectiveproblem.
MotivationforanewEA
InanearlierworkBorgulya2006wepresentedanewmethodforthebi-objectivequadraticassignmentproblembQAP,usinganewextendedversionofanexplicitcollectivememorymethod,called‘virtualloser’.IntheextendedvirtualloserEVLweenabledthevirtuallosertohandleseveraldiscretevaluesinsteadofbinaryvalues,andthevaluesofvariablesforexamplecanbethevaluesofpermutations,too.WecanusethisextendedvirtuallosertechniqueincaseofcombinatorialmodelswithouttheproblemdiscretemakingthroughbinaryorGraycoding.ForthebQAP,wehadmodifiedourearliermulti-objectiveEAusingtheEVLtechnique,andwepresentedfineresultswiththenewalgorithmnamedMOSCA2b.
UsingMOSCA2bwewanttoindicatethatthisalgorithmframeworkcanbeappliedsuccessfullyforsolvingfurthertypesofmulti-objectivecombinatorialproblems,too.LetusnotethatMOSCA2bwasappliedfirsttimeinBorgulya2007tosolvemultiobjectiveTSP.NowwearegoingtouseMOSCA2btosolveCVRPRB.
FortheCVRPRBwemodifiedtheMOSCA2bBorgulya2006:
?
weadaptedtheEVLfortheCVRPRB.
?
weusedtheEVLtechniquewitharestartstrategy.
?
weusedaspecialversionofthetruncationselection.
?
weusedtwospecialstochastic2-optlocalsearchalgorithmstoimprovethesolutions.
ThepublishedevolutionaryalgorithmssolvetheCVRPRBproblemsbyusingsophisticatedselection,recombinationandmutationoperators.Wewillshowthatourapproachisasimplerone.
Thepaperisorganizedinthefollowingway:
Sect.2showsthestructureoftheMOSCA2balgorithm,andSect.3describesthedetailsofthealgorithm:
theoperationsfortheCVRPRB,theextendedvirtualloserandthemutationoperator,andthedetailsoftheimplementation.Section4showsourcomputationalexperiencewiththenewEAandcomparesourresultstothatofotherheuristics.Section5givestheconclusions.
2ThestructureofMOSCA2b
TheprinciplesofthegeneralMOSCA2versionareasfollowsBorgulya2005:
thepopulationisseparatedintotsubpopulations,eachsubpopulationapproximateotherpartoftheParetofront.Eachsubpopulationisstoringonlynon-dominatedindividualsofthepossiblemembersofthesubpopulationatalimitedamount.Thedominanceofanewdescendantgettingintothesubpopulationisdeterminedbycomparingittoadesignatednon-dominatedindividual,theprototype.Ifitfindsanon-dominateddescendantsuperiortothepreviousprototype,itdeletestheformermembersofthesubpopulation,andreplacestheprototypebythenewdescendant.
DuringtheevolutionprocessthenewpotentialParetooptimalsolutionsareperiodicallystoredinaseparatearchive,andwehavetheresultinthisarchive.IfthisseparatearchiveSARCisfull,thealgorithmdeletesagivenpercentage10%ofitselements.Weselectfirstthemostdominatedindividualsfordeletion,afterthatcontinuouslyoneoftheindividualsclosetoeachother.
TheMOSCA2usesa2-stagealgorithmstructurewherebothstagesareasteadystateEA.Thefirststageisaquick“preparatory”onewhosetaskistoimprovethequalityoftheinitialpopulation.ThesecondstageisanevolutionarystrategywithsomespecialoperatorsmoredetailinBorgulya2005.
VersionMOSCA2bismodifiedforcombinatorialproblemsandusessomespecialoperators.Theselectionisaspecialtruncationone,andmutationisbasedonEVL.ThealgorithmusesalocalsearchprocedurewithaweightedobjectiveDeb2001,anditdoesnotuseanyrecombinationoperator.Asadditionaloperation,thealgorithmupdatestheECMmatrix,thememoryoftheEVLmethod.
3Experimentalresults
TheresultoftheCVRPRBisasimilarParetofrontbyeverytestproblemaswecanseeinFig.1.UsuallywedescribetheseresultsbytwopointsoftheParetofront:
withtheminimumvalueofthedistancetraveledbythevehiclesandtheminimumvalueofthedifferencebetweenthelongestroutelengthandtheshortestroutelength.WeshowtheresultsofthetestproblemsinTable1.Everytestproblemwasrunfivetimes,andthetableshowsthebestresultssimilarwayasintheotherpapers.Inthetablewegivetheproblemnamename,thenumberofthecustomersn,thebestlengthfoundmindistwithitsassociatedbalancebal,thebestbalancefoundminbalwithitsassociatedlengthdist,theaveragenumberofthesolutionsintheapproximationseff.FinallywegivetheimumnumberofgenerationsinthousandsgenandtheaveragerunningtimeinCPUsecondsCPU.
Tocomparetheresultsofouralgorithmwechosetwometa-heuristics.ThefirstisaparallelhybridEAthatusestabusearchaslocalsearchJozefowiezetal.2002notation:
Ptabu.ThesecondoneisalsoaparallelEAJozefowiezetal.2006thatisbasedonthestandardmulti-objectiveEA,theNSGAIInotation:
PNSGADebetal.2002.BothmethodssolvedonlythebenchmarkproblemsofChristofides,theydidnottrytosolvebenchmarkproblemsfromtheVehicleRoutingDataSets.WecouldnotchoosethemethodsPasiaetal.2007a,bforcomparison,becausetheydidnotpublishthenecessarydates.
OneofthemainproblemsofthiscomparisonisthattheoptimalParetofrontiersarenotknown.Wecancomparethevalueobtainedforthetotallengthcriteriontothebest-knownsolutionsoftheCVRPobjectivef1only.WefindsimilarcomparisonsinJozefowiezetal.2002andJozefowiezetal.2006aswell.Weenrichthecomparisonapplyingasingle-objectivemethodthatsolvestheCVRPproblemsinbothtestsets.ThenameofthismethodistheCLOVES,publishedinGaneshandNarendran2007.
Table2presentstheresultsofthecomparison.Thetableexhibitstheproblemnamename,thebestknownsolutionoftheCVRPBKS,andtheerrorofthebestfoundlengthfromBKSError%.TheError%arebasedontheresultsofMOSCA2b,Ptabu,PNSGA,andCLOVES.DuetothiscomparisonwecanchooseresultswithoneprocessorexceptthoseofPtabu,whereweknowtheresultsonlywithmoreprocessors.
Notwithstanding,ourdatesareveryincomplete,sowetrytocomparethequalityofthedifferentresults.BecauseoftheproblemsofVehicleRoutingDataSets,wecancomparetheresultsofMOSCA2bandCLOVESonly.DuetotheseproblemsMOSCA2bhasbetterresul
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 带有 路线 平衡 生产 线路 问题 一种 计算方法 外文 翻译