Large-scalenestingofirregularpatternsusingcompactneighborhoodalgorithmS.K.Cheng,K.P.Rao*Thetypicalnestingtechniquethatiswidelyusedisthegeometricaltiltingofasinglepatternorselectedclusterstepbystepfromtheoriginalpositiontoanorientationof1808,i.e.orthogonalpacking.However,thisisablindsearchofbeststocklayoutand,geometrically,itbecomesinefcientwhenseveralpatternentitiesareinvolved.Also,itisnothighlysuitableforhandlingpatternswitharangeoforientationconstraints.Inthispaper,analgorithmisproposedwhichcombinesthecompactneighborhoodalgorithm(CNA)withthegeneticalgorithm(GA)tooptimizelarge-scalenestingprocesseswiththeconsiderationofmultipleorientationconstraints.#2000ElsevierScienceS.A.Allrightsreserved.Keywords:Cuttingstockproblem；Nesting；Compactneighborhoodalgorithm；Geneticalgorithm；Orientationconstraints1.IntroductionThecuttingstockproblemisofinteresttomanyindustrieslikegarment,paper,shipbuilding,andsheetmetalindus-tries.GilmoreandGomory7haveinitiatedtheresearchworktosolvetherectangularcuttingstockproblembyusinglinearprogramming.Fortheirregularcase,Adamowicz1attemptedtouseaheuristicapproachwhichdividestheproblemintotwosub-problems,calledclusteringandnest-ing.Clusteringistospecifyacollectionofpatternsthattwelltogetherbeforenestingontoagivenstock.Nestingofpatternsorclusterscanbebroadlydividedintotwobroadcategories,namely,small-scaleandlarge-scale.Thediffer-encebetweenthemisthelevelofduplicationoftheclusteronthegivenstock.Forsmall-scalenesting,weonlyneedtondtheinter-orientationrelationshipbetweentheselectedclusterandthegivenstock4.However,theproblembecomesmorecomplicatedforlarge-scalenestingsincetheinter-spacerelationshipbetweentheduplicatedclustersshouldalsobeconsidered.Traditionally,twobasictechni-quesarepopularlyusedforgeneratingthistypeofnesting:hexagonalapproximationandorthogonalnesting.Atypicalpattern,showninFig.1a,withbothconcaveandconvexfeatures,isselectedtoexplainthesetechniques.The*Correspondingauthor.Tel.:852-2788-8409；fax:852-2788-8423.E-mailaddress:.hk(K.P.Rao)patterncontourisplottedwiththehelpofadigitizer,asshowninFig.1b,andhasanarea(Ap)of74.44sq.units.InthehexagonalapproximationsuggestedbyDoriandBen-Bassat5,thepatternisrstapproximatedusingaconvexpolygonwhichisfurtherapproximatedbyanotherconvexpolygonwithfewernumberofentitiesuntilanhexagonalenclosureisobtained,asshowninFig.1c.Thehexagonisthenpavedonagivenstockwithnooverlappingoftheformer6.TheresultantlayoutgeneratedbyuseofthistechniqueisgiveninFig.1e.Itisreadilyevidentthatthetechniqueisnothighlyefcientduetothepoorapprox-imationperformance,especiallyinthecaseofhighlyirre-gularpatterns.Anotherproblemisthatthepatternorclustercanassumetwopositionsonly(0or1808),withnoexploita-tionorconsiderationofotherpermissiblerangeoforienta-tions.Inthesecondtechnique,usedbyNee9,thenestingprocessisachievedbyapproximatingasinglepattern/clusterbyarectangleasshowninFig.1d.Thisrectangleisthenduplicatedinanorthogonalway,resultinginthelayoutshowninFig.1f.Thistechniquecanbeeasilyappliedwhenthereareno-orpartial-orientationconstraints,i.e.thesinglepatternorclustercanrotatewithinacertainrangewhilettingitonthestock.Likethehexagonalapproximation,themaindisadvantageofthisapproachisthatthealgorithmsperformanceishighlydependentontheshapeofpatterns.Moreover,inthecaseofmultipleorientationconstraints,the0924-0136/00/$seefrontmatter#2000ElsevierScienceS.A.Allrightsreserved.PII:S0924-0136(00)00402-7136S.K.Cheng,K.P.Rao/JournalofMaterialsProcessingTechnology103(2000)135140Fig.1.(a)ThechosenatpatternfordemonstratingtheworkingprincipleofCNAalgorithm；(b)patterncontourobtainedbydigitizer；(c)hexagonalapproximation；(d)orthogonalapproximation；(e)layoutgeneratedbyusinghexagonalapproximationyieldingastockutilizationof60.05%；(f)layoutgeneratedbyusingorthogonalapproximationyieldingastockutilizationof67.14%；and(g)layoutgeneratedbyusingCNAyieldingastockutilizationof74.10%.timetakentoestimateasuitablerotationangleforthepatternsisalwaysmuchlonger.Inordertoincreasetheaccuracyandspeedofnesting,ChengandRao4proposedacompactneighborhoodalgorithm(CNA)thatconsiderstherelationshipbetweenthenumberofneighborsandthesharingspacebetweenthem.Fig.1gshowsatypicallayoutgeneratedusingCNAwhichnormallyyieldshigherpackingdensitywhencom-paredwiththeorthogonalandhexagonalapproximations.However,CNA,initspresentform,hasbeenmainlydesig-natedfornestingofpatternswiththeconsiderationoffullorientationconstraints,andisnotidealforsituationswheremorefreedomisavailableintheorientationofpatterns.ThisstudyisaimedatimprovingtheexibilityofCNAbyincorporatingtheavailablefreedomintheorientationofpatternsandageneticalgorithm(GA)thatfollowsnaturalrulestooptimizethegeneratedlayouts.ThenewtechniqueistranslatedintoacomputerprogramwritteninCobject-orientedlanguage.Thenewalgorithmcanhandletheproblemofnestingtwo-dimensionalatpatternsofanyshapecontaininglinesegmentsandarcs.Withthehelpofatypicalexample,theenhancedcapabilitiesofCNAandtheassociatedcomputerprogramwillbedemonstratedinthispaper.2.Descriptionofcompactneighborhoodalgorithm(CNA)ACNA4tracksthecharacteristicsoftheevolvingneighborhoodswhenthepatternsaremovedtoformdifferentarrangements,assummarizedschematicallyinFig.2ac.Asthesheardisplacementincreases,theupperandlowerneighborstendtocollapseduetothechangeincrystallizationdirections.Finally,amostcompactstructureandanumericalvalueformaterialyield,calleduniversalcompactutilization(UCU),canbeobtained.NomatterFig.2.Typicalneighborhoodstructuresforcircularpatterns(a)formationoforthogonalpackingunitcellwithNn8andApu16r2；(b)shearingoflayersleadingtoshearedorthogonalpacking；and(c)bestcompactstructurewithhexagonalpackingunitcellwithNn6andAu63r2,whereAuistheareaofaunitcell,rtheradiusofcircularpatternandNnisthenumberofneighborstoconstructtheunitcell.S.K.Cheng,K.P.Rao/JournalofMaterialsProcessingTechnology103(2000)135140137Fig.3.(a)Stepsinvolvedinthegenerationofself-slidingpathtocreateaneighborhood；and(b)optimalneighborhoodstructurewithhexagonalpackingunitcellwithaUCUof83.07%.whetherthepatterncanberotatedornot,UCUindicatestheupperlimitofyieldthatmaybepossiblewithanychosenstockandhencecanberegardedasanindexforstoppingcriteriainthenestingprocess.Themainstepsinvolvedinndingthecompactneighbor-hoodare:(1)generatingaself-slidingpathorano-t-polygon(NFP)1,asshowninFig.3a,whichguidestherelativemovementbetweentwopatternswiththeconsidera-tionofnooverlapping；and(2)deningthecrystallizationdirections,asshowninFig.3b,thatprovideessentialdataforbuildingthewholeneighborhoodbyllingthegivenstockduringlarge-scalenesting.3.Proposedalgorithmforlarge-scalenestingTheproposedtechniquesofenhancingthecapabilitiesofCNAbytakingadvantageofageneticalgorithmaredealtinthissection.Aatpatterncanbedividedintoentitiesoflinesegmentsandarcs.Polygonalrepresentationmethods2expandthisstructuretolltheentirestock.Fornestingofpatternswithfullorientationconstraint,itisonlynecessarytodecideanestingvectorCDnthatdeneswheretheneighborhoodshouldbetranslatedaroundthegivenstock.However,inthecaseofnestingofpatternswithlimitedornoorientationlimitations,theproblembecomesmorecompli-catedduetoanincreaseinthepossiblecombinationsthatweneedtoconsider.Inthiscase,therststepwhichisglobalwithorwithoutorientationlimitationsistotranslatetheneighborhoodtoanarbitrarypositioninsidethegivenstock,i.e.deningavectorCDn.Afterward,anestingangleynistobedeterminedsothatagoodorientationisselectedfortheneighborhoodtogrow.Alltherequiredgeometricalopera-tionsaresummarizedinFig.4.ItiscriticaltooptimizeCDnandynwhichcannallyleadtoamostcompactneighborhoodstructure.Itisbelievedthattherearenouniquemathematicalstepstocalculatetheseparametersforanytypeofstock.Inaddition,wecannotacceptanexhaustivesearchbecauseoftheconstraintsposedoncomputationtime,especiallyinthecaseofnestingofpatternswithtoolongacomputationtime,especiallywhilenestingpatternswithmanyentitiesandconcavefeatures.Hence,inthisstudy,arecentpopularoptimizationtechni-que,calledGA,isapplied.Themainprincipleisprovidedinthefollowingsection.3.2.GAforoptimizinglayoutsGA8maintainsapopulationofcandidateproblemsolutions.Basedontheirperformance,thettestofthesesolutionsnotonlysurvive,and,analogoustosexualrepro-duction,exchangeinformationwithothercandidatestoformanewgeneration.Beforestartinganygeneticoperation,oneneedstodenethetnessfunctionandthecodingmethod.Asmentionedearlier,thegoalinnestingofpatternsistoreducethescrapbyttingtheclusterstogethersothattheyoccupyaminimumarea.Torepresentthecompactnessofaparticularlayout,onecanbecondentthatthemostdirectwayistorelateitwiththestockyieldfxYypy(1)canbeusedtorepresentbothconcaveandconvexarcsassetsofstraightlines.Theactualnumberoflinesisdependentontherequiredaccuracylevel.Also,clearanceoroffsetgen-erationisanessentialstepthatcontributestowardsthesuccessofCAD/CAMtechnology.Analgorithmtogeneratetherequiredoffset,calledthreepointislandtracing(TPIT)technique2,isincorporatedinthepresentnestingsystem.3.1.CNAforlarge-scalenestingIntheprevioussection,wehavealreadymentionedthebasicstepsinvolvedinobtainingthebestcompactneighbor-hood,asshowninFig.3b.Ournextconcernisthedetermi-nationofthebestpositiontoplacetherstpatternandxwherexistheareaofthegivenstockandythetotalareaofthepatternsthatcouldbecutoutfromthegivenstock.Codingcandirectlyandindirectlyinuencetheoptimi-zationprocess.Thisisbecauseourmainconcernishowtoxthetranslationposition(i.e.nestingvectorCDn)andthedegreeofrotation(i.e.nestingangleyn).Theyarethusselectedasthecodingparametersthatguidetheproperties(i.e.correspondingtonaturalchromosomes)forexchangeinthegeneticoperatorsofcross-overandmutation.3.3.ThegeneticoperatorsAsproposedbyHollandetal.8,theGAaimsatoptimizingthesolutionbymimickingnaturesevolutionary138S.K.Cheng,K.P.Rao/JournalofMaterialsProcessingTechnology103(2000)135140Fig.4.Translationoftheneighborhoodtoapre-denedpositionwithnestingvectorCDcess.LikehumanbeingsatypicalGAcontainsthefollowinggeneticoperators.3.3.1.InitializationAtthebeginning,a