Heuristic algorithm for RPAMP with central rectangle and its application to solve oil-gas treatment facility layout problem

Abstract

In this study, we address a specific 2D rectangle packing area minimization problem with central rectangle (CR-RPAMP). The most distinguishing feature of CR-RPAMP is that there exists at least one central rectangle among the candidate rectangles. The proposed MHACR (modified heuristic algorithm for CR-RPAMP) includes three new strategies which are strategy of monitoring the aspect ratio, strategy of decreasing computational complexity and strategy of filling the marginal inner space. The computational complexity analyses show that MHACR has a lower computational complexity than the existing algorithms IHACR (improved heuristic algorithm for CR-RPAMP) and HACR (heuristic algorithm for CR-RPAMP). Then, a series of experiments based on 34 benchmark instances are carried out, and the experimental results show that MHACR can produce better solutions as compared with IHACR and HACR, especially under a narrow limited scope of aspect ratio. Finally, MHACR is used to solve the facility layout problem of oil–gas treatment factory, and the final layout generated by MHACR is more suitable than that obtained by IHACR. Therefore, we can conclude that MHACR is a remarkable heuristic algorithm to solve CR-RPAMP.