（计算机软件与理论专业论文）二维装箱问题的启发式算法研究.pdf

摘要 摘要 装箱问题是一个经典的组合优化问题。简单地说，装箱问题就是将若干不同 尺寸的物体互不重叠地放入有定容量的箱子中以达到某种最佳目标。装箱问题 被广泛应用于计算机科学领域和工业领域，多处理器任务调度、内存管理、货物 装载以及原料切割等都是装箱问题在实际应用中的具体体现。因此，研究装箱问 题具有重要的理论意义和应用价值。 从二十世纪七十年代起，学术界就对装箱问题进行了广泛而深入的研究，但 是由于装箱问题是n p 难的，具有高度复杂性，用一般的数学方法很难求解。因 此，在最近的几十年，启发式算法被广泛应用于装箱问题的求解中。 本文首先对装箱问题的研究现状、问题分类及求解算法进行了综述和分析， 然后重点对二维矩形装箱问题进行研究。在总结和概括了当前主要的装箱优化算 法的基础上，对已有的h r 和p h 算法进行改进，提出了两种新的算法：基于递 归思想的模拟退火算法( s a + h r ) 和基于动态分层的最小浪费优先启发式算法 ( s a + l w f b d l ) 。s a + h r 算法主要是引进了模拟退火算法对h r 算法进行改 进，将h r 算法得到的值作为评价解的标准，将任意交换两个物体位置得到的所 有物体序列的集合作为邻域解空间，从而搜索出更好的物体序列来改善解的质 量。而s a + l w f b d l 算法在保留p h 算法动态分层的基础上，改进了物体的放 置策略，装物体时考虑所有的可行位置，优先选择放置后浪费面积最小的物体和 可行位置的组合，对于浪费面积相同的多种组合，按照适合度进行选择，最后我 们采用模拟退火算法来改善物体的装箱顺序从而得到更好的解。 实验结果表明，我们提出的两种算法比原有的算法h r 和p h 有很大的改进。 而且s a + h r 的求解质量优于著名的算法b f 、s a + b l f 和g a + b l f ，而s a + l w f b d l 算法经过多次运行对大多数实例都可以得到最优解，可以与目前优秀 的算法s p g a l 、h r b b 和h r p 相竞争。 关键词：装箱问题；启发式算法；模拟退火 a b s t r a c t a b s t r a c t t h ep a c k i n gp r o b l e mi sat y p i c a lc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s i m p l y , t h ep a c k i n gp r o b l e mi st op a c kt h eo b j e c t so fd i f f e r e n ts i z e si n t oad e f i n e ds p a c es oa s t oo b t a i nt h es p e c i f i e do p t i m a lo b j e c t i v e t h ep a c k i n gp r o b l e mh a sb e e nw i d e l y a p p l i e dt ot h ef i e l d so fc o m p u t e rs c i e n c ea n di n d u s t r y , s u c ha sm u l t i p r o c e s s o r s c h e d u l i n g ，m e m o r ym a n a g e m e n t ，g o o d sl o a d i n ga n ds t o c kc u t t i n g ，s ot h ep a c k i n g p r o b l e mh a sg r e a ts i g n i f i c a n c en o to n l yi nt h e o r yb u ta l s oi np r a c t i c e m a n yr e s e a r c h e r sh a v ed o n eal o to fr e s e a r c h e so nt h ep a c k i n gp r o b l e ms i n c e 19 7 0 s b e c a u s et h ep a c k i n gp r o b l e mi sn pc o m p l e t ea n do fh i g hc o m p l e x i t y , t h e g e n e r a lm a t h e m a t i c a lm e t h o d sa r eh a r dt os o l v ei t ，s oh e u r i s t i ca l g o r i t h m sh a v eb e e n w i d e l ya p p l i e dt ot h ep a c k i n gp r o b l e mi nl a t e s ty e a r s t h ea r t i c l er e v i e w st h er e s e a r c hp r o g r e s s ，a n da l s os u m m a r i z e st h ec l a s s i f i c a t i o n a n da l g o r i t h m sf o r t h ep a c k i n gp r o b l e m t h em a i nw o r ko ft h ea r t i c l ef o c u s e so nt h e t w o - d i m e n s i o n a lr e c t a n g u l a rs t r i pp a c k i n g b a s e do nt h ec u r r e n th ra n dp hm e t h o d ， t w on e wh e u r i s t i ca l g o r i t h m ss a + h ra n ds a + l w f b d la r ep r e s e n t e d s a + h ru s e s s i m u l a t e da n n e a l i n g ( s a ) t os e a r c hb e t t e ro r d e r so f o b je c t ss oa st og e tb e a e rs o l u t i o n s ， i nw h i c hh ri st h eb a s i cp a c k i n gs t r a t e g ya n dt h en e i g h b o r h o o di sd e f i n e db y e x c h a n g i n gt h ep o s i t i o n so ft w oo b j e c t sr a n d o m l y t h el e a s tw a s t e df i r s tp a c k i n g s t r m e g yb a s e do nd y n a m i cl a y e r si sp r e s e n t e di ns a + l w f b d l ，w h i c hs t i l lu s e st h e r a n d o ms e a r c ht e c h n o l o g ys at os e a r c hb e t t e rs o l u t i o n s t h e c o m p u t a t i o n a lr e s u l t so ns e v e r a lc l a s s e so f b e n c h m a r kp r o b l e m sh a v es h o w n t h a ts a + h ra n ds a + l w f b d li m p r o v et h es o l u t i o n so fh ra n dp h s a + h rc a n f i n db e n e rs o l u t i o nt h a nb f , s a + b l fa n dg a + b l es a + l w f b d lc a ng e to p t i m a l s o l u t i o n sf o rm a n yi n s t a n c e sb ys e v e r a lr u n s ，w h i c hc a nc o m p e t ew i t he x c e l l e n t a l g o r i t h m ss u c ha ss p g a l ，h r b ba n dh r p k e yw o r d s ：p a c k i n gp r o b l e m ；h e u r i s t i ca l g o r i t h m s ；s i m u l a t e da n n e a l i n g 厦门大学学位论文原创性声明 兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。本人在论文 写作中参考的其他个人或集体的研究成果，均在文中以明确方式标明。本人依法 享有和承担由此论文产生的权利和责任。 声明人( 签名) ： 砷年6 月日 厦门大学学位论文著作权使用声明 本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大学有权保留 并向国家主管部门或其指定机构送交论文的纸质版和电子版，有权将学位论文用 于非赢利目的的少量复制并允许论文进入学校图书馆被查阅，有权将学位论文的 内容编入有关数据库进行检索，有权将学位论文的标题和摘要汇编出版。保密的 学位论文在解密后适用本规定。 本学位论文属于 i 保密() ，在年解密后适用本授权书。 2 不保密( 4 ) ( 请在以上相应括号内打“4 ) 作者签名：渊 导师签名混徨面 矽哆矽倒 否月沙日 石 月2日 v 第一章绪论 1 1 课题的应用背景 第一章绪论 装箱问题是一个经典的n p 完全问题 1 】，早在二十世纪七十年代，学术界就 对装箱问题进行了广泛的探讨和研究 2 】。研究对象包括一维、二维、三维和高 维物体。装箱问题中研究最早和最多的是一维装箱问题 3 】。这一问题有很多的 实际背景，例如：用户送来一张订货单j = a 。，口：，口。) ，q 表示第f 个物品的长度 ( 允许有相同的) 。所说的物品可以是钢条、铅管、电缆、原装纸卷等一维线材。 假设厂家提供的原材料的标准长度为c ，当然，我们假定口，c ，试问如何能以 最少量的原材料截出用户所需要的物件。还有，假设有胛个物件需要加工，每一 物件只需在一台机器上加工一次即可，设加工第i 个物件所需的时间为a ；，所有 的机器性能皆相同，现要求所有的物件在规定时间c 内全部加工完毕，试问如何 以最少量的机器在规定时间内完成所有的任务。 尽管装箱问题有如此广泛的应用，然而，装箱问题的求解是非常困难的。由 于装箱问题是著名的n p h a r d 问题 1 】，采用精确算法虽然可以求得最优解，但 是随着问题规模的变大，计算量会发生组合爆炸，因此许多学者都试图采用近似 算法来求得装箱问题的近似解。 随着研究的深入，人们发现实际生活中更多存在的是一些带约束条件的装箱 问题，因此也就抽象出了，如二维、三维乃至高维装箱问题、有色装箱问题、对 偶装箱问题等等一系列的带约束的装箱问题。这里着重介绍二维装箱问题。通常 所说的二维装箱问题都是关于矩形物品的装箱问题。如果每个物品是不可旋转 的，则物品在装箱时只能水平放置，这类问题比较简单；如果每个物品可以在装 箱时加以旋转，则物品在装箱时有两种放置方向：水平方向和竖直方向，此时问 题是非常复杂的。在本文所讨论的装箱问题中，矩形物品在装箱过程中都是可旋 转的。 装箱问题是理论计算机科学与组合优化领域的一个重要问题，随着计算机科 学、管理科学和现代化生产技术等的日益发展，越来越受到运筹学、应用数学、 二维装箱问题的启发式算法研究 计算机科学及管理科学等诸多学科的重视。分析和研究装箱问题对其它n p 问题 的研究具有很大的参考价值。 装箱问题的应用在实际生活中无处不在，计算机科学中的多处理器任务调 度、存储分配、共享资源调度、内存管理等底层操作都是装箱问题在实际应用中 的体现。在工业领域中，包括服装行业的面料裁剪、运输行业的货物装运、印刷 行业的排版、加工行业的板材下料( 木料、玻璃、金属等) 、现实生活中的包装、 整理物件等，很多问题都可以归结为求解一个二维装箱问题，只是不同的应用可 能会有不同的约束条件和目标。由于与人们的生产生活密切相关，而且求解二维 装箱问题的近似算法也可以应用到三维装箱问题的求解中，所以研究二维装箱问 题具有重要的理论意义和应用价值。找到二维装箱问题的有效算法可以节省资 源，提高生产效率，对人们的生产生活产生重大影响，从而对人类社会具有积极 的推动作用。 1 2 国内外研究现状 装箱问题是一个典型的n p 完全问题，即在多项式时间内无法找到问题的最 优解。当问题的规模逐渐增大时，用传统的搜索技术求解这类问题，就会出现“组 合爆炸”的现象。在实践中，人们一般用启发式方法来求解装箱问题。 关于一维装箱问题的研究成果十分丰富，比较著名的算法有w f 、b f 、n f 、 f f 、f f d 等算法。其中最早提出的在线装箱算法是下次适应算法( 简称n f ) ， 效果最好的离线装箱算法为递减首次适应算法( 简称f f d ) 。c o f f m a n 等人在文 献 4 】中对经典一维装箱问题做了一个极好的综述，包含了几乎所有的经典一维 装箱算法。在经典的一维装箱算法中，最早的一个著名的结果是j o h n s o n 2 得到 的，他提出的算法是递减首次适应算法( f f d ) 。j o h n s o n 在1 9 7 3 年证明了f f d 算法的相对近似比r = 1 1 9 。随后g a r e y 与j o h n s o n ( 1 9 8 5 ) 设计出改进的f f d ， 具有群= 7 1 6 0 的近似比。这个不断改进尺；的过程已达到一个惊人的结果， l u e k e r 等发现对任意小的s 0 存在着具有r 象。) l + g 的算法a ( 6 ) ，在此基础上 只要稍作改进便可构造出尺：= 1 的算法。可以说，到目前为止，一维装箱问题已 经研究得比较成熟。 第一章绪论 对于二维装箱问题，自从p a u l l 5 在1 9 5 6 年提出新闻排版问题后，该领域一 直是一个研究的课题。由于其应用的广泛性，许多研究者对其进行了深入的研究， 并提出了很多有效的算法。这些方法大致可以分为三类：精确算法、启发式算法 和现代启发式算法。 精确算法主要包括线性规划、分支定界和动态规划等算法。g i l m o r e 和 g o m o r y ( 1 9 6 1 ) 2 4 使用线性规划方法来求得问题实例的最优解，这被认为是对原 料切割的第一个工业可应用的研究。尽管如此，由于受到计算时间的限制，只有 小规模的问题实例可以解决。c h r i s t o f i d e s 和w h i t l o c k ( 1 9 7 7 ) 7 使用树搜索方法解 决二维g u i l l o t i n ep a c k i n g 问题并达到最优，b e a s l e y ( 1 9 8 5 ) 8 解决n o n g u i l l o t i n e p a c k i n g 问题也同样达到最优。尽管如此，当问题规模更大时，这些方法就变得 在时间上不可行。后来，h i f i 和z i s s i m o p o l o u s ( 1 9 9 7 ) 9 对文献 7 的算法进行改进 并提出了一种精确算法：最好优先分支定界算法。c u n g 等人( 2 0 0 0 ) 1 0 基于文献 【9 】中的算法提出了一种新版本算法，解决了二维切割问题的一些变种问题。这 些方法的一个主要缺点就是不能在合理的时间内对规模大的实例计算出好的结 果。这时，就需要提出一些启发式算法来得到好的结果，虽然解不一定是最优的。 到目前为止，已经出现了很多启发式算法能够在合理的时间内计算出较好的 结果，对于规模大的例子也同样如此。文献 1 1 2 2 中不仅提出了启发式算法而且 分析了算法的近似比，包括n f d h 、f f d h 等算法。但是对于很多启发式算法， 分析它们的近似比是非常困难的。a l b a n o 和o r s i n i ( 1 9 7 9 ) 2 3 提出了一种启发式 方法：对于4 0 0 4 0 0 0 个矩形的规模较大的实例，将一些相似的矩形拼成一个更 大的矩形。b a k e r 等人提出了一种不同的经典装箱算法b l ( b o t t o m l e f t ) 【1 2 】： 把物品按宽度递减排序，将当前处理的物品放入能容纳它的尽量低尽量左的位 置，时间复杂度为o ( n 2 ) 。b l f ( b o t t o m l e f t f i l l ) 算法 2 4 1 是b l 算法的修改版， 时间复杂度为o ( n 3 ) 。e k b u r k e ( 2 0 0 4 ) 提出了一种新的启发式算法b f ( b e s t f i t ) 2 5 ：动态选择最合适的物体并增加了后处理策略，可以在很短的时间内求出较 好的解。张德富对可旋转的二维矩形装箱问题提出了两种快速有效的启发式算 法：递归启发式算法【2 6 】和拟人启发式算法 2 7 】。黄文奇等人对二维装箱问题提 出了一些有效的算法 2 8 ，2 9 ，其中的最小弹性优先和占角思想等都很巧妙。崔耀 东在递归启发式算法 2 6 】的基础上提出了一种新的递归分支定界算法 3 0 】，对某 二维装箱问题的启发式算法研究 些实例也得到了不错的结果。 现代启发式算法虽然比一般的启发式算法花费的时间更长一些，但是得到的 结果却更好，因此在装箱问题中的应用非常广泛，它其实是一种将启发式算法和 智能优化算法( 模拟退火算法、遗传算法、禁忌搜索算法、蚁群算法和神经网络 等) 相结合而构成的混合算法。a a r t s 和l e n s t r a 3 1 ，g l o v e r 和l a g u n a 3 2 给出 了这方面的一般性介绍。d a g l i 和h a j a k b a r i ( 1 9 9 0 ) 3 3 实现了对该类问题的现代启 发式算法的首次应用：他们使用模拟退火算法将矩形和不规则的物体装入到一个 有限维数的箱子中。l a i 等人 3 4 和f a i n a 3 5 将模拟退火算法应用到原料切割问 题中。人工神经网络方法也被d a g l i 和p o s h y a n o n d a 应用到该类问题中 3 7 。 k r o g e r 3 8 ( 1 9 9 5 ) 提出了求解二维装箱问题( 2 b p ) 的一种遗传算法。 b o r t f e l d t 3 9 ( 2 0 0 6 ) 提出了一种没有任何编解码的遗传算法，对某些实例结果表现 非常好。l o d i 4 0 - 4 2 等人给出了2 b p 的禁忌搜索算法。 3 6 q b 给出了基于b f 的 多种现代启发式算法并取得了较好的结果。h o p p e r 和t u r t o n 4 3 ( 2 0 0 1 ) 针对二维 装箱问题对启发式算法和现代启发式算法进行了实验分析。其它一些现代启发式 算法可参考文献 4 4 4 6 。 总的来说，现代启发式算法是一类更加复杂的启发式方法，同一实例经过多 次运行可能会得到多组不同的解，算法中都存在一些参数需要多次调整以达到最 好的效果。 三维装箱问题由于其复杂性和难度大，相关的研究文献较少，且各种算法都 是基于一定的假设之下，因此这些算法在具有各种复杂约束条件的实际应用中就 会受到很大的限制。到目前为止，提出了不少有效的三维装箱算法，较好的算法 对某些实例可达到9 0 左右的空间利用率，具体可参见文献 4 7 5 2 。 关于装箱问题的综述性文献可见d y c k h o f f 5 3 5 5 、d o w s l a n d 5 6 和l o d i 5 7 。 装箱算法的概率分析可见文献e 5 8 ，5 9 】。 1 3 本文的内容安排 尽管二维装箱问题已经研究了几十年，并且也出现了大量的研究成果，最近 提出的一些算法对某些问题实例可以达到1 左右的误差 2 9 ，3 0 ，3 9 ，但是它们并 不能适用于所有的问题实例，所以还有很大的局限性。因此提出一种通用的近似 4 第一章绪论 比更小的算法很有必要，但这也是件非常困难的事。本文主要对物体可旋转的二 维矩形装箱问题进行了研究，对文献 2 6 ，2 7 】中的算法进行改进并提出了一些更加 有效的方法，全文的主要内容安排如下： 第一章主要介绍了装箱问题的应用背景及其国内外研究现状，并在此基础上 阐述了本文的内容安排。 第二章是装箱问题概述，主要介绍了裁剪与装填问题，装箱问题的分类及 n p 难问题的一般求解方法。 第三章对启发式算法和智能优化算法在装箱问题中的应用做了详细介绍与 分析，重点介绍了b l 、b f 和h r 等几种比较经典的构造启发式算法和应用较多 的智能优化算法：模拟退火算法。 第四章是本文的核心，主要针对二维矩形装箱问题进行研究，在已有算法 h r 和p h 的基础上进行改进，提出了两种有效的启发式装箱算法，并对其进行 了实验测试和结果分析。 第五章对本文进行了总结，并提出了进一步的研究工作。 二维装箱问题的启发式算法研究 2 1 裁剪与装填问题 第二章装箱问题概述 装箱问题属于裁剪与装填问题( c u t t i n ga n dp a c k i n gp r o b l e m ) 的一个重要分 支。 裁剪问题，通常是指在一种材料上寻找各种形状的最佳布局以使材料的浪费 率最小。装填问题则通常是指若干小的物体以最佳方式组合并装入一个大的空间 从而使得空间的利用率最大 6 0 。装填问题也被称为布局问题。 图1 下料问题( - - 维裁剪问题) 从本质而言，裁剪问题与装填问题有着天然的内在联系，是一个互逆的过程， 很难有一个严格的界定将它们区分开来 6 0 。首先，它们都有两组最基本的数据， 一组是大的空间或原料，另一组是小的物体或形状；其次，它们在本质上都是一 种几何组合，即将小的物体或形状进行某种组合，使之能充分利用大的空间或原 料。具体来讲，对于装填问题，我们可以认为将小物体装入大空间的过程看作是 将大空间以最小浪费为目标分割成若干小空间( 小空间对应小物体) 的过程；对 于裁剪问题，可以认为是将若干剪成的小物体材料以最大的原料利用率为目标回 填到原来大材料中的过程。因此我们把这两类问题当作一类大的问题来考虑。例 如：图1 中的下料问题既可以看成二维裁剪问题，也可以看成二维装箱问题。 6 第二章装箱问题概述 裁剪与装填问题主要是在一维、二维和三维的物理空间中进行的。由于具有 很高的实用价值，裁剪与装填问题近年来在国际上备受关注。其中裁剪问题主要 应用于木材加工业、纺织皮革业、板金加工业等板料的切割或下料，装填问题主 要应用于半导体加工行业和机械行业等的布局设计 6 1 1 、企业的车辆装载、托盘 装载、货架上的货物摆放等等。尽管裁剪与装填问题具有很强的工程代表性，但 是由于它们是n p 难问题，求出最优解非常困难。由于此类问题涉及面广、潜在 价值巨大，同时又具有很高的复杂度，因此吸引了众多领域的研究人员对它进行 深入的研究，使它成为管理科学、计算机科学以及数学与运筹学等众多学科的一 个重要研究领域。 针对裁剪与装填问题的研究最早出现在大约五十年代。当时人们试图使用线 性规划求出在一大块材料上合理放置矩形块的最优解。但是，随着问题规模的增 大和不规则形状的引入，对于精确算法来说，遍历整个搜索空间以求得最优解已 经不太可能。于是近年来出现了针对不同材料与形状、不同目标、不同约束等情 况的裁剪装填问题的各类算法。 目前对于此类问题的解决方法分为精确算法和启发式算法两种。精确算法主 要包括分支定界、回溯法、动态规划等传统算法 6 1 0 】，这类算法只适合求解问 题规模比较小的情况，因为随着问题规模的增大，求解时间为指数级，不能在合 理的时间内算出最优解 6 2 】。因此，对装箱问题的研究采用的更多的方法是常规 启发式算法和各种智能搜索算法( 如模拟退火、遗传算法、禁忌搜索) 。虽然这 些方法未必能够算出最优解，但它们快速有效，一般可以满足实际问题的需要。 2 2 装箱问题分类 装箱问题涉及多学科、多领域的知识，属于复杂的组合最优化问题，被广泛 应用于生产实践中。由于不同的应用可能有不同的目标和约束条件，因此出现了 各种各样的装箱问题。本节从不同角度对装箱问题进行了分类。 2 2 1 按照装箱物体所属空间进行分类 1 一维装箱问题 经典的一维装箱问题( 1 b p ) 是这样描述的：给定一正数c 和一组数 7 二维装箱问题的启发式算法研究 j = q ，口：，a 。) ，0 口，c ，v i 寻求一种划分方法将，分成一些互不相交的子集 b ；，使得j = b 。ub ：u ub 。，满足y ，。a ；c ，w ，并使m 为满足这一要求的最-”o d i i a 口i 口 小整数。 该问题有着广泛的实际背景，如：钢条、铅管、电缆、原装纸卷等一维线材 的切割问题和物件加工问题都可归结为一维装箱问题。 2 二维装箱问题 在二维装箱问题中，被装物体的形状可以是矩形、三角形、圆形和其它一些 不规则形状，但是研究最为广泛的是二维矩形装箱问题，该问题主要可以分为如 下两类： ( 1 ) 2 s p ( t w o d i m e n s i o n a ls t r i pp a c k i n gp r o b l e m ) ：给定聍个矩形物品集合 j = 1 , 2 ，玎 和一个宽度为有限值，高度无限的箱子( s t r i p ) ，要求将所有的物 品装入箱子中而使得占用的箱子高度最小。在具体装填时，每个物品也有直角装 填、定向等限制。 在服装厂，制衣服的布匹通常都是卷起来的，可以看成一个宽度固定长度不 限的s t r i p ，如何用最短的布匹裁剪出需要的衣服，这就是一个2 s p 问题。 根据一些限制条件，2 s p 问题又可以划分为以下四个子类 4 0 ： a r f 类型：物体可以进行9 0 度旋转( r ) 而且不要求一刀切( f ) ； b r g 类型：物体可以进行9 0 度旋转( r ) 但是要求一刀切( g ) ； c o f 类型：物体的方向是固定的( o ) 但是不要求一刀切( f ) ； d o g 类型：物体的方向是固定的( o ) 而且要求一刀切( g ) 。 它们分别被称为r f2 s p , r g2 s p , o f2 s p 和o g2 s p 问题。在这里，“一刀切 的 原则是每切一刀都必须使原来的矩形分为两个矩形。关于2 s p 更详细的描述，可 参考文献 4 0 ，5 8 ，6 3 。本文中所讨论的问题属于r f2 s p 问题。 ( 2 ) 2 b p ( t w o d i m e n s i o n a lb i np a c k i n gp r o b l e m ) - 给定刀个矩形物品集合 j = 1 , 2 i i - - o ，刀 和无穷多个尺寸相同的矩形箱子( b i n ) ，其中第f 个物品的宽度为 嵋，高度为h i ，扛1 , 2 ，拧。矩形箱子宽度为形，高度为日，要求将所有的物品 装入箱子中而使用的箱子数量最少。 设用户需要n 块矩形钢板，而钢铁厂出产的原材料通常都是标准大小的钢板， 第二章装箱问题概述 如何裁剪最少量的原材料以满足用户的需求，这就是一个2 b p 问题。 对2 s p 问题，若设每个物体的高度都相等，限制装填方式为直角定向，则问 题退化为一维装箱问题；对2 b p 问题，若设每个物体的宽度与箱子宽度相等， 则该问题也退化为一维情形。 二维装箱问题在实际生活中有着广泛应用，如应用于板类( 金属板、木板、 玻璃、大理石板等) 切割行业和服装剪裁行业等的下料问题，建筑业中的房间布 局，工业中的模板布局( t e m p l a t el a y o u t ) 、新闻排版，集成电路布图设计及其 它一些工程设计等。 3 三维装箱问题 根据目标函数和边界约束条件的不同，三维装箱问题主要有以下几种变化形 式： ( 1 ) 最小长度装箱( s t r i pp a c k i n g ) ：它假设容器的高度和宽度为确定尺寸 但长度无限大，目标是装载所有的物体并使占用的容器长度最小。该类问题可以 应用在多目的地卸货情况下。 ( 2 ) 背包装载( k n a p s a c kl o a d i n g ) ：在背包装载问题中，每个物体都带有 一定的利润，问题是选择物体集的一个子集装到一个容器中使得装载的利润最 大。如果每个物体的利润与其体积相等，那么该问题的目标就转化为使得容器空 间浪费最小或者说容器空间利用率最高。 ( 3 ) 货柜装箱( b i np a c k i n g ) ：在该问题中，所有容器都有固定的尺寸且规 格统一，目标是所有的物体都要装到容器中且使用的容器数量最小。 ( 4 ) 多容器装载( m u l t i c o n t a i n e rl o a d i n g ) ：该问题与货柜装箱类似，只是 容器可以有多种规格且每个容器都有一定的运输成本，目标是选择容器的一个子 集装下所有物体并使得运输成本最小。 关于三维装箱问题更一般性的分类，可参考文献 6 4 ，6 5 】。 三维装箱问题有着广泛的应用背景，如运输行业的集装箱货物装载、飞机装 舱、码头装货等，机械行业中的钟表等布局，航空、航天工业中导弹仓的布局， 以及建筑、电子、造船业和纺织业等诸多领域。 9 二维装箱问题的启发式算法研究 2 2 2 按照装箱物体的形状进行分类 1 规则物体的装箱 包括二维规则物体的装填和三维规则物体的装填。规则物体是指具有规则外 形的物体，二维的主要有三角形、圆形和矩形等，三维的主要包括圆柱体、长方 体等。在过去及现在的装箱问题研究中，研究较多的仍然是规则物体的装箱问题， 如：原料切割问题，工业应用中的底盘装载问题和三维布局中的集装箱的货物摆 放问题等。 2 不规则物体的装箱 包括二维不规则物体的装箱和三维不规则物体的装箱。不规则物体是指具有 任意几何形状的物体。不规则物体的装箱问题在工业生产中大量存在，但同时也 是难度最大的装箱问题。二维不规则物体的装箱，如服装样本的下料、皮革下料 等。三维不规则物体的装箱，如向具有任意几何形状的容器中放置任意几何外形 的装箱物体，并满足特定的约束条件，达到装箱目标最优。从文献资料中可以看 出，许多研究者利用人工智能原理求解该类复杂问题 6 6 】。该问题的求解算法基 本上都是启发式的。 2 2 3 按照装箱物体到达情况进行分类 1 在线装箱问题 如果一个装箱算法在装入物品a ；时，只利用前面物品口m j f ) 的信息，而 不知道后继物品的任何信息，即按照物体到达顺序随到随装，则称该算法为在线 ( o n l i n e ) 算法。这种情况下的装箱问题称为在线装箱问题 6 7 。在实际应用中， 往往要求装载具有在线特性。例如对从传送带上下来的物体进行装载。 很多一维、二维在线装箱问题都采用层的思想。层由沿箱子宽度放置的一列 物品组成，也就是说箱子是由层中最大高度的物品来分割的。典型方法包括高度 递减首次适配法( f f d h ) 6 8 ，6 9 ，高度递减次适配法( n f d h ) 6 8 ，6 9 ，7 0 ，高 度递减最佳适配法( b f d h ) 6 8 ，改进的高度递减首次适配法( 环f d ) 与协和 算法( h a r m o n i ca l g o r i t h m s ) 6 8 ，7 0 】。尽管这些方法都很相似，但是每个算法都 是用不同的策略决定将物品放在哪里。解决三维在线装箱问题的最流行的方法之 1 0 第二章装箱问题概述 一是s h e l fm e t h o d 7 1 ，该方法是通过聚组相近尺寸的物品来提高装载空间利用 率的。 2 离线装箱问题 对物品装箱以前就已经得到所有物品信息，之后统一处理所有物品的近似算 法称为离线( o f f i i n e ) 装箱算法。这种情况下的装箱问题称为离线装箱问题。在 现代化的物流配送中，很多都要求按订单送货，因此物品的信息都是提前知道的。 该问题广泛地出现在集装箱装载、原料切割等应用中。分支定界方法 7 2 】、启发 式算法、遗传算法 7 3 ，7 4 】和模拟退火方法【7 5 】等都是用来解决离线装箱问题的常 用方法。 综上所述，装箱问题的分类可用图2 来表示。 图2 装箱问题分类 2 3 组合优化问题及一般求解方法 因为装箱问题是复杂的组合优化问题和n p 难问题。所以在深入讨论装箱问 题之前，有必要简要介绍一下组合优化问题和n p 问题的相关概念及其常用的解 决方法。 二维装箱问题的启发式算法研究 2 3 1 组合优化问题的相关概念 组合优化问题是指在离散的、有限的数学结构上，求满足给定约束条件的目 标函数的最优值( 最大值或最小值) 的问题，也称离散优化问题 7 6 ，7 7 。该问题 是运筹学的一个经典而重要的分支，涉及到计算机科学、工业管理、通信网络、 交通运输等诸多领域。 对于一个组合优化问题，我们对其形式描述如下：o p tf t ( x ) ix d 其中， x = ( 一，x ：) r 表示一组决策变量，所有的离散变量均离散取值；d 为所有可行 解的集合，也称为解空间或搜索空间；厂( x ) 表示目标函数；o p t 可以是m i n 或 者m a x ，即问题的目标是求最小值或最大值。一个组合优化问题可以用( d ，厂) 来 表示，它的特点是解空间d 为离散的有限点的集合。 网络、调度、运输、布局等诸多领域中的许多问题，都可以归结为组合优化 问题。典型的组合优化问题包括旅行商问题( t r a v e l i n gs a l e s m a np r o b l e m ，简称 t s p ) 、装箱问题( b i np a c k i n gp r o b l e m ) 、调度问题( s c h e d u l i n g ) 、背包问题 ( k n a p s a c kp r o b l e m ) 、可满足性问题( s a t ) 等等。 从组合优化问题的定义可以看出，由于解空间是有限的，我们只要通过枚举 就可以得到问题的最优解。如果目标函数是线性的，很容易求得问题的最优解。 如果目标函数是非线性的，问题就变得非常复杂，虽然枚举法可以求得最优解， 但是当问题规模较大时，计算量会发生所谓的组合爆炸，要在有限的时间内求得 最优解，事实上已经不可能。因此，我们在设计算法时必须考虑到问题的复杂性， 根据计算机的承受能力来寻求有效的算法。 综上，只有知道了问题的难易，我们才能更好的解决问题。按照计算复杂性 理论研究问题求解的难易程度，可把问题分为p 类、n p 类和n p 完全类。令玎表 示一个问题实例的规模。如果求解任何一个规模为1 的问题实例所需要的最大计 算时间都可以用刀的多项式时间来表示，则说我们研究的问题是多项式时间可解 的，相应的求解算法具有多项式时间复杂度。如果一个判定问题可以用一个确定 性算法在多项式时间内解出，则称该问题属于p 类( p o l y n o m i a l ) 【7 8 。p 类问 题被认为是容易处理的问题。 如果一个判定问题可以用一个确定性算法在多项式时间内检查或验证它的 1 2 第二章装箱问题概述 解，则称该问题属于n p 类( n o n d e t e r m i n i s t i cp o l y n o m i a l ) 。n p 类问题也常被称 为具有指数时间算法的问题类。这类问题表示验证一个解比较容易，但是求解却 比较难，是不容易处理的问题。如果n p 类中的每一个问题都可多项式时间归约 到某个判定问题l ，则称l 是n p 难的。n p 难问题比n p 问题更难求解。如果一 个问题l 是n p 难的，又属于n p ，则称l 是n p 完全的。n p 完全问题是n p 问 题类中最难的问题，它表明只要有一个n p 完全问题存在多项式时间算法，则所 有的n p 问题都存在多项式时间算法。显然，具有多项式时间算法的问题比具有 指数时间算法的问题容易求解得多 7 7 ，7 8 ，8 0 。 自从上个世纪六十年代以来，人们发现越来越多的判定性的组合优化问题是 属于n p 难的，例如s a t 问题、装箱问题、工作车间调度问题、顶点覆盖问题、 t s p 问题、图着色问题等等，而只有少数问题属于p 类。事实上，许多重要的实 际应用问题，都是n p 难问题，因此最优求解这类问题是非常困难的。枚举法是 不可行的，但是我们可以根据具体问题的特点来设计有效的算法，以便在合理的 时间范围内，得到问题尽可能好的解。 2 3 2n p 难问题的一般求解方法 由上一小节我们知道，很多著名的组合优化问题都是n p 难问题，像s a t 问 题、背包问题、顶点覆盖问题、装箱问题等等，对这些问题不存在一个多项式时 间算法来求得所有实例的最优解，只能设计一些有效的算法在合理的时间内给出 尽可能好的解。很多研究者对此类问题都进行了大量深入的研究，其一般求解方 法主要包括如下几种 7 9 】： ( 1 ) 精确算法：主要包括动态规划、回溯法、分枝定界法等算法。 ( 2 ) 启发式算法：主要包括贪心算法、局部搜索、现代启发式算法( 禁忌 搜索、遗传算法、模拟退火算法、蚁群算法，神经网络、d n a ) 等等。 ( 3 ) 近似算法：多项式时间内返回近似解的算法，具有可证的性能界限。 ( 4 ) 随机算法：主要包括拉斯维加斯算法( l a sv e g a s ) 和蒙特卡洛算法 ( m o n t ec a r l o ) 两类随机算法。 精确算法虽然能给出最优解，但是实践表明：它们只能求解小规模问题，对 于大规模的问题就无能为力了。因为问题的难度决定了，随着问题规模的增大， 二维装箱问题的启发式算法研究 计算时间肯定会发生组合爆炸。因此，这类算法只适用于求解需要最优解但是规 模又比较小的问题。 跟精确算法相比，启发式算法计算速度快，能够处理规模比较大的问题，以 满足实际问题的需要。但是启发式算法的时间复杂度比较难分析，而且又不能保 证解的质量。因此启发式算法只适合求解规模很大，非常难处理，而且不一定需 要最优解的一类问题。 近似算法具有多项式时间复杂度，且有一个性能界。因此，近似算法不仅计 算速度快，而且能保证任一个实例的近似解与精确解不会相差太多。但是要找到 一个有效的近似算法并不乐观，甚至存在一些困难的问题，似乎连“合理 的近 似算法都可能不存在，除非p - - n p 7 8 。 与解决同一问题的最好的确定性算法相比，随机算法所需的运行时间或空间 通常更小一些，而且自然、简单、易于理解和实现 7 8 】。因此，对解决某些问题 来讲，随机算法不失为一个有效的算法。 1 4 第三章二维装箱问题算法综述 第三章二维装箱问题算法综述 3 1 启发式算法概述 在最近的二十多年中，启发式方法已经成为一个重要的科研领域。其吸引人 之处在于它能够迅速得到复杂最优化问题的近似最优解，同优化领域的纯数学方 法相比更有艺术性和创造性，因此吸引了众多的研究者。启发式方法的起源要追 溯到s i m o n 8 1 的有限合理性原理( b o u n d e dr a t i o n a l i t y ) 。 s i m o n 从心理学出发，分析并研究了人类活动的特点，注意到尽管人自身的 能力和知识有限，但却能自如的解决那些看起来难以胜任的问题，并做出正确的 决策和反应。秘密在于：人通常不是采用系统的、精确的方法去追求问题的最佳 解，而是通过逐步尝试的方法，达到有限合理的目标，即取得足够满意的解。这 就是有限合理性原理，即所谓的启发式( h e u r i s t i c ) 问题求解方法。人类就是采 用这种方法克服了计算复杂度高的困难，使原来的n p 完全问题迎刃而解。 通俗的说，启发式算法实际上就是吸取了生活中的经验，使用“窍门 来求 解一些复杂最优化问题，尽管不保证一定奏效，但好的窍门常常一用就灵，在大 多数情况下能很快解决问题。这就是说，对许多任务来讲，有可能使用与任务或 问题有关的信息而大大减少搜索的代价，或者受到生活中类似问题的启发来设计 算法，并找到比较满意的解。 p e a r l 8 2 在1 9 8 4 年对启发式算法进行了详细的论述并给出了启发式算法的 定义。他认为：所谓启发式算法是指一组指导算法搜索方向的、建议性质的规则 集，按照这个规则集，计算机通常可在解空间中寻找到一个较好的解，但并不能 保证每次都能找到较好的解，更不能保证找到最优解。换句话说，所谓启发式算 法就是那些从大量的实验数据来看，算法的实际计算性能较好，但从理论上证明 这些算法的最坏计算性能并不好，或者理论上并不能证明这些算法具有优良的计 算性能的算法。 启发式算法的本质就是部分地放弃算法“一般化、通用化”的概念，把所要 解的问题的具体领域知识加到算法中去，以提高算法的效率。例如：宽度优先搜 索法可以用于求解很多搜索问题，如九宫图、旅行商问题以及魔方等等。但在实 二维装箱问题的启发式算法研究 际使用时，效率也许低得惊人，甚至根本解不出来( 如魔方问题) 。但如果我们 为每类问题找出一些特殊规则，和宽度优先法配合起来使用，那结果就可能完全 不一样了 8 3 】。 由于启发式算法的设计不依赖于纯数学中优化理论的突破与发展，因此在最 近2 0 多年来其研究和应用获得了突飞猛进的发展。尤其是在复杂的组合优化问 题上，各种各样的启发式算法更是层出不穷。也正是由于启发式算法缺乏严格的 理论推