二维矩形Strip Packing问题的算法研究与改进

来源：计算机技术与发展杂志2024年第07期北京时间：

作者：蔡家尧;王磊

摘要：二维矩形 Strip Packing 问题的约束条件及目标函数与基本型二维矩形 Packing 问题类似,都是在有限的矩形容器中,有效地摆放各个矩形块,以最大化容器利用率为目标。 为了解决这一 NP-hard 问题,该文在邓见凯、王磊提出的拟人型全局优化算法的基础上进行了深入的算法研究与改进。 针对 Strip Packing 问题特点,提出了QHG(Quasi-Human Group)算法,其核心改进涵盖了多个方面,包括扩充初始点集合、删除和替换评价标准以及扩大邻域空间搜索范围。 和单个局部极小值点的迭代相比,对局部极小值点集合进行迭代所生成布局优度更高,跳坑策略用于跳出局部极小值点,将搜索引向有希望的区域,优美度枚举有望进一步提高布局优度。 通过这些措施,QHG 算法更好地模拟人类决策过程,提高了全局搜索的效率。 为评估 QHG 算法性能,对 8 组标准问题实例(C 组、N 组、NT 组、CX 组、NP 组、ZDF 组、2sp 组、bwmv 组)进行了大量实验。 实验结果表明,QHG 算法生成的布局优度优于当前国际文献中的几种较先进算法,展现了其在 Strip Packing 问题上的卓越性能。

关键词：Strip Packing问题;组合优化;全局优化;算法;拟人