MultiplePeoplePickingAssignmentandRoutingOptimizationBasedonGeneticAlgorithm

更新时间:2024-02-16 作者:用户投稿原创标记本站原创 点赞:23315 浏览:99885

【Abstract】Inordertoimprovethepickingefficiency,reducethepickingtime,thispapertakeartificialpickingoperationofacertaindistributioncenterwhichhasdouble-areawarehouseasthestudyingobject.Discussthepickingtaskallocationandroutingproblems.EstablishtheTSPmodeloforder-pickingsystem.CreateaheuristicalgorithmbasesontheGeicAlgorithm(GA)whichhelptosolvethetaskallocatingproblemandtogettheassociatedorder-pickingroutes.AndachievethesimulationexperimentwiththeVisual6.0C++platformtoprovetherationalityofthemodelandtheeffectivenessofthearithmetic.

【Keywords】Order-pickingtaskallocating;Associatedorder-pickingroutes;Aheuristicalgorithmbasedongeicalgorithm

Goodsindistributioncentermustbepickedupanddistributedbytheorderform,thenachievesthehandsofcustomers.Investigationshowsthat,order-pickingtaskisnotonlyawasteoftimebutalsohasahighcost[1].Sotheoptimizationoforder-pickingroutingprobleminraisingtheefficiencyoflogisticscenterhasanimportantrole.In1976,S.Sahni[2]provesthestorageallocationproblemisNP-pleteproblem,withthisconclusionlaterscholarshebeguntostudythestorageallocationheuristicalgorithm.FelixT.S.Chan[3]studiestheStorageAssignmentPoliciesonwarehousepartitioningandmodityclassificationproblems.Inordertoachieveahigherefficiency,heusestheapproachtomakeaproperredistributionforthelayoutofthewarehouse.WithbiningtheStorageAssignmentpoliciesandthePathOptimizationStrategyR.DeKker[4]putorwardaneffectivewayinimprovingthepickingefficiency.T.Le-Duc[5]establishedastatisticalmodelinassessingtheeragedistanceoforder-pickingprocess,andproposedakindofDoubleoptionexchangeheuristicalgorithminsolvingwarehousepartitioning.Shizhen-Li[6]addressesanorder-batchingmethodbasesonClusteringAnalysis,shefocusonobtainingtheminimumtreldistance.Tranormsthisproblemintotheclusteringproblembasesontheestablishedmathematicalmodel,proposesasolutionofsimilaritycoefficientmethodtogetanearoptimalresult.YanRu-Li[7]makesadiscussiononhowpickingstrategieseffectstheefficiencyoforder-pickingandthelevelofservice.ConsideringtheReal-timeofcustomerorders,anadaptivefunctionofthegeicalgorithmisdesignedtomakeareasonablesequence.Zhen-Li[8]tranormedtheroutingoptimizationproblemintoTSPissue,usesanichegeicalgorithm(NPGA)tosolveit,andobtainstheoptimalpathoforder-pickingtask.Hong-Wang[9]makesaresearchontheroutingoptimizationproblembasesonthedouble-areawarehouse,discusseshowtosolvetheproblemthatoneorderpickedbymultiplepickingcarts.Mostoftheresearcherentionedabovefocusonwarehouselayout,orderprocessingandroutingoptimizationproblems.Theyneglectthedetailsoftaskingwhentherearemultipleorderpickers.Thisarticlenotonlymakesadeepresearchontheoptimizationoforder-pickingroutingproblembutalsosolvestheproblemoftaskallocation.

1Problemdescription

Pickingprocesscanbedividedinto4parts:theformationofpickingdata(generatecustomerorders),walkingandhandling,picking(takeandconfirmation),classificationandconcentration.Thepickingtimecanbedividedinto:orderprocessing,generatingpickinginstructions,thetotalwalkingtime,thetimerequiredtofindthecorrectstorage.Aftercustomerssubmittheirorders,theformationofthepickingdataisestablished,andthenitwillbeassignedtoeachpicker.PickerswillgofromtheI/OpottoeachlocationofthegoodswhenfinishingthepickingprocesstheyebacktotheI/Opot.

1.1Modelassumptions

1)1ordercontainsatleast1atmostN,(N≥1)kindsofgoods(Nrepresentsthetotalstorageallocationinthewarehouse);

