An improved heuristic algorithm for 2D rectangle packing area minimization problems with central rectangles

摘要

Be different with traditional 2D rectangle packing area minimization problem (RPAMP), a specific RPAMP named CR-RPAMP includes one or more central rectangles, which must be located in the center of the final layout. Besides, for CR-RPAMP, the length and width of the final layout are not fixed, but can be changed within a reasonable length-width ratio scope. In this paper, based on HACR (heuristic algorithm for CR-RPAMP), an improved heuristic algorithm called IHACR is proposed in order to improve the performance of HACR, especially to decrease the computational complexity of HACR. Compared with HACR, IHACR includes three more rectangle placement mechanisms, which are strategy of combining rectangles, strategy of leaving biggest inner space and strategy of eliminating unnecessary comparisons. Then, a set of schematic descriptions is used to describe the difference between HACR and IHACR. Simulation results based on 34 benchmark instances show that computing time obtained by IHACR is much shorter than that obtained by HACR when solving CR-RPAMP, and the filling rate of final layout obtained by IHACR is bigger than that obtained by HACR while the number of rectangles of the instance is appropriate large. It means that IHACR is more effective and efficient than HACR. Finally, HACR and IHACR are used for solving the equipment layout problem of oil-gas-water treating system of semi-submersible production platform, and the results show that the performance of IHACR is better than that of HACR. The wonderful final layout obtained by IHACR satisfies the requirements of semi-submersible production platform and verifies the practicality and high-efficiency of IHACR.