基于禁忌算法的二维装箱问题研究

【摘 要】装箱问题是计算机科学领域最原始的基础问题之一，在多个研究领域内盛行，诸如组合优化。装箱问题的研究使得近似度分析和对手分析策略得到发展，对计算机科学的发展有巨大的推动作用。在计算机领域的多处理器调度，内存分配和工业领域的任务调度，切割存储及其装载卡车问题上都有着广泛的应用。本文提出了求解大型二维装箱问题的禁忌算法。算法基于自然数编码并根据邻域的不同，构造了两种禁忌表，设计了货物的摆放规则和序列生成方式。算法采用惩罚函数处理空间利用率约束，最后给出了具有代表性算例试验结果并且进行了分析。

【关键词】装箱 禁忌算法 问题研究

一、引言

装箱问题作为最原始的NP难问题之一，其研究始于20世纪70年代，影响至今。装箱问题还有着极为广泛的实际应用研究背景，涉及到工业领域，计算机应用科学领域，物流行业及其日常生活领域等多方面。

二、装箱问题定义及描述

大型2BP问题的实际应用中，一般含有多种尺寸型号，而每种尺寸型号又含有多个同尺寸的物体.故本文大型2BP问题可描述如下：公司现有N 个尺寸型号的矩形物体（以后简称货物） ， 每个型号货物的宽、高分别为wi ， hi （wi ≤hi ） ，每个型号货物数量分别为ni个. 要把这些物体放入宽、高分别为W， H （W ≤H） 的矩形箱，且单个矩形箱的空间利用率要大于D %. 求选用最小的矩形箱个数的装载方案.

三、求解禁忌算法设计

（一）货物摆放方位及解的编码设计

2BP问题涉及到货物宽、高两个方向，因此每一货物有2种摆放方式，对应矩形箱的宽高W， H，货物摆放方位分别为：wi、hi ， hi、wi ， 可用编码0、1表示.

本文解的结构由以下两部分组成：编号和方位.

1.货物的编号：用自然数表示，不同编号的物体可能是同种型号（尺寸） ；

2.货物的方位：即放置的货物方位，用0、1表示.

（二）货物摆放规则

把矩形箱左下点定义为基点，货物从基点开始按一定次序放置. 货物与矩形箱、货物与货物之间边线的左下相交点称为潜在放置点.A 点为基点， B、C、D为潜在放置点.对于解（ i1 ， i2 ，… ， in ， - j1 ， j2 ， …， jn ），货物的摆放规则为：

1. 置k： = 0；

2. k： = k + 1，如果k > n，转6；

3. 对于物体ik，判断当前矩形箱是否还能按方位jk放置该货物，能则转5，否则继续；

4. 增加一新矩形箱，确定新基点；

5. 把ik 按方位jk 放入所有潜在放置点，比较ik 与货物或者矩形箱的接触线aj与 bj的大小，选择该值最大的潜在放置点摆放ik ， 转2；

6. 结束

（三）初始化

产生初始解步骤为：

1. 随机在区间（0， 0. 5）之间取随机数a，将所有货物按值a*wi + （1 - a）*wihi降序排列，得到序列SH ；初始化i = 0； j = 0；

2.判断SH 是否为空，是则转10；否则继续；

3.j： = j + 1；

4. 取新矩形箱j；

5.i： = i + 1；

6. 如果SH 中i已经移出，转5；

7. 按0方位在j箱放置货物i，如果j箱空间不足，不能按0方位放置i，继续；否则将i从SH 中移去，转5；

8.按1方位在j箱放置货物i，将i从SH 中移去，转5；否则继续；

9.在SH 中i后面的货物分别按0、1方位放置，如果找到能放入当前层的货物k，则按既定方位放置，将k从SH 中移去， i： = k， 转5 ；否则转3；

10.结束算法.

（四）利用率最小的矩形箱货物移入、移出操作

每经过一次货物序列更新邻域或者货物摆放方位变化邻域操作，选用的矩形箱会出现剩余空间或者剩余货物. 出现剩余空间是因为经过邻域操作得到了更好的摆放序列或者摆放方位，反之会出现剩余货物.

（五）禁忌表的设计和终止准则

本文设计的两种邻域是针对不同对象（货物序列和单个货物）进行的操作，故构造了与之相对应的两个禁忌表，分别为货物序列禁忌表和货物方位禁忌表.货物序列禁忌表. 即对序列调整系数a按步长ξ进行操作，如果当前代对a进行了增加ξ的操作，那么在接下来的ηx 代内，不允许对a进行减小ξ的操作； 货物方位禁忌表. 即如果当前代对货物i进行了方位取反操作，那么在接下来的ηH 代内，不允许再对货物i进行方位取反操作.终止准则. 如果连续迭代ND 代最优解没有变化，则算法终止.

四、禁忌算法优化大型二维装箱问题关键步骤

禁忌算法优化多箱型二维装箱问题详细步骤为：

1.初始化各参数，产生初始解，搜索循环次数i = 0；

2.i： = i + 1；

3.货物摆放方位变化邻域，货物序列更新邻域操作；

4.禁忌表及特赦准则处理；

5.满足终止条件，转6；否则转2；

6.结束.

五、算例分析

把Martello算例产生程序稍加修改，增加wi ≤ hi 限制，产生一组数据. 货物型号分为25种，每种型号宽度wi在区间（0. 5， 5）中随机产生，高度hi在区间（2， 10） 中随机产生，且wi ≤ hi ，每种货物型号的数量在区间（50， 150） 之间产生，总共产生2239个货物. W = 50， H = 70， D% = 85%.用C语言实现大型二维装箱问题的禁忌算法， 取禁忌算法参数ξ = 0. 02，ηX = 30，ηH = 4，ND = 200， NX = 20. 在PⅣ2. 0机型上计算20次，以100%概率收敛到本算法所能得到的最优解值为13 （各解的货物排列序列不完全相同） ，总空间利用率达到93. 7% ，平均收敛时间仅为1分26秒. 从算法的计算效率方面分析是有效的.

六、结论

本文对大型二维装箱问题进行了描述，提出了求解该问题的禁忌算法，介绍了算法的原理，并通过算例结果及其分析证明了此算法的有效性. 用本文提出的禁忌算法能优化规模较大的二维装箱问题，速度较快，运算过程及结果稳定，具有较强的实际应用价值。