一种求解矩形packing问题的智能枚举算法

An intelligent enumerative algorithm for solving rectangle packing problem

矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路(VLSI)布局设计,新闻排版等。国内外已提出了许多求解此问题的算法,如:遗传算法,模拟退火算法以及启发式算法等。在目前已有研究的基础上,提出了一种智能枚举算法,该算法的关键在于设计一种快速有效的枚举策略。用Hopper和Turton提出的21个矩形packing实例对所提出的算法性能进行了实算测试,平均面积未利用率为0.04%,平均计算时间为277.69 s,并求得了其中18个实例的最优解。实算结果表明:该算法对求解矩形packing问题是行之有效的。

Rectangle packing is often applied in industry, such as shipping, timber cutting, very large scale integration （VLSI） floor planning, newspaper layout, and so on. Many algorithms, such as genetic algorithm, simulated annealing and other heuristic algorithms are presented to solve it. Based on existing research, an intelligent enumerative algorithm is proposed, and the key of the algorithm is to design a fast and efficient enumerative strategy. Twenty one instances provided by Hopper and Turton were used to test the performance of the proposed algorithm. The percent of unpacked area and runtime are 0.04% and 277.69 s respectively ; furthermore, 18 instances of them have achieved optimal solutions. The experimental results demonstrate that the presented algorithm is efficient for solving the rectangle packing problem.