2)MPickersworkatthesametime;

3)Supposesallofthepickersworkingandwalkingatthesamespeed;

4)Thelengthofalleywayandgangwayandthewidthanddepthofthecontaineraregiven.(Walkingdistancecanbecalculated);

5)Becausethewarehousechannelortunnelisnotwideenough,itcanonlyholdonepickingcartthrough,sowhentwopickingcartencounter,thetwopickersshouldexchangetheirordersandcontinuetowork;

6)Pickingcartsareordinaryhandcartswhichcanbeusedrepeatedlywithoutconsideringthecost.Becauseatthesametimetherearemanypickersworktogether,sothecapacityofpickingcartisnotconsidered;

7)Theitemsrequiredintheordersarenotoutofstock;

1.2Modeling

ThebasicstructureasshowninFigure1isamontwo-areawarehouse.Thewarehouseposedbymanyshelvesandacertainnumberoflanewayswhichhethesamelengthandwidth(shownastransversechannelsinFig.1.)Thewarehousedividedbythemainchanneleragely(inthemiddleofthewarehouseshownasverticalchannelsinFig.1).Eachsideofithasasidechannelwhichparalleltothemainchannel.TheI/Oportdirectlyoppositethemainchannel.

Fig.1Schematicdiagramofwarehouselayout

AnyStoragelocationintheWarehousecanbeexpressedas:pi等于p(xi,yi,zi),i等于1,2..N

Inthiormula,xiindicateslanewaynumber,xi∈{1,2..a};yiindicatesthetwoareas(theeasthalfandthewesthalf)oftheWarehouse;yi等于1,east0,west;ziindicatessectionnumber,zi∈{1,2..b},1→b/2representstheeasthalf,b/2+1→brepresentsthewesthalf;Nisthetotalnumberoflocationsinwarehouse.ThewidthofthecounterisD1,D1等于1meteranditsdepthisD3,D3等于0.5meter;ThewidthofthechannelisD2,D2等于1meter;theWidthofthemainchannelisD4,D4等于2meter.

Whenanytwolocationsofpiandpjdistributeinthesamelaneway(xi等于xj),theshortestdistancebetweenthemis:

