论文部分内容阅读
装箱问题就是将不同尺寸的物品摆放入有一定容量的容器中,以获得某种最佳的效益。装箱问题广泛地用于机械生产和交通运输等行业当中。对该问题求解方法的研究无论是在理论上,还是在实践中都具有一定的意义。装箱问题属于组合最优化问题和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算法要好。