搜索
NFP,,200030:NFP,,NFP()NFP,NFPNFP,NFP,,,,:;;NFP;;:TP391:1004132X(2007)060723042DIrregularNestingAlgorithmBasedonGravityCenterNFPLiuHuyaoHeYuanjunShanghaiJiaotongUniversity,Shanghai,200030Abstract:Thispaperproposed2DirregularshapednestingalgorithmbasedongravitycenterNFP.Theproblemsofpolygonstouchingdetectionandoptimumnestingpositionselectionwerere2solvedherein.Allcontainerregionandpieceswererepresentedaspolygons,andthetouchingposi2tionscanbefoundbycalculationofNFP.Inordertogettheoptimalnestingposition,thispaperpro2posedtheconceptofgravitycenterNFP.ThelowestvertexongravitycenterNFPwasselectedtonestthepieces.Fortheproblemofcalculationnestingsequence,thispaperpresentedarecursivenest2ingalgorithmandageneticalgorithmtoreducethewastedarea.Theproposedalgorithmcandealwithirregularshapedpiecesandcontainer,itcanalsodealwitharbitraryrotationofpartsandholesoncon2tainerregion.Keywords:irregularnesting;nofitpolygon(NFP);gravitycenterNFP;recursivenesting;geneticalgorithm:20051212:(60573146)0,,:;;,,,,,,,,,,,:,(NFP),,,,,,[1,2],Fujita[3]327NFP,Ja2kobs[4],,,,Hopper[1][5,6],,,[7],,:;O(n2),,,,,(),NFP,NFPNFP,,1,(nofitpolygon,NFP)NFP,,:,,,,()(1),,:[8]1(minkowskisum)[9]NFP,NFPNFP2,,,,,,,[10],,NFP,NFP,NFP,22NFP,,,,NFP,NFP42718620073,,,,(),NFP,NFP,NFPNFP,,,,33NFP,,10,360/10=36NFP,,,3NFP,,,,,,,,,,,,3.1,,,,,,:,,,,,,,4,1,,,2,21,321231,231,21,12123,43.2,,OX,3.2.1(3),,,3.2.2527NFP,3.2.3,:f=f++,f;f=favgfavg-fmin=-fminfavgfavg-fmin=favgK,K;favg;fmin,,,3.2.4OX(order-crossover)2,2(5,2,3,7,6,1,4),(4,6,2,1,3,5,7),23,(4,6,3,7,2,1,5)(5,3,2,1,7,6,4)3.2.5,0110122(2),,44.11[4],,,,,[4](:P4115G,640M),14.22ESICUP(EUROspecialinterestgrouponcuttingandpacking),,,55NFP,:NFP,NFP;,NFP,,5(55.06mm,81.4%,93.9s),,,,,,(731)627186200736.48k=2|A(k)|=66,P=5617%7,,,,,,:[1],,,.[J].(),2004,34(5):9O13.[2],,.Petri[J].,2000,11(9):1007O1009.[3].[M].:,2005.[4]PavlovVV,,,.[J].,2001,35(11):1208O1210.[5]PavlovVV.TheoreticalBaseofAssemblyforAir2planeandWhirlybird[M].Moscow:MAIPress,1993.[6],,,.[J].,2003,43(8):1046O1048.[7],,,.[J].,2005,39(11):1254O1258.[8],,.[J].-CIMS,2002,8(7):575O579.():,,19805,,1946,,1979(726),,80%,:[1]HopperE,TurtonH.AReviewoftheApplicationofMeta-heuristicAlgorithmsto2DStripPackingProblems[J].ArtificialIntelligenceReview,2001,16:257O300.[2]KathrynAD,WilliamBD.SolutionApproachestoIrregularNestingProblems[J].EuropeanJournalofOperationalResearch,1995,84:506O521.[3]FujitaK,AkagjiS,KirokawaN.HybridApproachforOptimalNestingusingAGeneticAlgorithmandALocalMinimizationAlgorithm[C]//InProceed2ingsofthe19thAnnualASMEDesignAutomationConference.Albuquerque,NM,USA,1993:477O484.[4]JakobsS.OnGeneticAlgorithmsforthePackingofPolygons[J].EuropeanJournalofOperationalRe2search,1996,88:165O181.[5]FischerAD,DagliH.EmployingSubgroupEvolu2tionforIrregular-shapeNesting[J].JournalofIn2telligentManufacturing,2004,15(2):187O199.[6]FrancisE,TayH,ChongTY,etal.PatternNest2ingonIrregular-shapedStockusingGeneticAlgo2rithms[J].EngineeringApplicationsofArtificialIntelligence,2002,15(6):551O558.[7],,.[J].,2005,16(02):316O232.[8],,.[J].,2000,12(7):488O491.[9]JuliaAB,KathrynAD,WilliamBD.TheIrregu2larCutting-stockProblem-ANewProcedureforDerivingtheNo-fitPolygon[J].Computer&Op2erationsResearch,2001,28:271O287.[10]RogerBG,TomMC.ANewAlgorithmfortheMinimal-areaConvexEnclosureProblem[J].Eu2ropeanJournalofOperationalResearch,1995,84:522O538.():,,19778,,1945137