三维装箱问题的智能启发式算法

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

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)．作者简介：陈德良