《Ant Colonies As Logistic Processes Optimizers Carlos A》由会员分享,可在线阅读,更多相关《Ant Colonies As Logistic Processes Optimizers Carlos A(34页珍藏版)》请在金锄头文库上搜索。
1、AntColoniesAsLogisticProcessesOptimizersOutlineAbstractIntroductionThe Logistic ProcessScheduling Using Ant ColonyStimulation Results and AnalysisReal work ExampleConclusionReferencesAbstractTheoptimizationoflogisticprocessesusingantcolonies.Theanalysisofthealgorithmparametersisdoneinasimulation.Itw
2、asappliedtoareallogisticprocessatFujitsu-SiemensComputers.Theresultsshowthattheantcoloniesprovideabettersolutiontologisticprocesses.Introduction WhatisLogistics? Planning,handling,andcontrolofthestorageofgoodsbetweenthemanufacturingpointandtheconsumptionpoint.cross-dockingcentersinsteadofstocks.Thek
3、eyissueistodeliverthegoodsintimebyminimizingthestocks.Theschedulingalgorithmhastodecidewhichgoodsaredeliveredtowhichcustomers.Centralizedstaticschedulingvs.dynamicdistributedschedulingTheLogisticProcess Fig.1.Generalrepresentationofthelogisticprocess TheLogisticProcessThebirthprocess(arrivalofneword
4、ers).Poisondistributionofthebirthprocess:x:therandomvariablenumberoforderslambdaT:theprobabilityofthiseventoccuronacertaintimeT.TheLogisticProcessThe death process (delivery of orders) is modeled by the exponential distribution.T: the random variable : the death rate.ProcessDescription Orderarrival.
5、- orderisasetofcomponents ci and containadesired delivery dateComponentrequest.-Eachcomponenthasquantity.Componentarrival.- supplier delay:timetobedeliveredtothelogisticsystem.ProcessDescription Componentassignment.Thefocusofthispaper-Acomponent stockcontainstheavailablecomponentsandtheirquantity.-A
6、order stockiswaitinglistOrderdelivery-delayd isdifferencebetweenthedeliverydateandthedesireddate.SchedulingPolicies Pre-assignment vs.dynamicdecentralizedapproachPre-assignment(p.a.).Componentsareassignedtospecificorders.NotefficientlyDistributedapproach.Theagentsassociatedwithordersandcomponentsexc
7、hangeinformationbetweeneachother.Moreflexiblethanpre-assignmentSchedulingUsingAntColonies TheoptimizationoftheschedulingprocessisaNP-hardproblem.Theproblemsinformationcanbetranslatedintothepheromones,andusedbyalltheinteractingagentsinordertoachieveagoodglobalsolution.SchedulingUsingAntColoniesTwodif
8、ferentsetofentities:componentfoodsourceordernest.mants,oneperfoodsource,distributethefoodtothennests.Ineveryiterationtofthealgorithm,theantshavetochoosewithsomeprobabilityp whichisthenesttovisitfirst.Then,theydepositapheromoneinthepathfromthefoodsourcetothenest. SchedulingUsingAntColoniesEachantdeli
9、versanamountqijfromthetotalamountqiofcomponenti 1,.,m toanorderj 1,.,n.Sincethereareseveralneststovisit,theantkchooses the path to a particular nestwithaprobability pSchedulingUsingAntColonies ij istheamountofpheromoneconnectingitoj,nij isavisibilityfunctionTk isthetabulistofthekth ant.Thislistconta
10、insallofthevisitedorders+theordersdontneedcomponenttype. and expresstherelativeimportanceoftrailpheromone(experience)withvisibility(knowledge)SchedulingUsingAntColoniesdj isthedelay oforderjWetrytohave nij=1.Thelocalupdateofthepheromoneconcentrationisthengivenbywhere c issmallconstant.SchedulingUsin
11、gAntColoniesAttheendofacompletetourthechangeofpheromonesinallpathsisgivenbythesolutioncanbeevaluatedusingaperformancemeasurenisthenumberofordersanddj isthedelayoforderj.SchedulingUsingAntColoniesFig.2.Exampleofanantcolonyappliedtothelogisticprocesswithpheromoneconcentrationlevelonthetrails:High(),Me
12、dium(-)andLow()SchedulingUsingAntColoniesAteachtourNofthealgorithm(whereeachtourhasnmiterationst),aziscomputedandstoredinthesetZ=z(1),z(N)Ifz(N)ishigherthanthepreviouszZ,thentheactualsolutionhasimprovedandtheusedpheromonesshouldbeincreased.Ifitisworse,theyshouldbereduced.SchedulingUsingAntColoniesTh
13、isisdonebytheglobalpheromoneupdateAlgorithmFig.3.AntcoloniesoptimizationalgorithmforlogisticprocessesSimulationResultsLet lambdaT=10;eachordercanhaveatthemost7differenttypesofcomponentsci;thequantityforeachcomponentvariesrandomlybetween1and20;eachtypeofcomponenthasaconstantsupplierdelay,whichare1,3,
14、2,3,1,2,6daysforcomponentstypec1,c7respectively.Foreachorderadesireddateisgeneratedusinganexponentialdistributionwith=7.Thesimulationreferstoanintervalof6months.SimulationResultsTheresultsarepresentedwiththeparameters=1,=10,p=0.9andNmax =20.Table1.Comparisonbetweentheschedulingmethodsinnumberoforder
15、sSimulationResultsFig.4.Histogramsoftheorderdelayd.Pre-assignmentmethod(left)vs.theresultsfortheants(right).Ants:highernumberofdeliveryontime(d=0)lowerspreadbetweenmaxandmindelayTuningtheParameters Theparameters andwhicharecoupledbetweeneachotherarechangedatthesametime,whileothersdecoupledparameters
16、remainconstant.Varying and, usingafixedvaluep=0.9. TuningtheParametersFig.5.Numberofordersdeliveredforafixed andvarying and.TuningtheParametersNumberofordersdeliveredonthecorrectdateishigh,ifissmall.Ithasanoptimalvaluefor=1Wecanconcludethattheparametertunesthenumberofordersintherightdayandcontrolsth
17、espreadaroundthatvalue TuningtheParametersEvaporationcoefficient(1-p)p0:theincrementreceivedbythenewantsitwillinfluencegreatlythepathsofthenextantsp1thesolutioncanrapidlystagnate.Asitcanbeseen,thevalueofevaporationshouldbearound0.1(p=0.9),inordertoachieveagoodsolutionFig.6.Numberofordersintherightda
18、y,fordifferentsetsoffixed and andvaryingpTuningtheParametersNumberofcoloniesperdayNmax.Fig.7.Evolutionofthesolutionfordifferentnumberofcoloniestoofew:nothaveenoughiterationstofindagoodsolutiontoomany:increasedseverelythecomputationalcost.RealWorldExample Theanalysispresentedanoptimizedsolutionwith=1
19、,=0.5,p=0.9,andNmax=20.InsmalldatasetofthedataFig.8.Histogramsoftheordersdelayd fortheschedulingmethodsRealWorldExampleAnts: More orders are delivered on time. Less orders are delayedGood alternative to pre-assignment scheduling method !ConclusionsToapplyintheantcoloniesoptimizationalgorithmtotheopt
20、imizationoflogisticprocesses.Itsexploredthecorrelationsbetweentheparametersandtheirroleinthealgorithm.Theresultsshowhowtheanalysisisabletoimprovethealgorithmperformance,andexplainthereasonsforthatimprovement.Finally,thealgorithmwasappliedtoarealdataset,andtheantalgorithmprovedtobeabetterschedulingme
21、thodthanthepre-assignment.ConclusionsFuturework:Theuseofadifferentcostfunctionz,Theincorporationintheantswithsomesortofpredictionmechanism.Thereisstillsomeinformationintheprocess,likepriorityoftheorders,thatwasnotusedsofarandcaninfluencetheschedulingofthelogisticprocess.References 1.JayashankarM.Swa
22、minathan,S.F.S.,Sadeh,N.M.:Modelingsupplychaindynamics:Amultiagentapproach.DecisionSciencesJournal29(1998)6076322.McKay,K.,Pinedo,M.,Webster,S.:Apractice-focusedagendaforproductionschedulingresearch.ProductionandOperationsManagement10(2001)3.Palm,R.,Runkler,T.:Multi-agentcontrolofqueuingprocesses.In:ToappearinProceedingsofWorldConferenceonAutomaticControlo-IFAC2002,Barcelona,Spain.(2002)4.Silva,C.A.,Runkler,T.,Sousa,J.M.,Palm,R.:OptimizationoflogisticprocessesusingantThe EndQuestion?Comment?