基于遗传和递归的装箱算法研究.pdf

摘要
装箱问题就是将不同尺寸的物品摆放入有一定容量的容器中，以获得某种最
佳的效益。装箱问题广泛地用于机械生产和交通运输等行业当中。对该问题求解
方法的研究无论是在理论上，还是在实践中都具有一定的意义。装箱问题属于组
合最优化问题和 NP 完全问题，具有高度复杂性，用一般的数学方法很难求解，
目前研究得最多的是用启发式方法解决装箱问题。
本文为求解二维装箱问题提出了 GA+HR、GA+IHR 和 GA+OIHR 三个算法。
这三个算法是在已提出的 HR 算法的基础上改进的。GA+HR 算法是 HR 算法结合遗
传算法的全局搜索能力，通过遗传算法搜索到更优的排列顺序，使得解的效果进
一步提高。GA+IHR 算法中，定义了参考矩形和结合层的概念，通过找出所有结
合层，然后计算每个结合层数所产生的解，最后从这些解中找出最优的解和最佳
结合层数。GA+OIHR 算法中，在 HR 算法中加入了穷举的思想，即对每一层的
第一块矩形的放置都考虑水平放置和垂直放置两种情况，然后分别计算出这两种
放置方式所带来的空间利用率。采用利用率比较大的方式作为该层的放置方式。
而且在每一层子空间采用 HR 递归算法时，先搜索那些长或宽要么和子空间的高
度相同要么和子空间的宽度相同的矩形，先把这些矩形放置好，这样放置后该子
空间还是只被划分成一个更小的子空间，可以减少子空间的个数。从而减少因为
不断递归划分成两个子空间，使得一些小空间因为再也放置不下任何一块矩形而
造成的浪费。
在本文中我们还把计算二维装箱问题的 HR 算法和 GA+HR 算法运用到三维
装箱问题中。计算结果显示 HR 算法运行时间短，但所带来的空间利用率并不理
想；GA+HR 算法运行时间较长，但有较高的空间利用率。特别地，GA+HR 算法
的平均结果比著名的 Bischoff 算法要好。

关键词：遗传算法；装箱问题；启发式算法
Abstract
The bin packing problem is to put some objects with various sizes into a defined
space in order to obtain the specified optimal benefit. Bin packing is a combinatorial
optimization and NP-complete problem and widely applied to the mechanical
manufacture and traffic transportation industries. The study of algorithm for bin
packing problem is of great significance not only in theory but also in practice. Up to
now, the heuristic algorithm is one of the most efficient algorithms for the packing
problem because the problem is of high complexity.
In this paper, we propose GA+HR algorithm, GA+IHR algorithm and GA+OIHR
algorithm for 2D-packing problem. They are based on the Heuristic Recursive
algorithm (HR). GA+HR algorithm is to combine genetic algorithm with global
search capability with HR algorithm. It can search the better sequence to make the
solution further improvement. In the GA+IHR algorithm, we define the concepts of
the reference rectangle and the