装箱问题是一个经典的组合优化问题。简单地说,装箱问题就是将若干不同尺寸的物体互不重叠地放入有一定容量的箱子中以达到某种最佳目标。装箱问题被广泛应用于计算机科学领域和工业领域,多处理器任务调度、内存管理、货物装载以及原料切割等都是装箱问题在实际应用中的具体体现。因此,研究装箱问题具有重要的理论意义和应用价值。从二十世纪七十年代起,学术界就对装箱问题进行了广泛而深入的研究,但是由于装箱问题是NP难的,具有高度复杂性,用一般的数学方法很难求解。因此,在最近的几十年,启发式算法被广泛应用于装箱问题的求解中。本文首先对装箱问题的研究现状、问题分类及求解算法进行了综述和分析,然后重点对二维矩形装箱问题进行研究。在总结和概括了当前主要的装箱优化算法的基础上,对已有的HR和PH算法进行改进,提出了两种新的算法:基于递归思想的模拟退火算法(SA+HR)和基于动态分层的最小浪费优先启发式算法(SA+LWFBDL)。SA+HR算法主要是引进了模拟退火算法对HR算法进行改进,将HR算法得到的值作为评价解的标准,将任意交换两个物体位置得到的所有物体序列的集合作为邻域解空间,从而搜索出更好的物体序列来改善解的质量。而SA+LWFBDL算法在保留PH算法动态分层的基础上,改进了物体的放置策略,装物体时考虑所有的可行位置,优先选择放置后浪费面积最小的物体和可行位置的组合,对于浪费面积相同的多种组合,按照适合度进行选择,最后我们采用模拟退火算法来改善物体的装箱顺序从而得到更好的解。实验结果表明,我们提出的两种算法比原有的算法HR和PH有很大的改进。而且SA+HR的求解质量优于著名的算法BF、SA+BLF和GA+BLF,而SA+LWFBDL算法经过多次运行对大多数实例都可以得到最优解,可以与目前优秀的算法SPGAL、HRBB和HRP相竞争。