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

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