An improved heuristic algorithm for 2D rectangle packing area minimization problems with central rectangles. (November 2017)

• Record Type: Journal Article
• Authors: Wu, Lei; Tian, Xue; Zhang, Jixu; Liu, Qi; Xiao, Wensheng; Yang, Yaowen
• Is Part Of: Engineering applications of artificial intelligence. Volume 66(2017:Jun.)
• Page Start: 1
• Page End: 16
• Publication Date: 2017-11
• Subjects: Two-dimensional rectangle packing -- Heuristic algorithm -- Central rectangle -- Layout optimization -- Equipment layout -- Semi-submersible production platform; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2017.08.012
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: 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. Highlights: A special RPAMP named CR-RPAMP is described. An improved heuristic algorithm called IHACR is proposed for solving CR-RPAMP. IHACR includes three new strategies for packing rectangles. Experiment results prove the advantage of IHACR compared with HACR. IHACR is used to solve the layout problem of semi-submersible production platform.