求解二维矩形装箱问题的启发式算法

摘要

为实现二维矩形装箱问题的高效求解,提出一种启发式最优剩余空间算法.该算法以促使小矩形的放置更为紧密和剩余空间更加平滑为基本思想,通过空间分割、放置位置选择和最优解搜索3个相来实现对三维矩阵装箱问题的求解.基于两个经典的C21和N13数据集,最优剩余空间算法与多种算法进行了对比实验.测试结果表明,所提算法能够在最短的时间内得到C21全部算例的100％布置和N13数据集的9个最优解,在计算效率和计算效果上均优于现阶段的其他算法.