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.

Automated summary

A novel heuristic approach NHACR was proposed to solve the 2D rectangle packing problem with central rectangles, improving performance through three new strategies. The NHACR outperformed existing algorithms in terms of success rate, filling rate of final layout, and computing time across two benchmark sets, confirming its advantage in solving specific application problems in the oil and gas industry.