资源描述：
《a branch and cut algorithm for the pallet loading problem》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、ABranchandCutAlgorithmforthePalletLoadingProblemR.Alvarez-Valdesa,∗,F.Parre˜nob,J.M.TamaritaaUniversityofValencia,DepartmentofStatisticsandOperationsResearch,46100Burjassot,Valencia,SpainbUniversityofCastilla-LaMancha.DepartamentodeInformatica,E.PolitecnicaSuperior,CampusUniversitario,0207
2、1Albacete,SpainAbstractWeproposeabranchandcutalgorithmforthePalletLoadingProblem.The0-1formulationproposedbyBeasleyforcuttingproblemsisadaptedtotheproblem,addingnewconstraintsandnewproceduresforvariablereduction.Wethentakeadvantageoftherelationshipbetweenthisproblemandthemaximumindependent
3、setproblemtousethepartiallineardescriptionofitsassociatedpolyhedron.Finally,weexploitthespecificstructureofourproblemtodefinethesolutiongraphandtodevelopefficientseparationprocedures.WepresentcomputationalresultsforthecompletesetsCoverI(upto50boxes)andCoverII(upto100boxes).Keywords:Palletloadi
4、ng;Packing;Maximumindependentset;1IntroductionThePalletLoadingProblem(PLP)ariseswheneveridenticalrectangularboxeshavetobepackedonarectangularpallet.Thoughtheproblemisinitiallythree-dimensional,practicalconsiderationsusuallymeanthattheboxesmustbeplacedorthogonallywithrespecttotheedgesofthep
5、allet,andinlayersinwhichtheverticalorientationoftheboxesisfixed.Withtheserestrictionsthe⋆ThisworkhasbeenpartiallysupportedbytheSpanishMinistryofScienceandTechnology,DPI2002-02553∗Correspondingauthor.Emailaddresses:ramon.alvarez@uv.es(R.Alvarez-Valdes),fparreno@info-ab.uclm.es(F.Parre˜no),jo
6、se.tamarit@uv.es(J.M.Tamarit).PreprintsubmittedtoElsevierScience25thNovember2003problembecomesthetwo-dimensionalproblemofpackingalargerectangle,apallet,withthemaximumnumberofsmallidenticalrectangles,boxes.Theproblemhasmanypracticalapplicationsindistributionandlogistics.Anincreaseinthenumbe
7、rofboxeswhichcanbeshippedonapalletdirectlyleadstoadecreaseincosts.Theproblemhasthereforeattractedalotofresearchinrecentdecadesandmanyheuristicmethodshavebeendeveloped.Ontheonehand,constructivemethodsofincreasingcomplexity,fromsimplestructuresinwhichthepalletis