dij等于zi-zj×D1,{(1≤zi≤b/2,1≤zj≤b/2)or(b/2

Whenthetwolocationsarenotdistributedinthesamelaneway(xi≠xj),canbedividedintothefollowingthreecircumstances:

Whenyi等于yj等于1:

dij等于zi+zj×D1+xi-xj×D2+2D3,(1≤zi≤b/4,1≤zj≤b/4)30-zi-zj×D1+xi-xj×D2+2D3,(b/4

Whenyi等于yj等于0:

dij等于zi+zj-30×D1+xi-xj×D2+2D3,(b/2

Whenyi≠yj:

dij等于zi-zj×D1+xi-xj×D2+2D3+D4,{(1≤zj≤b/2,b/2

ThedistancefromI/Opointtoanylocationis:

d0i等于(b/2-zi)×D1+(xi-1)×D2+2D3+D4/2,(xi∈{1..,a},1≤zi≤b/2)(zi-b/2)×D1+(xi-1)×D2+2D3+D4/2,(xi∈{1..,a},b/2

Theobjectivefunctionofcalculatingthetotaldistanceis:

D等于mindij×xij+d1O+dNO(1)

Intheformulaabove:dijindicatesthedistancebetweenanytwolocations(locationiandlocationj)inthewarehouse;d1,O(ordN,O)indicatesthedistancefromthefirst(orthelast)pickingmoditytotheI/Opoint.Because,pickerssetofffromtheI/Opoint,whentheyfinishtheirtaskstheyhetodeliverthegoodstotheI/Opoint.

Theconstraintconditionsare:

xij等于1,(i≠j;j等于1,2..N)(2)

xij等于1,(i≠j;i等于1,2..N)(3)

Intheformulasabove:xijandxjiaredecisionvariables,ifthepickergofromlocationiandlocationj,xij等于1orelsexij等于0;xijandxijindicatethetotalfrequencyoflocationitolocationjandlocationjtolocationi.Whenbiningtheformulasof(2)and(3)makeanindicationofthereisonlyonewaybetweeniandjlocations,sopickeraynotmakearepeatedpicking.2Algorithmicprocesses

1)Therequiredinformation:Makeastatisticforallthelocationsofpickinggoods,designaprograminordertocalculatetheshortestdistancesbetweenanytwogoods.Setupthedistancematrixwhichisrepresentedbyatwo-dimensionalarrayintheprogram.

2)Coding:nindicatesthetotallocationnumberofthepickinggoods.Encodeallthepickinglocationswith0,1..,n-1(eachpickinglocationhasauniquenumber).

3)Initialization:Generateminitializedarraysinthemethodofarrangingthenlocationnumberrandomly(mindicatesthenumberofthereservedindividualsineachgeneration).

4)Alternative:Whenanewgenerationemergences,abandonthedisadvantageswiththeprobabilityofpsandthenreplacetheinferiorgroupwiththeoptimalindividuals.

5)Cross:Withthecrossoverprobabilitypcselectstheindividualromthecurrentgeneration,andthendividedalltheselectedindividualsintotwogroupsasthetwomalesofthenextgeneration.Namethemasparent1andparent2.Selectacrossoverpointrandomlyforeachpairoftheparent.Thecrossingprocessisdesignedaollows:

father1:0,1,2,3|4,5,6,7,8,9father2:5,6,4,3|2,1,0,8,7,9?圯son1:0,1,2,3|*,*,*,*,*,*son2:5,6,4,3|*,*,*,*,*,*

?圯son1:0,1,2,3|5,6,4,8,7,9son2:5,6,4,3|0,1,2,7,8,9

Asshownabove“|”indicatesthecrosspoint;the“*”partduplicateromfirstelementofanotherparenttothelastone,extracttheelementswhicharedifferentfromtheformerones.

6)Variation:Withthemutationratepmselectstheindividualromthecurrentgeneration,anddeterminetwomutationpointsrandomlyforeachindividual(selectedasthecrossingpoint),exchangethetwoelementsatthemutationpoints,aftertheprocessofvariation,newindividualsappear.Inordertooidprematureconvergence,whentheevolutionnumberislargeenoughthemutationratepmwillbeincreased.

7)CalculateObjectivefunctionvalue:anyindividual,e.g.0,1,2,3,4,5,6,7,8,9,*,*,*******,canbedividedintoMone-dimensionalarraysbytheneverrepeatedM-1randomseparationpoints(M≤n).“|”representtheseparationpoints,e.g.0,1,2,3|4,5,6,7,8|9,*,*,*|******...(thenumberofpickersisM,thisstepaimtoassigntaskortheMpickers).Inthiswaywecansplitanone-dimensionalarrayintochunksofnewarraysas[0,1,2,3],[4,5,6,7,8],[9,*,*,*]..thentakethebiggestobjectivefunctionvalueofthenewarraysastheoriginal’s.8)Select:accordingtotheobjectivefunctionvalue,sortallindividualsofeachgenerationandreservethetopcindividuals.

9)Repeatthestepromthe4thtothe8thdescribedabove,untilitreachesthemaxgeneration(genmax).

10)Theend:OutputtheMsubarraysofthepopulationofthefinalgeneration,meanwhileexporttheobjectivefunctionvaluesofeachindividual.

3Thesimulationexperimentandresult

1)Supposethatinacertainperiodoftime,distributioncenterreceives20customerorders,thetotaltypesofgoodsinthe20ordersaccountor50whichlocatedinthefollowlocations:(1,1,10),(1,1,12),(1,1,15),(1,0,16),(1,0,18),(1,0,19),(1,0,20),(2,1,11),(2,1,13),(2,1,14),(2,0,15),(2,0,16),(2,0,18),(2,0,21),(3,1,8),(3,1,15),(3,0,16),(3,0,17),(3,0,21),(3,0,22),(3,0,23),(4,1,12),(4,1,14),(4,0,17),(4,0,18),(4,0,23),(4,0,24),(5,1,12),(5,1,13),(5,1,14),(5,0,15),(5,0,17),(5,0,18),(6,1,9),(6,1,10),(6,1,11),(6,1,14),(6,0,16),(6,0,17),(6,0,20),(6,0,22),(7,1,10),(7,0,16),(7,0,21),(8,1,10),(8,1,12),(8,1,15),(8,0,19),(9,0,16),(10,0,16);

