Algorithm Research and Improvement for Optimizing 2D Rectangle Strip Packing Problem
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.
国家科技期刊平台
NSTL
万方数据
