一种求解集装箱装载问题的启发式算法

《一种求解集装箱装载问题的启发式算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机科学2008Vol135№18　一种求解集装箱装载问题的启发式算法3)1　黄文奇2　尚明生1　傅　彦1陈端兵(电子科技大学计算机学院　成都610054)1　(华中科技大学计算机学院　武汉430074)2　摘　要　所谓集装箱装载问题,就是将若干大小不同的长方体盒子装进一个大小已知的长方体容器,其目标是最大化容器的积载率。对这一问题,国内外学者利用不同的哲学思想,提出了诸如遗传算法、模拟退火算法等求解算法。本文提出一种求解此问题的基于最大穴度优先原则的启发式算法。算法中使用了两个重要的策略:最大穴度原则和最小边度原则。用一些公开的算例对算法性能进行了实算测试,

2、测试结果表明:算法所得结果的容器积载率高,是求解集装箱装载问题的有效算法。关键词　Packing问题,集装箱装载,启发式算法,穴度,边度　HeuristicAlgorithmforSolvingtheContainerLoadingProblemCHENDuan2bing1　HUANGWen2qi2　SHANGMing2sheng1　FUYan1(SchoolofComputerScience,UniversityofElectronicScienceandTechnologyofChina,Chengdu610054,China)1(SchoolofCompu

3、terScience,HuazhongUniversityofScienceandTechnology,Wuhan430074,China)2　Abstract　Thecontainerloadingproblemistheproblemofloadingaseriesofboxeswithdifferentsizesintoafixedcu2 boidcontainer.Theobjectiveistomaximizethevolumeutilizationofthecontainer.Researchersproposemanyalgo2 rithmssuc

4、hasgeneticalgorithmandsimulatedannealingtosolveitbasedondifferentidea.Thispaperpresentsaheu2risticalgorithmbasedonmaximumcavingdegreefirstprincipleforsolvingthisproblem.Twoimportantstrategiesareconsideredinthealgorithmproposed.Oneisthemaximumcavingdegreeprinciple,theotheristheminimum

5、edgede2greeprinciple.Theperformanceofthealgorithmisevaluatedbysomepublictestproblems.Highvolumeutilizationisobtainedbyrunningthealgorithm.Experimentalresultsdemonstratethatthealgorithmproposedisfairlyefficientforsolvingthecontainerloadingproblem.Keywords　Packingproblems,Containerload

6、ing,Heuristicalgorithm,Cavingdegree,Edgedegree　1　引言和Bortfeldt提出了求解此问题的并行遗传算法[10],Bortfeldt等提出了并行禁忌搜索算法[11]。2002年,Pisinger在泥瓦工集装箱装载问题就是将若干大小不同的长方体盒子装进砌墙的实践基础上提出了一种新的启发式算法[12]。2007年,一个大小已知的长方体容器。通常情况下,优化的目标是最杨德荣和杨超提出了求解三维装箱布局的单向寻优搜索算大化容器的装载效率,即最大化容器的积载率。在货运码头、法,并对两个典型算例进行了实算[13]。物流、仓储等

7、工作中均牵涉到这一问题。本文在最大穴度优先的基础上,提出了一种求解集装箱集装箱装载问题属于NP难问题[1],因而求解此问题的装载问题的启发式算法,其优化目标是最大化容器的积载率。算法大多是启发式算法。国内外学者利用不同的哲学思想提出了许多启发式算法,如Loh和Nee[2],Bischoff和Rat2算法中使用了两个重要的策略。第一个策略就是放进容器的盒子始终占据一个角,甚至占穴,这一策略是文[14216]的一cliff[3],许光泞和俞金寿[4],等等。个发展和提高。另一个策略是即将放进容器的盒子和其它已近年来,国内外许多学者都在致力于集装箱装载问题求放进容器的

8、盒子所形成的棱的数量要尽