ｐｅｒｓｏｎｉｆｉｃａｔｉｏｎ ｈｅｕｒｉｓｔｉｃｓ，ｗｈｉｃｈ ｉｓ ｉｎｓｐｉｒｅｄ ｂｙ ｔｈｅ ｄａｉｌｙ
ｓｔｒａｔｅｇｙ
ｏｆ
ｂｕｉｌｄｉｎｇ ｗａｌｌ ｉｎ ｔｈｅ ２Ｄ・ｐａｃｋｉｎｇ
ｌｉｆｅ．Ｓｉｍｉｌａｒ
ｔｏ
ｔｈｅ ｐｅｒｓｏｎｉｆｉｃａｔｉｏｎ ｈｅｕｒｉｓｔｉｃｓ ｆｏｒ ｔｈｅ
ａ
ａｌｇｏｒｉｔｈｍ，ｗｅ
ｂａｓｅｄ
ｔｒａｎｓｆｏｒｍ
ｔｈｅ ２Ｄ ｓｔｒｉｐ ｐａｃｋｉｎｇ
ｐｒｏｂｌｅｍ ｉｎｔｏ
ｐｒｏｂｌｅｍ．Ｔｈｅｎ，ｆｏｒ ｔｈｅ ２Ｄ
ｏｎ
ｋｎａｐｓａｃｋ
ｐａｃｋｉｎｇ ｐｒｏｂｌｅｍ，ｗｅ ｐｒｅｓｅｎｔ
ｔｏ ｐａｃｋ
ｌｅａｓｔ
ｗａｓｔｅｄ
ｆｉｒｓｔ ｓｔｒａｔｅｇｙ
等制造行业都有广泛应用。
与切割相对应的是填充（排样、布局）问题，随着超大规模集成电路的出现， 一块电路板中的元器件有成千上万个。怎么样合理地安排每个元器件在电路板上 的位置，最大化利用电路板的空间，即电路板的布局问题，成为集成电路版图设 计中的一个重要步骤。该问题也同样出现在报纸的排版中。 在数学的王国中，有一个问题一直困扰着人们，即“完美正方形”【２ｌ的寻找。 所谓“完美正方形＂是指可以用一些大小各不相同，并且边长为整数的小正方形 铺满的正方形，有趣的是，该问题也跟装箱问题有密切联系，事实上，２１阶的 “完美正方形’’正是用大型电子计算机算出来的。 由此可见，装箱问题的应用非常广泛，研究该问题有着重要的实际意义。随 着应用领域的不同，装箱问题的目标和约束条件也不同，因此人们抽象出了一些 通用的数学模型并把该问题分成了很多类型来分别研究。装箱问题一般可描述如
ａｎｄ ｔｈｅ ｎｅｗｓｐａｐｅｒ
ｅｄｉｔｏｒ．Ｉｔ ｉｓ
ａ
ＮＰ ｃｏｍｐｌｅｔｅ
ｐｒｏｂｌｅｍ；ｔｈｅ ｒｅｓｅａｒｃｈ
ｐｒａｃｔｉｃｅ．Ｉｔ ｉｓ ｈｉｇｈ ｐａｃｋｉｎｇ
ｏｎ
ｔｈｉｓ ｐｒｏｂｌｅｍ ｉｓ ｏｆ ｇｒｅａｔ ｉｆ ｗｅ
ｕｓｅ
ｓｉｇｎｉｆｉｃａｎｃｅ
ｉｎ ｂｏｔｈ ｔｈｅｏｒｙ
ａｎｄ
ＢＦＤ（Ｂｅｓｔ
Ｆｉｔ Ｆｉｔ
Ｄｅｃｒｅａｓｉｎｇ）、ＮＦＤ（Ｎｅｘｔ
Ｆｉｔ
Ｄｅｃｒｅａｓｉｎｇ）、
Ｄｅｃｒｅａｓｉｎｇ）等。一维装箱问题的研究相对比较成熟，关于一维装箱
的具体资料可参考文献［６．１０】。 自从Ｐａｕｌｌ［１１】在１９５６年提出新闻排版问题以来，二维装箱问题一直是一个研 究的热点。该问题又可分为规则物品装箱和不规则物品装箱。在规则物品装箱中， 研究较多的是矩形装箱。对于矩形装箱，人们一开始集中寻求该问题的近似求解 【１２１，如基于一维装箱的ＦＦＤ算法、ＢＦＤ算法；双向背包算法；相近图形组合算 法；线性规划、分支定界和动态规划算法等。文献［１３．１４］对二维矩形装箱各种算
２
第一章绪论
法的性能进行了分析。Ｇｉｌｍｏｒｅ［１５］等使用线性规划技术求得该问题实例的最优 解，这被认为是对原料切割的第一个工业可应用的研究。文献［１６．１７］用树搜索方 法解决二维矩形装箱问题也能达到最优。后来，Ｈｉｆｉ［１８１等提出了一种精确算法： 最好优先分支定界算法。这些近似算法的特点是针对某类或某些装填问题的结果 较好，但是对于规模很大的实例很难在合理的时间内给出好的结果。启发式算法 正好弥补了这个缺点，它能够在合理的时间内给出比较好的结果，即使对于规模 很大实例。其中著名的算法有：ＢＬ（Ｂｏｔｔｏｍ．Ｌｅｆｔ）【１９】，ＢＬＦ（Ｂｏｔｔｏｍ．Ｌｅｆｔ．Ｆｉｌｌ） ［２０】，ＢＦ（Ｂｅｓｔ．Ｆｉｔ）［２¨。国内，张德富等对可旋转的二维矩形装箱问题提出了两种
声明人ｃ㈣：氧风军
沙Ｑ墨年岁月２Ｓ日
厦门大学学位论文著作权使用声明
本人完全了解厦门大学有关保留、使用学位论文的规定。厦门大 学有权保留并向国家主管部门或其指定机构送交论文的纸质版和电 子版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学 校图书馆被查阅，有权将学位论文的内容编入有关数据库进行检索， 有权将学位论文的标题和摘要汇编出版。保密的学位论文在解密后适 用本规定。 本学位论文属于 １．保密（ ），在 年解密后适用本授权书。
厦门大学 硕士学位论文 求解装箱问题的启发式算法研究 姓名：魏丽军 申请学位级别：硕士 专业：计算机应用技术 指导教师：张德富 20080401
摘要
摘要
装箱问题是个在工业生产中经常碰到的问题，如集装箱的装载、板材的切割、 集成电路的设计、报纸的排版等等。该问题又是ＮＰ完全问题，因此对该问题的 研究有着重要的应用价值和理论意义。如果用精确算法求解装箱问题，势必带来 计算量的组合爆炸，因此学者提出了很多求解该问题的启发式算法。 本文首先研究了二维装箱问题，在总结前人工作的基础上，提出了解决二维 矩形条装箱（２ＳＰ）的二分搜索启发式（ＢＳＨＡ）算法。首先，通过引入二分搜索把２ＳＰ
ｉｍｐｒｏｖｅ
ｔｈｅ ｐｅｒｓｏｎｉｆｉｃａｔｉｏｎ ｈｅｕｒｉｓｔｉｃｓ．Ｃｏｍｐｕｔａｔｉｏｎａｌ ｒｅｓｕｌｔｓ
ｔｈｅ
ｂｅｎｃｈｍａｒｋ ｆｒｏｍ ｔｈｅ
ｉｎｓｔａｎｃｅｓ
ｌｉｔｅｒａｔｕｒｅｓ．
ｓｈｏｗ
ａｌｇｏｒｉｔｈｍ Ｃａｎ ｃｏｍｐｅｔｅ ｗｉｔｈ
ｅｘｃｅｌｌｅｎｔ
ｈｅｕｒｉｓｔｉｃｓ
关键词：装箱问题；启发式算法：模拟退火
Ａｂｓｔｒａｃｔ
Ａｂｓｔｒａｃｔ
Ｐａｃｋｉｎｇ ｐｒｏｂｌｅｍ ｉｓ ｆａｃｅｄ ｉｎ ｍａｎｙ ｉｎｄｕｓｔｒｉｅｓ，ｆｏｒ ｅｘａｍｐｌｅ，ｔｈｅ ｃｏｎｔａｉｎｅｒ ｌｏａｄｉｎｇ， ｔｈｅ ｓｈｅｅｔ ｃｕｔｔｉｎｇ，ｔｈｅ ｄｅｓｉｇｎ ｏｆ ＶＬＳＩ
ＧＲＡＳＰ，ＳＰＧＡＬ，ＨＲＢＢ，ｅｓｐｅｃｉａｌｌｙ，ＢＳＨＡ
ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｆｏｒ ｍａｎｙ ｉｎｓｔａｎｃｅｓ ｉｎ ｓｈｏｒｔ ｔｉｍｅ．
Ｆｏｒ ｔｈｅ ３Ｄ—ｐａｃｋｉｎｇ ｐｒｏｂｌｅｍ，ｗｅ Ｆｉｒｓｔｌｙ，ｗｅ ｄｅｖｅｌｏｐ
ａ
ｐｒｅｓｅｎｔ
ａ
ｃｏｍｂｉｎａｔｉｏｎａｌ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ．
Ｋｅｙ ｗｏｒｄｓ：Ｐａｃｋｉｎｇ
Ｐｒｏｂｌｅｍ；Ｈｅｕｒｉｓｔｉｃ Ａｌｇｏｒｉｔｈｍ；Ｓｉｍｕｌａｔｅｄ Ａｎｎｅａｌｉｎｇ
厦门大学学位论文原创性声明
兹呈交的学位论文，是本人在导师指导下独立完成的研究成果。 本人在论文写作中参考的其他个人或集体的研究成果，均在文中以明 确方式标明。本人依法享有和承担由此论文产生的权利和责任。
求解装箱问题的启发式算法研究
下：给定一批物品和容器，要求将这批物品的一部分或全部互不重叠地装入容器 中，使其某项性能达到最优，有时还要满足其它的一些限制条件。～般地，根据 容器所属空间维数的不同，该问题可分为一维装箱、二维装箱和三维装箱。然而 不幸的是，即使是最简单的一维装箱，也被证明是ＮＰ完全问题【３】，即在多项式 时间内找不到最优解，如果采用精确算法进行求解，计算量会随着问题规模增大 而发生组合爆炸。因此，很多学者对该问题进行了研究，以期能够找到一种快速， 接近全局最优解的算法。然而，迄今为止，还是没找到令人满意的算法。对于二 维装箱问题，虽然提出了很多算法，但对于著名的由Ｈｏｐｐｅｒ和Ｔｕｒｔｏｎ［４】提出的 ２１个实例，还是不能找到最优解。而对于三维装箱问题，目前较好的算法也只 能对某些实例达到９０％的空间利用率，因此，都有着很大的改进空间。 装箱问题还跟计算机组合优化问题中的作业调度问题等有着密切相关性，研 究该问题能够推动人们对ＮＰ完全问题的认识，找到更一般的解决组合优化问题 的方法，因此还有很大的理论价值。 总之，研究装箱问题有着重要的实际意义和理论价值。
问题转化成二维背包装箱问题（２ＫＰ）来求解。然后，针对２ＫＰ，本文提出了最小
浪费优先策略，该策略通过记录点的方法来记录装填位置，并引入浪费面积、平 整度等评价机制来评价某个物品放入某个位置的好坏程度。最后，利用随机局部 搜索算法进一步改进计算的结果。本文对ＢＳＨＡ算法进行了大量的实例测试， 结果表明，ＢＳＨＡ的求解质量优于目前优秀的算法，如ＧＲＡＳＰ、ＳＰＧＡＬ、ＨＲＢＢ
ｐｒｏｂｌｅｍ，ｗｅ
ｉｎｔｒｏｄｕｃｅ ｔｈｅ‘＇ｒｅｆｅｒｅｎｃｅ ｂｏｘ’’ａｎｄ ｔｈｅ‘‘ｒｅｆｅｒｅｎｃｅ ｌｉｎｅ＇’ｔｏ
ｇｕｉｄｅ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｐａｃｋｉｎｇ．Ｌａｓｔｌｙ，ａ
ｔｏ
ｓｉｍｕｌａｔｅｄ
ａｎｎｅａｌｉｎｇ ａｌｇｏｒｉｔｈｍ 请在以上相应括号内打“４”）
作者签名：乏魁风写日期：扫。吕年｝月２∑日
剔程名纠劬醐：硎年ｊ，月％日
第一章绪论
第一章绪论
１．１研究背景及意义 装箱／布局问趔ｌｌ是个在实际生产生活中经常碰到的，对工业生产和经济发展
有重要意义的问题。
随着我国经济的快速发展，物流成为经济建设中不可或缺的行业，配送则是 物流中一个极为重要的环节，而集装箱装载是一种非常重要的配送方法。因此如 何最大限度的利用集装箱容积和承载能力从而降低配送成本，即集装箱配装问 题，成为了物流中研究的热点。当然在实际应用中，必须考虑各种限制条件，比 如装载货物的稳定性、同类货物的装载约束性、货物抗压性以及装卸货物的方便 性等等。 在板材的工业生产中，总是先做出有一定规格的板材毛坯，再根据实际需要 切割成小块板材。而需求总是千变万化，因此，怎样用已有的板材毛坯切割出各 种形状的小板材以满足实际需要，同时使得浪费的板材最小，即怎样最大化板材 的利用率，这个与生产成品息息相关的切割（裁剪）问题，成了板材生产中关心 的重点。这个问题在钢铁制造行业、纸品加工行业、服装制造业、以及玻璃加工
ｐｒｏｂｌｅｍ．Ｂａｓｅｄ
ｏｎ
ｔｈｅ ｋｎｏｗｎ ｔｈｅ ２Ｄ ｓｔｒｉｐ
ａｌｇｏｒｉｔｈｍ，ｗｅ ｐｒｅｓｅｎｔ
ｐａｃｋｉｎｇ
ｂｉｎａｒｙ ｓｅａｒｃｈ ｈｅｕｒｉｓｔｉｃ