三维装箱问题的组合启发式算法33849

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

1、一·一,·汤,,,,一刀￡蒯一一】阴渐口三维装箱问题的组合启发式算法’,’,’,’,办旺,张德富魏丽军陈青山陈火,,厦福建厦门门大学计算机科学系东南融通博士后工作站,福建厦门国防科学技术大学计算机学院,湖南长沙一胡一,,一,一,一,,,邵一,缸,····一一,一一,一,￡,,,·,,一可一匕卜,一一一,摘要通过组合拟人启发式和模拟退火算法,提出了三维装箱问题的组合启发式算法拟人启发式算法的主要思想来源于日常砌墙中的策略利用找点法以及水平和垂直参考线规则来控制装填过程用模拟退火算法改进拟人启发式经过一些数据的测试,实验结果表明,该算法能够同文献中的优秀算法竟争关键词三维装箱启

2、发式算法拟人模拟退火算法中图法分类号即文献标识码把一些箱子装入容器中是一个在工业生产中经常遇到的数学难题,比如集装箱的装箱问题对于二维装箱问且的求解算法己经研究得比较多,例如文献【一,而对于三维装箱问题的求解算法,则研究得相对较少本文研究三维装箱问题,并且假设箱子和容器都是方型的,有关不规则形状箱子的装填算法可参考文献【,并且我们不考虑箱子的重量和装填稳定性等约束条件,只是把箱子作为一个几何体,考虑其体积有约束的装载可参考文·一厦门大学院士启动基金一毛耸恤。。以犯信息科技平台资助一一一一“,,二伽,软件学报献根据目标的不同,三维装箱问题可分成以下几类一,一箱柜装载问题简称给

3、定一些不同类型的方型箱子和一些规格统一的方型容器,问题是要把所有箱子装入最少数量的容器中文献提出了该问题的一种启发式算法一一,一,容器装载问题甘面匕简称在该题中所有箱子要装入一个不限尺寸的容器中,目标是要找一个装填,使得容器体积最小,文献【给出了三维矩形块布局的序列三元组编码方法该问题更一般的形式是容器的长和宽不变,找一个装填使容器高最小,文献对该问题的不同算法进行了比较背包装载问题甘一如叩,简称一毗每个箱子有一定的价值,背包装载是选择箱子的一部分装入容器中,使得装入容器中的箱子总价值最大如果把箱子的体积作为价值,则目标转化为使容器浪费的体积最小在本文中,我们研究的求解算法

4、当箱子的长、宽分别与容器的长、宽相,问题等价于经典的背包问题因此一,,等时,是难问题对于实际应用中规模比较大的数据很难求得它的最优解因此,提出了很多针对该问题的启发式算法根据文献的分类,常用的启发式算法有砌墙算法、建堆算法、立方体排列算法和切割算法文献首次对该问题提出了砌墙算法,该算法把容器分成层,层再分成条,最终转化为一维背包问题文献川提出了按层布局的贪婪算法,针对层和条的选择策略,文献提出了基于砌墙策略的树搜索算法文献【提出了建堆启发式算法,该方法先把箱子放入合适的堆中,再通过解决一个二维装箱问题把这些堆摆放入容器中文献〔提出了立方体排列算法,通过一些立方体的排列相似箱

5、子的排列递归地填充容器文献提出了切割算法,该方法利用分治的思想,通过切割树来表示装填,每棵切割树代表把一个容器切割成小的容器,树叶代表箱子特别地,文献通过组织装填树把大空间分成小空间进行装填,最后再对剩余空间进行处理,取得了不错的效果这些算法都假定装填结果满足一定的结构,虽然简化了装填过程,但势必造成搜索解空间变小,从而导致解的质量不是很好为了改进解的质量,本文基于拟人启发式和模拟退火算法,为问题提出了一种组合启发式算法问题介绍一,,,,我们给出问题的形式化定义给定一个长方型容器和一个长方型箱子的集合⋯容器、、、一‘‘。口长宽高每个箱子有长宽和高,每个箱子的体积为令标志,分

6、别表示是否允许箱子尺寸,行作为垂直方向尺寸设为的一个子集,定义中所有箱子体积之和为,即。·‘场,问题的目标是选择的一个子集使得最大并且满足以下条件对任何箱子币在容器中对应有‘一个装填位置所有中的箱子必须全部包含在中中任何两个箱子都不重叠中箱子的方向必须与方向标志口,,口相一致定义子集对应的填充率为万拟人启发式算法,,拟人的【人们一般会先放置一块参考砖思想在解决实际问题时是很有效的”在日常砌墙时并以参考砖的高度作为基准,规定每个物体的高度都不能超过参考砖的高度,当物体不能放入时,则提高参考砖的高度受此思想的启发,我们在三维装箱过程中,在水平和垂直方向上同时引入参考砖来引导装填

7、过程我们使用了记录可放置点的方法来查找装填位置该方法与其他方法的不同之处在于并不需要装填结果满足一定的结构,这使得装填过程非常灵活,并且通过引入水平参考线和垂直参考线来引导装填过程可放我们把容器嵌入到一个三维坐标系中如图所示使其底部左上角在坐标原点,长、宽、高分别在轴按顺序考虑箱子,根据经验,当前放置的箱子必须靠住容器或者前面放置的箱子因此,我们考虑如下记录可,假设箱放入容器之放置点的方法我们用每个箱子底面左上角坐标作为其放置坐标由于箱子可旋转后沿,张德富等三维装箱问题的组合启发式算法轴上长度分别为呵,,可显然,呵