欢迎来到天天文库
浏览记录
ID:38991656
大小:253.68 KB
页数:4页
时间:2019-06-23
《三维装箱问题的智能启发式算法》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、万方数据第29卷第3期2009年6月中南林业科技大学学报JournalofCentralSouthUniversityofForestry&TechnologyVoI.29NO.3Jun.2009文章编号:1673—923X(2009)03--0134一04三维装箱问题的智能启发式算法陈德良1’2,陈治亚1(1.中南大学交通运输工程学院,湖南长沙410075I2.中南林业科技大学物流学院,湖南长沙410004)摘要:三维装箱问题是一类典型的NP—hard组合优化问题.找到一个高效快速的算法具有重要的现实意义.模
2、拟人们在实际装箱时总是尽量保证每一层装的比较“平直”思想,设计了一种智能启发式算法,借以克服一般启发式算法依赖“经验”的不足.给出了详细算法流程和关键数组的定义.该算法结构简单,实验表明算法收敛速度快,能有效解决三维装箱问题.关键词:物漉工程I三维装箱}启发式算法;智能启发式中图分类号:U169.61文献标志码:AAnIntelligentHeuristicApproachtoThree-DimensionalBin-packingProblemCHENDe—lian91“.CHENZhi—yal(1.Scho
3、olofTraffic&TransportationEngineering。CentralSouthUniversity·Changsha410075,Hunan,China;2.SchoolofLogistics。CentralSouthUniversityofForestry&Technology,Changsha410004,Hunan,China)Abstract:Thethree—dimensionalbin-packingproblemisveryhardtOsolvebutthereisahigh
4、levelofinterestindevelopinganeffectivewaytOsolvethisitinordertoreducethetime.energyandotherresourcesspentinbinpacking.ThispaperdevelopsapowerfulintelligentapproachtOitssolution.imitatinghumanintelligencetopackbinsstraightandflatasfaraspossible.Thisapproachis
5、ofsimplestructureandovercomesthedeficiencyingeneralheuristicalgorithmsdependingonprivateexperience.Thepaperalsoprovidesadetailedalgorithmprocessandkeydefinitionsofthearray.Testsonsuchproblemsshowthatourapproachmakesthemostofvolumeutilization.Keywords:logisti
6、csengineering;three·-dimensionalbin--packingproblem;heuristicalgorithm;intelligentheuristic装箱问题(BinPackingProblem)是一典型的组合优化问题.由于需要考虑维数、形状、约束、目标等不同因素,从计算复杂性来说,装箱问题是NP—hard难题[1].装箱问题在现实生活中具有广泛的应用,如计算机领域中的多处理器的任务调度、内存分配等.特别在现代物流中,很多问题都可以抽象化为装箱问题或装箱问题的变形,如车辆如何装车
7、,才能充分利用车辆.到目前为止,人们对装箱问题提出了许多算法【2一],但都有明显不足:穷举法在箱子数目稍大时就存在“组合爆炸”;而一般的启发式算法引入的启发信息依赖于个人经验,并且同样存在“组合爆炸”;神经网络方法在解决装箱问题时效果明显,但它收敛速度慢,易陷入局部极优.因此,找到一个高效快速的算法具有重要的现实意义.装箱问题的数学模型考虑三维装箱问题,即:给定长方体箱子B(D,W,日),D、W、H分别为箱子的三维尺寸,以及T1个长方体物品m正(dJ,甜』,hs)l歹∈{1,2,⋯,理}],其中西、硼J、h』分
8、别为物品的尺寸.问题是选择其中的一些物品装入箱子中,使箱子的空间利用率最大.装人时任一物品的摆放方向与箱子的三维保持正交(称为正交摆放),即物品的三方向的中轴线与箱子的三条中轴线保持平行.另外假设所有物品的最小尺寸不大于箱子的最大尺寸,收稿日期:2008.09—01基金项目:中南林业科技大学青年科学基金资助(2006年重点项目)}湖南省自然科学基金(07JJ3134).作者简介:陈德良
此文档下载收益归作者所有