Abstract: To solve the two-dimensional Rectangular Packing Problem (RPP) efficiently,a recursive heuristic algorithm named Best Residual Space Algorithm (BRSA) was proposed.Based on the idea to make the items placement more compact and the remaining space smoother,three stages that were space division,placement position selection and optimal solution searching was adopted.Based on two sets of classical benchmark instances C21 and N13,BRSA was compared with many algorithms.The experimental results showed that BRSA was able to obtain all 100% filling rates for C21 and nine optimal solutions for N13 in shortest time,which was superior to the current algorithms in both computational efficiency and effectiveness.

Key words: rectangular packing, layout optimization, space utilization maximization, heuristic algorithms

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

关键词: 矩形装箱, 布局优化, 空间利用率最大, 启发式算法