2)Cordthe50locationswith0~49decimalnumbers.

3)ImporttheLocationinformationintotheprogram,Setupparametersaollows:N等于100;M等于2,M等于3orM等于4;pc等于0.9;pm等于0.1;c等于40;genmax等于200.

WhenM等于2,theoptimalpathis:

[4,3,2,1,8,9,10,11,12,16,17,23,24,29,30,31,34,35,36,37,42,45,46,47,48,49,50],[5,6,7,15,14,13,22,21,20,19,18,28,27,26,25,33,32,41,40,39,38,44,43];Theshortestwalkingdistance:S等于518meters.

WhenM等于3,theoptimalpathis:

[7,6,5,1,2,3,4,15,14,13,8,9,10,11,12,16,17,22,21,20,19,18,23,24],[28,27,26,25,33,32,29,30,31,41,40,39,38],[44,43,48,49,50,45,46,47,42,34,35,36,37];Theshortestwalkingdistance:S等于306meters.

WhenM等于4,theoptimalpathis:

[31,30,29,23,24,17,16,12,11,10,9,8,4,3,2,1],[28,27,26,25,18,19,20,21,22,15,14,13,5,6,7],[50,49,48,43,44,38,39,40,41,33,32],[45,46,47,42,34,35,36,37];Theshortestwalkingdistance:S等于189meters.

4TheTag

Thispapertakesartificialpickingoperationsina(下转第57页)(上接第27页)certaindistributioncenterwhichhasdouble-areawarehouseasthestudyingobject.Establishesthemathematicalmodel,designsaheuristicalgorithmbasedonthegeicalgorithm,andobtainsagoodresult.However,thereisstillmuchroomforimprovement,theactualprocessoforder-pickingprocessiuchmoreplicatedthantheestablishedmathematicalmodel,therearemanyrestrictions,forexample,thepickingcartaybecapacityconstrained,workingefficiencyofdifferentworkerscannotbethesame,fewofthewarehousehasainerraticgeometricfigure,onlytakingthepickertreldistanceasthemeasurestandardsisnotaccurateenough.Intheprocessoforder-batching,thesubmissionofcustomerordersisadynamicprocesswhichshouldalsobeconsideredwhencalculatingtheoptimalpath.Inaddition,thealgorithmitselfalsohassomedisadvantages,howtoexpeditetheconvergencerate,oidthelocalconvergenceandmakeaneasycalculationalsoneedurtherstudy.【References】

[1]Drury,J..Towardoreefficientorderpicking[J].IMMmonograph,No.1.Cranfield,UK:TheInstituteofMaterialsManagements,1988.

[2]Sahni,S.&Gonzalez,T.L..P-pleteapproximationproblems[J].JournaloftheAssociationofComputerMachinery,1976(23):555-565.

[3]CHANFelixT.S,CHANH.K.ImprovingtheProductivityofOrderPickingofaManual-pickandMulti-levelRackDistributionWarehousethroughtheImplementationofClassbasedStorage[J].ExpertSystemswithApplications,2011(38):2686-2700.

[4]DeKker,R.,deKoster,R.,VanKalleveen,H.,&Roodbergen,K.J.Improvingorder-pickingresponsetimeatAnkor’swarehouseInerfaces[J].2004,34(4):303-313.

[5]Le-Duc,T.,&deKoster,R..Treldistanceestimatedandstoragezoneoptimizationina2-blockclass-basedstoragestrategywarehouse[J].InternationalJournalofProductionResearch,2005,43(17):3561-3581.

[6]LiShizhen,DuWenhong.Theclusteringanalysisoftheorder-batchingpickingmodelbasedonheuristicalgorithm[J].Packagingengineering,2008(12):5-9.

[7]LiYanru.Orderpickingreal-timeschedulingproblembasedongeicalgorithm[J].Packagingengineering,2011,32(13):97-101.

[8]LiZhen,HuQingdong.Researchonartificialpickingrouteoptimizationbasedonnichegeicalgorithm[J].Logisticstechnology,2011(6):95-98.

[9]WangHong,FuZhuo.Researchondouble-areawarehousepickingrouteoptimizationbasedongeicalgorithm[J].ComputerengineeringandApplications,2009,45(6):224-228.

[责任编辑:丁艳]

相关论文范文