计算机技术与发展2024，Vol.34Issue(7)：138-146,9.DOI:10.20165/j.cnki.ISSN1673-629X.2024.0096
二维矩形Strip Packing问题的算法研究与改进
Algorithm Research and Improvement for Optimizing 2D Rectangle Strip Packing Problem
摘要
Abstract
The constraints and objective function of the two-dimensional rectangular Strip Packing problem are similar to those of the basic two-dimensional rectangular Packing problem in that each rectangular block is effectively placed in a limited rectangular container with the goal of maximizing container utilization.To tackle this famous NP-hard problem,we conduct in-depth algorithm research and achieve significant improvements based on the quasi-human global optimization algorithm proposed by Deng Jiankai and Wang Lei.Ac-cording to the characteristics of the Strip Packing problem,we propose the QHG(Quasi-Human Group)algorithm,incorporating key enhancements such as enlarging the set of the initial points,deleting and replacing evaluation criteria and expanding the search scope of neighborhood space.Compared with the iteration of a single local minimum point,iterating on a set of local minimum points can generate better configurations.Off-trap procedure is used to jump out of the local minimum point and lead the search into the promising areas.Tree-search procedure is expected to further improve the area usage ratios of the configurations.Through these measures,the QHG algorithm better simulates human decision-making processes so as to generate better configurations.To evaluate the performance of the QHG algorithm,extensive experiments are conducted on 8 sets of standard problem instances(C,N,NT,CX,NP,ZDF,2sp,and bwmv).The experimental results demonstrate that the quality of the configurations generated by the QHG algorithm surpasses several ad-vanced algorithms in the current international literature,highlighting its outstanding performance in addressing the Strip Packing problem.关键词
Strip Packing问题/组合优化/全局优化/算法/拟人Key words
Strip Packing problem/combinatorial optimization/global optimization/algorithm/quasi-human分类
信息技术与安全科学引用本文复制引用
蔡家尧,王磊..二维矩形Strip Packing问题的算法研究与改进[J].计算机技术与发展,2024,34(7):138-146,9.基金项目
国家自然科学基金(62271359) （62271359）
