大型二维装箱问题及其禁忌算法研究

维普资讯 http://www.cqvip.com ２００７年９月　安徽火学学报（自然科学版）　Ｓｅｐｔｅｍｂｅｒ　２００７　第３１卷第５期　Ｊｏｕｒｎａｌ　ｏｆ　Ａｎｈｕｉ　Ｕｎｉｖｅｒｓｉｔｙ　Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ　Ｖｏ１．３１　Ｎｏ．５　大型二维装箱问题及其禁忌算法研究　屈援　＇　王雪莲　（１．天津大学管理学院，天津３０００７２；２．暨南大学管理学院，广东广州　５１０６３２）　摘要：对大型二维装箱问题进行描述，提出求解该问题的禁忌算法．算法基于自然数编码，设计了　货物的摆放规则和序列生成方式，采用二种邻域，根据邻域的不同，构造了两种禁忌表．算法采用惩罚函　数处理空间利用率约束．介绍算法的原理，给ｍ了具有代表性算例试验结果并且进行了分析．试验结果　表明了提出的禁忌算法对优化大型二维装箱问题的有效性．　关键词：装箱问题；二维；禁忌算法　中图分类号：ＴＰ３９３　文献标识码：Ａ　文章编号：１０００—２１６２（２００７）０５—００３２—０４　装箱问题（Ｂｉｎ　Ｐａｃｋｉｎｇ　Ｐｒｏｂｌｅｍ，简称ＢＰ）是运筹学领域一个经典问题．二维装箱问题（Ｔｗｏ—　Ｄｉｍｅｎｓｉｏｎａｌ　Ｂｉｎ　Ｐａｃｋｉｎｇ　Ｐｒｏｂｌｅｍ，简称２ＢＰ）即为物体在二维空间的摆放优化问题，可以描述为：宽、高分　别为１２）　，ｈ　的ｎ个矩形物体在多个尺寸相同的矩形箱中摆放，在满足一定的约束（重量约束、空间利用率　约束）条件下，使使用的矩形箱数量最少．二维装箱问题有很强的应用价值，在运输优化以及木材、玻　璃、布料、纸张切割等领域有着广阔的应用前景．　对于二维装箱问题是ＮＰ—ｈａｒｄ问题ｌ１　Ｊ，如果用传统算法求解，复杂度随摆放物体数量的增加而呈　指数规律增长，因此很难在实际生活中得到应用．目前，国内外很多学者都应用现代启发式算法对装箱　问题进行研究，代表人物有Ｌｏｄｉ，Ｍａｒｔｅｌｌｏ，Ｖｉｇｏ，Ｐｉｓｉｎｇｅｒ，Ｃｏｆｆｍａｎ，Ｄｏｗｓｌａｎｄ等　Ｉ４ｊ．在目前所能查找　到的文献中，很少有大型（ｎ≥１０００）二维装箱问题的研究成果．实际应用中，例如，对纸张、布料的裁　剪，规模往往很大，要根据情况进行优化，减少材料浪费．在本文中，作者将对大型二维装箱问题进行研　究，并且提出一种禁忌算法来对该问题进行优化，给出了算法设计过程和算例的优化结果．　１　问题描述　大型２ＢＰ问题的实际应用中，一般含有多种尺寸型号，而每种尺寸型号又含有多个同尺寸的物体．　故本文大型２ＢＰ问题可描述如下：公司现有』ｖ个尺寸型号的矩形物体（以后简称货物），每个型号货物　的宽、高分别为１２）　，ｈ　（１２）　≤ｈ　），每个型号货物数量分别为ｎ　个．要把这些物体放人宽、高分别为　，日（Ｗ≤　日）的矩形箱，且单个矩形箱的空间利用率要大于Ｄ％．求选用最小的矩形箱个数的装载方案．　２　大型二维装箱问题禁忌算法设计　２．１　货物摆放方位和解的编码设计　２ＢＰ问题涉及到货物宽、高两个方向，因此每一货物有２种摆放方式，对应矩形箱的宽高　，日，货物　摆放方位分别为：１２）　、ｈ　，ｈ　、１２）　，可用编码０、１表示．　本文解的结构由以下两部分组成：编号和方位．　（１）货物的编号：用自然数表示，不同编号的物体可能是同种型号（尺寸）；　（２）货物的方位：即放置的货物方位，用０、１表示．　２．２货物的摆放规则　如图１所示，把矩形箱左下点定义为基点，货物从基点开始按一定次序放置．货物与矩形箱、货物与　收稿日期：２００７—０４—１３　作者简介：屈援（１９６５一），女，江苏常熟人，暨南大学副教授，天津大学博士研究生　维普资讯 http://www.cqvip.com 第５期　屈　援，等：大型二维装箱问题及其禁忌算法研究　货物之间边线的左下相交点称为潜在放置点．图１中，　点为基点，Ｂ、ｃ、Ｄ为潜在放置点．　对于解（ｉ　，ｉ：，…，ｉ　，一　，…，　），货物的摆放规则为：　（１）置ｊ｝：＝０；　（２）ｋ：＝ｋ＋１，如果ｋ＞ｎ，转（６）；　（３）对于物体ｉ　，判断当前矩形箱是否还能按方位＾放置该货物，能则转（５），否则继续；　（４）增加一新矩形箱，确定新基点；　（５）把ｉ　按方位　放人所有潜在放置点，比较　与货物或者矩形箱的接触线ａｊ　ｂｊ的大小，选择该　值最大的潜在放置点摆放ｉ　，转（２）；　（６）结束．　图１货物摆放规则　２．３初始解的产生　产生初始解步骤为：　（１）随机在区间（０，０．５）之间取随机数ａ，将所有货物按值ａ　ｗ　＋（１一ａ）　ｗ　ｈ　降序排列，得到序　列ＳⅣ；初始化ｉ＝０；　＝０；　（２）判断　是否为空，是则转１０；否则继续；　（３）　：＝　＋１；　（４）取新矩形箱．　；　（５）ｉ：＝ｉ＋１；　（６）如果Ｓ　中ｉ已经移出，转（５）；　（７）按０方位在　箱放置货物ｉ，如果　箱空间不足，不能按０方位放置ｉ，继续；否则将ｉ从　中移去，　转（５）；　（８）按１方位在　箱放置货物ｉ，将ｉ从ｓ　中移去，转（５）；否则继续；　（９）在ｓ　中ｉ后面的货物分别按０、１方位放置，如果找到能放人当前层的货物ｋ，则按既定方位放　置，将ｋ从ｓ　中移去，ｉ：＝ｋ，转（５）；否则转（３）；　（１０）结束算法．　２．４邻域的操作　设计两种邻域：一种为货物序列更新邻域，另一种为货物摆放方位变化邻域．　２．４．１　货物序列更新邻域　生成初始解时，货物序列首先按值ａ　ｗ　＋（１一ａ）　ｗ　ｈ　（ａ为随机数）降序排列，然后在货物的摆　放过程中根据摆放规则进行了小幅调整（即如果矩形箱空间不够，则改变方位或者重新选择货物）．货　物序列更新邻域就是对每个矩形箱的货物序列进行更新，搜索更好的摆放序列．定义摆放序列函数　『口　Ｗ　＋（１一口）　ｌｉｈ　，摆放方位为０　【ａ　ｆ　＋（１一ａ）　ｗ　ｈ　，摆放方位为１　其中ａ为序列调整系数，且０≤ａ≤１．对ａ进行调整，能够改变矩形箱中货物的摆放序列．当ａ＝０时，　完全按　面积值进行降序排列；当口＝１时，完全按宽度值Ｗ　进行降序排列．取步长　，每次　的变化　维普资讯 http://www.cqvip.com 安徽大学学报（自然科学版）　第３１卷　值为‘　，进而对摆放序列进行调整．　２．４．２货物摆放方位变化邻域　　．生成初始解时，摆放的货物已经有了初始方位，对该方位改变，进而对矩形箱中货物的摆放进行调　整．对于２个摆放方位的装箱问题，邻域操作对选中的货物当前方位取反即可．　２．５利用率最小的矩形箱货物移入、移出操作　每经过一次货物序列更新邻域或者货物摆放方位变化邻域操作，选用的矩形箱会出现剩余空间或　者剩余货物．出现剩余空问是因为经过邻域操作得到了更好的摆放序列或者摆放方位，反之会出现剩余　货物．所以，邻域操作过后要把利用率最小的矩形箱ｉ作为缓冲：当出现剩余空问时，把ｉ中货物按ｉ中序　列和方位放人其他Ｉ叶Ｉ现剩余空间的矩形箱中（如果出现ｉ中为空的现象，则移去该矩形箱）；当出现剩余　货物时，把这些货物按摆放序列函数排列，插入到ｉ中（如果ｉ空间仍不足，则增加一新矩形箱）．　２．６约束的处理　本文提　的装箱问题含有单箱空间利用率约束，采用在解的评价函数中增加惩罚函数的方法加以　限制．惩罚函数如下　，　Ｐ＝ｃ　∑ｍａｘ（０，＿一　、　Ｄ—ｄ　）　ｉ　Ｅ　其中，　为选用矩形箱集合；　为矩形箱ｉ的实际空间利用率；ｃ为惩罚系数．本文中Ｃ将采用动态变化的　方法，初始值取０，随着迭代次数的增加，ｃ按曲线ｃ：０．０１　￣／ｍ逐渐增加．即在迭代过程中，空间利用　率约束逐渐由软约束过渡到硬约束．　２．７禁忌表的设计和终止准则　本文设计的两种邻域是针对不同对象（货物序列和单个货物）进行的操作，故构造了与之相对应的　两个禁忌表，分别为货物序列禁忌表和货物方位禁忌表．　货物序列禁忌表．即对序列调整系数ａ按步长　进行操作，如果当前代对ａ进行了增加　的操作，那　么在接下来的７７　代内，不允许对ａ进行减小　的操作；货物方位禁忌表．即如果当前代对货物ｉ进行了　方位取反操作，那么在接下来的７７　代内，不允许再对货物　进行方位取反操作．　终止准则．如果连续迭代　代最优解没有变化，则算法终止．　３禁忌算法优化大型二维装箱问题关键步骤　禁忌算法优化多箱型二维装箱问题详细步骤为：　（１）初始化各参数，产生初始解，搜索循环次数ｉ＝０；　（２）ｉ：＝ｉ＋１；　（３）货物摆放方位变化邻域，货物序列更新邻域操作；　（４）禁忌表及特赦准则处理；　（５）满足终止条件，转（６）；否则转（２）；　（６）结束．　４算例结果及其分析　４．１算例及结果　把Ｍａｒｔｅｌｌｏ算例产生程序稍加修改，增加Ｗ　≤ｈ　限制，产生一组数据．货物型号分为２５种，每种型　号宽度　在区间（０．５，５）中随机产生，高度ｈ。在区间（２，１０）中随机产生，且Ｗ　≤ｈ　，每种货物型号的数　量在区问（５０，１５０）之间产生，总共产生２２３９个货物．　＝５０，Ｈ＝７０，Ｄ％＝８５％．　用ｃ语言实现大型二维装箱问题的禁忌算法，取禁忌算法参数　＝０．０２，７７　＝３０，卵　＝４，　ＮＤ＝２００，Ｎｘ＝２０．在ＰＩＶ２．０机型上计算２０次，以１００％概率收敛到本算法所能得到的最优解值为　１３（各解的货物排列序列不完全相同），总空间利用率达到９３．７％，平均收敛时问仅为１分２６秒．　维普资讯 http://www.cqvip.com 第５期　屈援，等：大型二维装箱问题及其禁忌算法研究　３５　４．２算例分析　由于２ＢＰ问题是ＮＰ—ｈａｒｄ问题，对于４．１规模的问题，很难得到精确解，运用本文提出的禁忌算　法，能够以比较稳定的收敛过程得到次优解．从算法的计算效果方面分析是有效的．对于货物规模达到　２２３９的算例，本禁忌算法仍能以较快速度（平均收敛时间为１分２６秒）得到优化解．从算法的计算效率　方面分析是有效的．　５　结语　本文对大型二维装箱问题进行了描述，提出了求解该问题的禁忌算法，介绍了算法的原理，并通过　算例结果及其分析证明了此算法的有效性．用本文提出的禁忌算法能优化规模较大的二维装箱问题，速　度较快，运算过程及结果稳定，具有较强的实际应用价值．　参考文献：　［１］Ｌｏｄｉ　Ａ，Ｍａｒｔｅｌｌｏ　Ｓ，Ｍｏｎａｃｉ　Ｍ．Ｔｗｏ—ｄｉｍｅｎｓｉｏｎａｌ　ｐａｃｋｉｎｇ　ｐｒｏｂｌｅｍｓ：Ａ　ｓｕｒｖｅｙ［Ｊ］．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，１９９６（７６）：２３５—２４９．　［２］Ｃｏｆｆｍａｎ　Ｊｒ　Ｅ　Ｇ，Ｇａｒｅｙ　Ｍ　Ｒ，Ｊｏｈｎｓｏｎ　Ｄ　Ｓ。Ａｐｐｒｏｘｉｍａｔｉｏｎ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｂｉｎ　ｐａｃｋｉｎｇ：Ａ　ｓｕｒｖｅｙ，ｉｎ：Ｄ．Ｓ。Ｈｏｃｈｂａｕｍ　（Ｅｄ．），Ａｐｐｒｏｘｉｍａｔｉｏｎ　Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ＮＰ—Ｈａｒｄ　Ｐｒｏｂｌｅｍｓ［Ｊ］．Ｐｗｓ　Ｐｕｂｌｉｓｈｉｎｇ　Ｃｏｍｐａｎｙ，Ｂｏｓｔｏｎ，１９９７　（２３）：４６—９３．　［３］Ｄｏｗｓｌａｎｄ　Ｋ．Ｓｏｍｅ　ｅｘｐｅｒｉｍｅｎｔｓ　ｗｉｔｈ　ｓｉｍｕｌａｔｅｄ　ａｎｎｅａｌｉｎｇ　ｔｅｃｈｎｉｑｕｅｓ　ｆｏｒ　ｐａｃｋｉｎｇ　ｐｒｏｂｌｅｍｓ［Ｊ］．Ｅｕｒｏｐｅａｎ　Ｊｏｕｒｎａｌ　ｏｆ　Ｏｐｅｒａｔｉｏｎａｌ　Ｒｅｓｅａｒｃｈ，１９９３（６８）：３８９—３９９。　［４］Ｍａｒｔｅｌｌｏ　Ｓ，Ｐｉｓｉｎｇｅｒ　Ｄ，Ｖｉｇｏ　Ｄ．Ｔｈｅ　ｔｈｒｅｅ—ｄｉｍｅｎｓｉｏｎａｌ　ｂｉｎ　ｐａｃｋｉｎｇ　ｐｒｏｂｌｅｍ［Ｊ］．Ｏｐｅｒａｔｉｏｎｓ　Ｒｅｓｅａｒｃｈ，２０００（４８）：　２５６—２６７．　Ｔｈｅ　ｓｔｕｄｙ　ｏｎ　ｌａｒｇｅ　ｓｃａｌｅ　ｔｗｏ　ｄｉｍｅｎｓｉｏｎａｌ　Ｂｉｎ　Ｐａｃｋｉｎｇ　Ｐｒｏｂｌｅｍ　ａｎｄ　ｉｔｓ　ｔａｂｕ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　ＱＵ　Ｙｕａｎ　’－，ＷＡＮＧ　Ｘｕｅ．１ｉａｎ　（１．Ｓｃｈｏｏｌ　ｏｆ　Ｍａｎａｇｅｍｅｎｔ，Ｔｉａｎｊｉｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉｎ　３０００７２，Ｃｈｉｎａ；　２。Ｓｃｈｏｏｌ　ｏｆ　Ｍａｎａｇｅｍｅｎｔ，Ｊｉｎａｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ　５　１０６３２，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ａ　ｌａｒｇｅ　ｓｃａｌｅ　ｔｗｏ　ｄｉｍｅｎｓｉｏｎａｌ　Ｂｉｎ　Ｐａｃｋｉｎｇ　Ｐｒｏｂｌｅｍ（２ＢＰ）ｉｓ　ｐｒｅｓｅｎｔｅｄ　ｉｎ　ｔｈｉｓ　ｐａｐｅｒ．Ａ　ｔａｂｕ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ（ＴＳ）ｉｓ　ｄｅｓｉｇｎｅｄ　ｔｏ　ｓｏｌｖｅ　ｔｈｉｓ　ｐｒｏｂｌｅｍ　ｏｎ　ｎａｔｕｒｅ　ｎｕｍｂｅｒ．Ｔｏ　ｅｘｔｅｎｄ　ｔｈｅ　ｓｅａｒｃｈ　ｓｐａｃｅ，ｔｗｏ　ｋｉｎｄｓ　ｏｆ　ｎｅｉｇｈｂｏｒｈｏｏｄ　ａｎｄ　ｔｗｏ　ｋｉｎｄｓ　ｏｆ　ｔａｂｕ　ｌｉｓｔ　ａｒｅ　ｐｒｏｐｏｓｅｄ　ｉｎ　ｔｈｉｓ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｕｓｅｓ　ｐｅｎａｌｔｙ　ｆｕｎｃｔｉｏｎ　ｔｏ　ｃｏｎｔｒｏｌ　ｔｈｅ　ｕｔｉｌｉｚａｔｉｏｎ　ｒａｔｉｏ　ｌｉｍｉｔ．Ｔｈｅ　ｐｒｉｎｃｉｐｉｕｍ　ｔｈｅ　ＴＳ　ａｒｅ　ｉｎｔｒｏｄｕｃｅｄ，ａ　ｒｅｐｒｅｓｅｎｔａｔｉｖｅ　ｒｅｓｕｌｔ　ａｎｄ　ｔｈｅ　ａｎａｌｙｓｉｓ　ａｒｅ　ｇｉｖｅｎ．Ｔｈｅ　ｅｘｐｅｒｉｍｅｎｔ　ａｎｄ　ｔｈｅ　ａｎａｌｙｓｉｓ　ｉｎｄｉｃａｔｅ　ｔｈｅ　ｖａｌｉｄｉｔｙ　ｏｆ　ｔｈｅ　ＴＳ　ｔｏ　ｔｈｅ　ｌａｒｇｅ　ｓｃａｌｅ　ｔｗｏ　ｄｉｍｅｎｓｉｏｎａｌ　Ｂｉｎ　Ｐａｃｋｉｎｇ　Ｐｒｏｂｌｅｍ．　Ｋｅｙ　ｗｏｒｄｓ：Ｂｉｎ　Ｐａｃｋｉｎｇ　Ｐｒｏｂｌｅｍ；ｔｗｏ　ｄｉｍｅｎｓｉｏｎａｌ；ｔａｂｕ　ｓｅａｒｃｈ　ａｌｇｏｒｉｔｈｍ　责任编校：朱夜明