Abstract It’sthattimeofyearagain,weareexpectedtohelpSantatofindabeststrategytopackhissleigh.Thekeytosolvingtheproblemliesinmakingstandardstomeasurewhatisthebestandmethodtoformulatepresentpackingstrategy.AcommonevaluationforpackingSanta’ssleighisgiveninthetestquestions,whichisregardsasreasonabletoourmind.Sointhearticle,ourmajortargetistoformulateasuitablepackingstrategy,makingthepresentsascompactlyaspossibleandinthebestorderpossible. Wemainlyformulatedthreestrategiesforpackingsleigh.Strategy1:Everyfixednumber( T )ofpresentsinorderaregrouped.Ineachgroup,thepresentsaredividedintobig-sizecategoryandsmall-sizecategory,accordingtowhethertheirlongestside-lengtharebeyondClassification( K ).Whenpacked,thepresentinbigsizewillgainpriority. Strategy2:defineacompactdegree( d )todescribeapresentissuitablewiththeavailablespace.Everypresentshouldbepackinthewaytomakethedegreetothebest. Strategy3:weshouldputthepresentinthelowestplacefromallregions,butwealsosearchthehigherlevelwhenthelowestplacecannotenoughforthepresent’ssize.Thenweputforwardtwooptimizationstrategytoreducethecomputationalcomplexityofthemodel:oneistogiveupthesmallgap;theotheristooptimizetheunavailablespace,andwegetthefinalmodel. Thenwetakethefirst1000presentsofthelistassampletotestthemodelandanalyzetheparameters.Astheresult,wegettheminimumvalueof M whenthelengthofgroup T =10 ,theclassificationboundary K =2 ,andthecompactdegree d =9 . Finally,weapplythemodelwiththebestparameterstocalculate30000,100000and1000000presents,andwegetthecorresponding M valuerespectively,theseare56261,186734and1862431.Wealsoanalyzethestrengthandweaknessofourmodel. KeyWords: packingproblem; classification; compactness 1 1 Introduction Christmasiscoming,Santaneedsanoptimalloadingmode,makesthepresentascompactaspossibleandorderlyarrangedinthesledge.Thetitlegivesanevaluationonthebeststandards,wethinkitiseffective,ourobjectiveisbasedasmuchaspossibletodetermineanoptimalloadingmethod. Thisisaspacelayoutoptimizationproblems ,andissimilartotheclassiccontainerloadingproblem.Containerloadingproblemaimstodeterminetheloadingstrategyasfaraspossibletomakemaximumutilizationofthecontainerspace,solutionmethodoftenusedtohaveaconstructiveheuristicalgorithm,usinggeneticalgorithm,antcolonyalgorithm,tabusearchalgorithmandotherintelligentalgorithm.ButintheSantaClauspresentloading,wenotonlyneedtomakeapresenttheplacementspaceutilizationrateofthehighestpossible,shouldalsobepossibletomaketheplaceasfaraspossibletheorderly,theexistingmethodsarenotapplicable,weneedtohavecharacteristicsdetermineasuitablemethod. Now,wewillshowourworkinthepaper: • Wefirstestablishthreepresentplacementstrategy. • Accordingtothestrategytoestablishthecorrespondingpresentdisplaymodel. • Wecarriedoutexperimentsoneachparameterinthemodel,tofindthebestparametervalue. • Weusethemodifiedmodeltocalculatethenumberofpresentsonthesubjectaregiven,toobtaintheresult. • Weusetheresultsofanalysistodiscussthebasicplacementstrategy,andtodiscusstherationalityofdefinitionoftheoptimalindexanalysisofthegiventopic. 2 Assumptionsandinterpretation Themutualextrusionwillnotattributetothedeformationamongpresents. Inthispaper,themainpurposeistogivethebestpresentloadingmethod,consideringtheclosedegreeandorder.Themathematicaldescriptionthatpresentsproduceextrusiondeformationisverycomplex.Toestablishthemathematicalmodeltofacilitatethesolution,wethinkthatthemutualextrusionwillnotgeneratedeformation. Anypresentplacedstateisstable,thepresentwillnotcollapse. Infact,thecenterofgravitywhenthetoppresentbelowontheoutsidesurfaceofthepresent,thewholestructurewillcollapsebecauseoftheunstable.Establishtheprocesstosimplifythemodeltoreducethecomputationalcomplexity,weassumethatanarbitrarystatedisplayprocessisstable. Putanypositionisfrombottomtotop. Becauseofgravity,articlesmustbefromthebottomup,nothangingputpresents,whichismoreconsistentwiththerealsituation. Undertheaboveandbasicassumptions,wecansetouttoconstructourmodel. 3 Establishstrategyandbuildmodels 3.1 Howtoputpresents Loadingofacertainnumberofobjectstothesleigh,wemakeitascompactaspossible,andtrytomakeitorderly.Astraightforwardideaistoputsomebigsizeofthepresentsfirst,andthenputthesmallsizeintothegap.Foreachofthepresents,wecanadjusttheirattitudetofindthemostappropriateway.Eachgiftputcanstartfromthelowestplace,thiscanmakethesleighmoresmoothandmorecompact.Tothisend,weputforwardthefollowingstrategies. • Groupacertainnumberofpresents,andeachgroupbysizewithinintotwokindsofsize,largesizeinafirst,putthesmallsizesafter. Iftheidealsequencetoputcanproducemanysmallgap,notonlyreducethespaceutilization,andincreasedalotofjudgment,makethealgorithmcomplexityhasgreatlyincreased.Wecangroupfirst,classifyafter,andthenputaccordingtothestrategyofthelargesizeclassfirst,smallsizeclassafter.Thisnotonlycaneffectivelymakesuseofgaps,butalsogreatlyreducesthecomplexityofthealgorithm. WedivideeachofTpresentsintoagroup.Whenweputnpresents,thenextgroupcanbeshowedastheavailableset G { g n +1 ,g n +2 ,...,g n + T } . Throughthestatisticalanalysisforthegivenpresentssize,wecanseetheanalysisresultsasshowninFig3.1. Figure3.1:presentssizechart Fromthechart,theeachsidelengthofthemajoritypresentsislessthan 10 ,whichcanbeaboundarytodividedthemintolargesizeandsmallsize. Largesizeandsmallsizecanberespectedbytheset B and S .TheclassificationdiagramasshowninFig3.2. Figure3.2:Classificationdiagram Setthe n + k presentsoflength,widthandheight,respectively,andcanbeexpressedas u n + k , v n + k , w n + k .Thustheclassificationmethodcanbedescribedas k = T S =X g n + k ,andbecauseourmodelisrelativelyideal,computationalcomplexityistoobigthatitishardtosolve.Herewewillanalyzeafewofthemaincausesofcomputationalcomplexityandimproveourmodelforreducingthecomplexityofthecalculation. 3.3.1 Giveupsmallspace Afterthepresentputontheavailablespace,itwillbesetapartasgap1andgap2space,asshowninFig3.5.Toomuchgapwillproducealargenumberofsearchpoints,thatwillincreasessearchingcomplexityseriously. Figure3.5:Spaceisseparated Tosolvethisproblem,wecangiveupsomesmallspacetoreducethesearchingcomplexity.Soifforanyrectangularspace,theshortestedgeislessthanthegivenclosedegree d min ,itisconsideredtobenotused.Judgeexpressionasfollows: gap1(orgap2)isunavailablegap1(orgap2)isavailable 3.3.2 Howtodealwiththeunavailablespace Unavailablespace:Ifpresent g n isunabletoputintotheavailablespaceandneedtochoosethenextavailablespace,thespacebecomesunavailablespaceatthistime.whenweputintothepresent g n +1 ,wewillrestoretheunavailablespace. Dueto Min functionistosearchtheglobalminimumaltitude,youneedtotagsearchedspacenotusedtoavoidrepetition.Fuzzyproblemsexistinthechangewithunavailablespace,sowewillmakeastrategy. Figure3.6:unavailablespace ThefuzzyproblemsisshownintheFig3.6.Thedirectionofsearchingisdownandtotheright,thatcanmakethesearchpointspreadoutandproducetwospaces { S1,S2 } .IfwechangedthespaceofS1,thequantityofstatewillbataggedandS1isunabletouseatnextsearching.Toavoidthissituation,wetaketheshortestlengthofthespaceastheboundaryoftheunavailablespace.Becausetheupperlengthaislessthanthelowerlengthb,wedefineS2asunavailablespace. 4 TestingtheModel Wetake1000presentsastheresearchobject,andcountupthe3dlengthof1000presents.Wefindthatthestatisticof1000presentsissameofthe30000,100000and1000000,sowecansaythistestingismeaningful. ThecalculationflowchartisshowninFig4.1: Figure4.1:Thecalculationflowchart Forthebestanswer,weshouldtestsomeparametersofthemodel. 4.1 Parameteranalysis 4.1.1 ClassificationK Whenweresearchcategoryboundaries K influencingontheresult,weneedtoconsidertheindicatorsofdifferentscales.Inordertohighlightthechangetrendofeachindicators,theresultsafternormalizationisanalyzed.TheresultisshowninFig4.2: Figure4.2:AnalysisofparameterK Wecanseefromthefigurethat,theminimumvalueof M isobtainedat K =10 ,atthesametime,thechangeof K ontheimpactofthevariousindicators: 1. Withtheincreaseof K ,theorderofevaluationindicators σ ( p ) ,rapidgrowthandthenslowgrowth,andin K =10 ,thereistherateofchange; 2. Amaximumheightof Max z inatroughat K =10 ,afterthatheightchangeslittle; 3. M therewasaminimumvalue M =2582 inthe K =10 ,lateralongwiththechangeof K , M valueisbasicallythesame. 4.1.2 PacketlengthT Parameters T (branchlength)inthemodelinfluencetheorder,totesttheresultsof T withdifferentvalues,theresultisshowninFig4.3: Figure4.3:Analysisofparameter T Wecanseefromthefigurethat,theminimumvalueof M isobtainedat T =2 ,atthesametime,thechangeof T ontheimpactofthevariousindicators: 1. Withtheincreasingof T ,theorderofevaluationindicators σ ( p ) intolineargrowth,increasetheslopeis176.5; 2. Amaximumheightof Max z inatroughwhen T =2 ,after T 4 ,withtheincreaseof T changedlittle; 3. M valuethroughoutthechangeismainlyinfluencedbysigma(p),thereistheminimumwhen T =2 , M =2582 ,after T 5 ,withtheincreaseof T , M valuelineargrowth,growthslopewas163,slightlylessthan σ ( p ) thegrowthoftheslope. 4.1.3 Compactdegreeofd Inordertoavoidintheprocessofsolvingthesearchforunavailablespace,wegiveupsmallspace,andcompactdegreeofdinthestrategy’sinfluenceontheresultshereareanalyzing.Let T =2 and K =10 ,theresultsoftheanalysisisshowninFig4.4: Figure4.4:Analysisofparameterd Wecanseefromthefigurethat,theminimumvalueof M isobtainedat d =9 ,atthesametime,thechangeof d ontheimpactofthevariousindicators: 1. d hasnoeffectonthesizeof σ ( p ) ; 2. Amaximumheightof Max z inatroughwhen d =9 ,aftertheheightchangesgraduallyincrease; 3. M therewasaminimumvalueinthe d =9 , M =2262 ,lateralongwiththechangeof d , M valueincreasesgradually,andchangerateand Max z tendtobethesame. 4.2 Testresultsandanalysis 4.2.1 Bestparameterresult 1. Classificationboundary K =10 ; 2. Lengthofgroup T =2 ; 3. Compactness d =9 ; 4.2.2 Theanalysisoftheresults • Withtheincreaseofpacketlength T ,the M valuewillincreasequickly,whichshowsthatthelengthofthepackethasagreatinfluenceontheorder; • Withtheincreaseofclassificationboundaries K ,intheinitialtimesequenceindex σ ( P ) increasedrapidly,becausethepresentsizemostlylocatedwithin10; • Thechangeofcompactness d almosthasnoinfluenceontheorder.Itismainlytochangethespaceutilizationrate.Thereisaminimum d whichsatisfiestheoptimalspaceutilizationrate,andthatmaydecidedbythedistributioncharacteristicsofpresentsownsize. 5 Modelapplication Because1000,30000,100000and1000000presentssizehavethesamestatisticaldistribution,wecansettheparametersasthebestparametersintesting.Solutionofthespecificstepsareasfollows: Step1: Setupparametersandinputsizeandnumberofgifts T (blocklength) =2 , K (boundary) =10 , d (compactness) =9 , N =30000 Step2: Accordingtotheclassificationboundarytothegiftofclassification,getgiftplacednumber; Step3: Searchspaceandplacethegiftaccordingtothemodelofthealgorithm; Step4: calculate M ,outputtheresult. Table5.1:Result N 300001000001000000 σ ( p ) 496816553165503 Max z 25647 85090 848464 M 56261 186734 1862431 CalculatedresultstableatTab5.1 Ascanbeseenfromthetable,withthegrowthinthenumberofgifts,targetshowedabasiclineargrowth,thisfindingishelpfulforlarge-scalegiftspacelayoutoftheindexforecast. 6 StrengthandWeakness 6.1 Strength • Themodelhasacertaingeneralityandexpansibility,andcanaddtherequiredconstraintsorchangethedisplaytarget,thusobtainsthecorrespondingdisplaymethod. • Thestrategyisreasonable,andtheutilizationrateofthespaceishighaccordingtothedisplaymode. 6.2 Weakness • Thestabilityproblemintheprocessofmodeldoesnotconsider,sotheresultsaredifferentfromtheactualvalue. • Computationalcomplexityislarger,thedataprocessingtimeislong. References YuanQu,XuelianWang. Anefficientalgorithmforthreedimensionalbinpackigproblemundercomplexcondition. HoistingandConveying Machinery,2007(8):48-51. ZeshuangChen,JianmingHe. Morehybridgeneticalgorithmforunconstrainedthree-dimensionalcontainer. ModernComputer,2001(1):14-18. MartelloS,PisingerD,VigoD. Thethreepackingpmblem.OperationsResearch, 2000(48):256-267. DavidPisinger. HeuristicsfortheContainerLoadingProblem. EuropeanJournalofOperationalResearch141(2002):382-392. MichaelEley. SolvingContainerLoadingProblemsbyBlockArrangement. EuropeanJournalofOperationalResearch,141(2002):393-409. KovalyovMY,NgCT,ChengTC,etal. Singlemachineschedulingwithavariablecommonduedateandresource-dependentprocessingtimes .ComputerandOperationsResearch,2003,30:1173-1185. Appendices matlabsource: %******************************************************%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %sourceofdata:dataisderivedfromthefaculty %mainmethod:iteration %mainstepsofprogrammingandpurpose:everytimewesearchthelowest %placeandavailablearea,andtrytoputthegivenpresent.ifcan’t,we %raisetheheightofthefoundareawiththelowestheightofbordered%place,andrepeatthestepuntilpresentcanbeput. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%inputdata clear ; clc ; clf ; load presents.mat; %%parametersettings total=30000; %totalnumberofthepresentstobedelivered; L_divide=10; %Lengthofgroup; L_space=10; %Lengthoftheunavailablespace; L_group=10; %boundry num_group=total/L_divide; %numberofgroup; %%initial figure ; hold on; colormap ( jet (512)); axis equal; view ( );location= =find_min_height(lmap); =fit_block(lmap,x,len,presents(i,2:4)); ifflag ==0 if (len(1)L_space||len(2)L_space)hmap=fillmap(hmap,x,len); %discardthenarrowplacetoimprovetheefficiencyofsearching; end lmap=fillmap(lmap,x,len); %fillthetriedareatoavoidbeingfoundagain; end end hmap=renewmap(hmap,x,dem); %updatetheheightmapafterpresentsbeingput; location(i,1)=x(1);location(i,2)=x(2);location(i,3)=h; %recordthecoordinatesofpresentsput paint_block( ,dem,randi(512)); pause (0.1);count=count+1; P=P+ abs (total-count-i+1);M=P+2* max ( max (hmap)); fprintf (’i=%d,M=%d,P=%d,Hmax=%d\n’,i,M,P, max ( max (hmap))); endend for i=k*L_divide+L_divide:-1:k*L_divide+1 ifmin (presents(i,2:4))=L_group flag =0;lmap=hmap; while ( flag ==0) =find_min_height(lmap); %vispriority =fit_block(lmap,x,len,presents(i,2:4)); ifflag ==0 if (len(1)L_space||len(2)L_space)hmap=fillmap(hmap,x,len); end lmap=fillmap(lmap,x,len); end end hmap=renewmap(hmap,x,dem);location(i,1)=x(1);location(i,2)=x(2);location(i,3)=h;paint_block( ,dem,randi(512)); pause (0.1);count=count+1; P=P+ abs (total-count-i+1);M=P+2* max ( max (hmap)); fprintf (’i=%d,M=%d,P=%d,Hmax=%d\n’,i,M,P, max ( max (hmap))); end endend function paint_block(location,len,k) %****************************************% %function:paintcuboid %parameter:location:coordinate; len:sizeofpresent;k:colorparameter; %****************************************% len=len-0.001; X= ; Y= ;Z= ; surf (X,Y,Z,ones(2,2).*k); X= ; Y= ; Z= ; surf (X,Y,Z,ones(2,2).*k); Z= ; X= ;Y= ; surf (X,Y,Z,ones(2,2).*k); Z= ; X= ; Y= ; surf (X,Y,Z),ones(2,2).*k; Y= ; Z= ;X= ; surf (X,Y,Z,ones(2,2).*k); Y= ; Z= ;X= ; surf (X,Y,Z,ones(2,2).*k); function newmap=renewmap(hmap,x,presents) %******************************************% %function:updatethemapwiththegivenpresent %parameter:hmap:originalheightmap; x:thecoordinateofpresenttobe %put; presents:informationoflength,widthandheight; %******************************************% h= max ( max (hmap(x(1):x(1)+presents(1)-1,x(2):x(2)+presents(2)-1)))...+presents(3);hmap(x(1):x(1)+presents(1)-1,x(2):x(2)+presents(2)-1)=h;newmap=hmap; function =fit_block(hmap,x,len,presents) %********************************************************% %function:ifastateofplacementtoputpresentcanbefind,return %1anditsplacement;ifcan’t,return0; %parameter:hmap:originalheightmap; x:thecoordinateofpresenttobe %put; len:sizeofgivenarea;presents:informationoflength,widthand %height; %*******************************************************% flag =0; if (presents(1)presents(2))temp=presents(1);presents(1)=presents(2);presents(2)=temp; end if (presents(2)presents(3))temp=presents(2);presents(2)=presents(3);presents(3)=temp; end if (presents(1)presents(2))temp=presents(1);presents(1)=presents(2);presents(2)=temp; end dem=presents; if (presents(1)=len(1)presents(2)=len(2)) ifall (hmap(x(1):x(1)+presents(1)-1,x(2):x(2)+presents(2)-1))... =hmap(x(1),x(2)) flag =1; return ; end end if (presents(2)=len(1)presents(1)=len(2)) ifall (hmap(x(1):x(1)+presents(2)-1,x(2):x(2)+presents(1)-1))... =hmap(x(1),x(2)) flag =1;dem(1)=presents(2);dem(2)=presents(1); return ; endend if (presents(3)=len(1)presents(1)=len(2)) ifall (hmap(x(1):x(1)+presents(3)-1,x(2):x(2)+presents(1)-1))... =hmap(x(1),x(2)) flag =1;dem(1)=presents(3);dem(2)=presents(1);dem(3)=presents(2); return ; end end if (presents(1)=len(1)presents(3)=len(2)) ifall (hmap(x(1):x(1)+presents(1)-1,x(2):x(2)+presents(3)-1))... =hmap(x(1),x(2)) flag =1;dem(1)=presents(1);dem(2)=presents(3);dem(3)=presents(2); return ; end end if (presents(2)=len(1)presents(3)=len(2)) ifall (hmap(x(1):x(1)+presents(2)-1,x(2):x(2)+presents(3)-1))... =hmap(x(1),x(2)) flag =1;dem(1)=presents(2);dem(2)=presents(3);dem(3)=presents(1); return ; end end if (presents(3)=len(1)presents(2)=len(2)) ifall (hmap(x(1):x(1)+presents(3)-1,x(2):x(2)+presents(2)-1))... =hmap(x(1),x(2)) flag =1;dem(1)=presents(3);dem(2)=presents(2);dem(3)=presents(1); return ; end end function =find_min_height(map) %********************************************% %function:findthecoordinateofthelowestplaceandsearchthe %availablearea; %parameterintroduction:x:coordinate;h:lowestheight;len:sizeof %available %area; %*******************************************% = min (map); = min (a);x(2)=d;x(1)=b(d);h=c;len(1)=1;len(2)=1; while (x(1)+len(1)-1=1000map(x(1)+len(1)-1,x(2))=h)len(1)=len(1)+1; end len(1)=len(1)-1; while (x(2)+len(2)-1=1000 all (map(x(1):x(1)+len(1)-1,x(2)... +len(2)-1)=h))len(2)=len(2)+1; end len(2)=len(2)-1; function lhmap=fillmap(hmap,x,len) %*****************************************% %function:findthelowestheightofblockbordered,andfillthegiven %areatoraiseitbytheheight %parameter:hmap:originalheightmap; x:thecoordinateofpresenttobe %put; len:sizeofgivenarea; %****************************************% L=len(2); if x(1)==1x0=1; else x0=x(1)-1; end if x(1)+len(1)-1==1000x1=1000; else x1=x(1)+len(1); end if x(2)==1y0=1; else y0=x(2)-1; end if x(2)+len(2)-1==1000y1=1000; else y1=x(2)+len(2); end h=hmap(x(1),x(2))+65535; for i=x0:x1 for j=y0:y1 if hmap(i,j)˜=hmap(x(1),x(2))hmap(i,j)hh=hmap(i,j); endendend if x(1)˜=1 for i=x(2):x(2)+L-1 if hmap(x(1)-1,i)==hmap(x(1),i) L=i-x(2); break ; end endend if x(1)+len(1)-11000 for i=x(2):x(2)+L-1 if hmap(x(1)+len(1),i)==hmap(x(1)+len(1)-1,i) L=i-x(2); break ; end endend for i=x(1):x(1)+len(1)-1 for j=x(2):x(2)+L-1 if hmap(i,j)hhmap(i,j)=h; end endend lhmap=hmap;
标签: 论文
