NHACR: A novel heuristic approach for 2D rectangle packing area minimization problem with central rectangle

摘要

As a special 2D rectangle packing problem, the 2D rectangle packing area minimization problem with central rectangle (CR-RPAMP) has one or more central rectangles among the candidate items. The central rectangles should be packed near the center of the final layout. At the same time, the length-width ratio of the final layout must be within a reasonable region. The CR-RPAMP has been applied in many areas such as the layout design of semi-submersible platform, farmland irrigation, urban planning. In this study, to improve the performance of heuristic approach for solving the CR-RPAMP, three novel strategies including strategy of filling inner space, strategy of generating inner space and strategy of simplifying packing process, are proposed and combined to form a novel heuristic approach NHACR (Novel Heuristic Approach for CR-RPAMP). The analyses of computational complexity of the proposed NHACR indicate that it has low computational complexity. Based on two famous sets of benchmark instances, the proposed NHACR shows better performance compared with several existing algorithms considering the success rate, the filling rate of final layout and the computing time. Finally, the NHACR is utilized to solve a specific application problem in oil and gas industry and its advantage is further confirmed.