Article Contents
Article Contents

# An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle

• * Corresponding author: Mao Chen
• This paper presents a heuristic algorithm for solving a specific NP-hard 2D rectangular packing problem in which a rectangle called central rectangle is required to be placed in the center of the final layout, and the aspect ratio of the container is also required to be in a given range. The key component of the proposed algorithm is a greedy constructive procedure, according to which, the rectangles are packed into the container one by one and each rectangle is packed into the container by an angle-occupying placement with maximum fit degree. The proposed algorithm is evaluated on two groups of 35 well-known benchmark instances. Computational results disclose that the proposed algorithm outperforms the previous algorithm for the packing problem. For the first group of test instances, solutions with average filling rate 99.31% can be obtained; for the real-world layout problem in the second group, the filling rate of the solution is 94.75%.

Mathematics Subject Classification: Primary: 68T20, 68R05.

 Citation:

• Figure 1.  Cartesian coordinate system and central rectangle

Figure 2.  An illustrative example of angle

Figure 3.  An illustrative example of initial layout

Figure 4.  An illustrative example of angle

Figure 5.  Visual representation of the changing trend with the increase of $\varepsilon$

Figure 6.  The final layout of two hard test instances

Figure 7.  Final layout of the drilling platform

Table 1.  Settings of important parameters

 Parameter Description Value Nar$_{\min}$ Lower bound of the aspect ratio of the container 0.5 Nar$_{\max}$ Upper bound of the aspect ratio of the container 2 $Z_{Hmin}$ Lower bound of the between centrality of CR in vertical direction 1 $Z_{Hmax}$ Upper bound of the between centrality of CR in vertical direction 2 $Z_{Wmin}$ Lower bound of the between centrality of CR in horizontal direction 1 $Z_{Wmax}$ Upper bound of the between centrality of CR in horizontal direction 2

Table 2.  Filling rate (%) of test instances N1--N10 under different values of parameter $\varepsilon$

 Instance Filling rate (%) under different values of parameter $\varepsilon$ 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 1.4 1.5 1.6 N1 81.63 81.63 83.33 77.37 83.33 78.43 77.75 77.37 74.59 74.59 73.46 73.46 74.59 74.59 73.46 52.59 N2 100 100 98.81 98.04 100 98.81 98.81 98.04 98.04 98.04 98.04 98.04 98.81 98.81 98.04 98.04 N3 99.67 99.67 99.47 99.67 99.21 99.21 99.21 98.75 98.81 98.81 98.88 98.04 99.21 98.04 98.04 90.74 N4 98.98 98.77 99.01 98.46 98.49 98.77 98.98 97.86 98.51 98.28 98.05 98.77 96.75 97.09 98.31 89.19 N5 99.21 99.21 99.21 99.21 98.18 98.24 98.12 98.39 98.19 97.98 97.65 97.98 98.27 97.23 97.92 97.22 N6 100 100 99.70 99.56 99.50 99.56 99.70 99.21 99.30 99.21 99.36 99.36 99.36 99.70 99.50 99.21 N7 100 99.95 100 99.95 99.55 99.95 99.50 99.50 99.55 99.30 99.90 99.95 99.55 99.30 99.38 99.30 N8 99.90 99.90 99.91 99.90 99.76 99.70 99.76 99.90 99.37 99.71 99.55 99.69 99.57 99.76 99.71 99.36 N9 99.75 99.75 99.73 99.73 99.73 99.68 99.73 99.68 99.68 99.68 99.68 99.68 99.68 99.68 99.68 99.68 N10 100 100 99.96 100 99.93 99.96 99.93 99.89 99.74 99.91 99.89 99.74 99.93 99.91 99.88 99.71 Average 97.91 97.89 97.91 97.19 97.77 97.23 97.15 96.86 96.58 96.55 96.06 96.47 96.57 96.41 96.39 92.50

Table 3.  Comparison with previous state-of-the-art algorithms on N13 and C21 instances

 Instance $n$ HACR HA_AOP $H$ $W$ Fillrate (%) Nar $Z_{H}$ $Z_{W}$ Time (s) $H$ $W$ Fillrate (%) Nar $Z_{H}$ $Z_{W}$ Time (s) N1 10 48 37 90.09 1.297 1.400 1.056 15.37 48 40 83.33 1.200 2.000 1.000 0.45 N2 20 36 45 92.59 0.800 1.250 1.500 77.48 30 50 100 0.6 2.000 1.500 0.13 N3 30 32 50 93.75 0.640 1.133 1.174 162.07 28 54 99.21 0.519 1.000 1.000 0.70 N4 40 89 76 94.62 1.171 1.119 1.533 294.51 70 93 98.49 0.753 1.500 2.000 17.10 N5 50 92 114 95.35 0.807 1.244 1.073 452.74 98 104 98.18 0.942 1.500 1.000 66.40 N6 60 74 71 95.17 1.042 1.467 1.536 747.08 75 67 99.50 1.119 2.000 2.000 20.76 N7 70 85 98 96.04 0.867 1.237 1.333 1061.3 90 89 99.55 1.011 1.500 1.500 62.07 N8 80 96 86 96.90 1.116 1.400 1.263 1406.7 99 81 99.76 1.222 2.000 1.000 54.29 N9 100 81 85 97.47 0.853 1.025 1.159 1913.8 94 80 99.73 1.175 1.000 2.000 59.98 N10 200 78 138 97.55 0.565 1.026 1.379 6075.4 121 87 99.93 1.391 2.000 1.500 334.58 N11 300 89 120 98.31 0.742 1.094 1.124 12489 105 100 100 1.050 2.000 2.000 572.07 N12 500 155 195 99.26 0.795 1.067 1.000 20435 154 196 99.39 0.786 1.000 2.000 93376.28 N13 3152 822 750 99.66 1.096 1.055 1.344 1.16$\times$10$^{5}$ 1024 600 100 1.707 2.000 2.000 187.80 C11 16 18 24 92.59 0.750 1.250 1.400 54.45 20 20 100 1.000 1.000 1.500 0.07 C12 17 16 27 92.59 0.593 1.286 1.077 60.88 20 20 100 1.000 1.000 1.500 0.05 C13 16 21 21 90.70 1.000 1.625 1.625 52.16 25 16 100 1.563 1.000 1.000 0.01 C21 25 28 23 93.17 1.217 1.000 1.300 98.76 30 20 100 1.500 2.000 1.000 0.02 C22 25 24 27 92.30 0.889 1.400 1.455 94.05 20 30 100 0.667 2.000 1.000 0.04 C23 25 28 23 93.17 1.217 1.333 1.556 103.44 30 20 100 1.500 2.000 1.500 0.02 C31 28 38 50 94.74 0.760 1.111 1.083 154.62 30 60 100 0.500 2.000 1.500 0.86 C32 29 52 37 93.56 1.405 1.364 1.176 149.78 44 41 99.78 1.073 1.500 2.000 2.11 C33 28 40 48 93.75 0.833 1.500 1.400 160.22 40 45 100 0.889 1.000 2.000 0.74 C41 49 54 70 95.24 0.771 1.700 1.333 427.69 82 44 99.78 1.864 2.000 2.000 11.28 C42 49 73 52 94.84 1.404 1.433 1.364 432.15 72 50 100 1.440 2.000 1.500 2.65 C43 49 60 63 95.24 0.952 1.308 1.100 430.27 50 72 100 0.694 2.000 1.000 4.05 C51 72 80 70 96.43 1.143 1.353 1.188 1216.3 100 54 100 1.852 1.500 1.000 1.80 C52 73 73 77 96.07 0.948 1.433 1.265 1300.4 100 54 100 1.852 2.000 2.000 0.21 C53 72 78 72 96.15 1.083 1.137 1.215 1278.2 90 60 100 1.500 1.000 2.000 5.06 C61 97 101 99 96.01 1.020 1.172 1.020 1714.5 120 80 100 1.500 1.000 2.000 13.99 C62 97 108 92 96.62 1.174 1.571 1.300 1807.6 128 75 100 1.707 2.000 2.000 2.65 C63 97 100 100 96.00 1.000 1.273 1.174 1786.3 85 113 99.95 0.752 1.000 1.500 83.70 C71 196 197 200 97.46 0.985 1.402 1.128 6246.2 183 210 99.92 0.871 1.500 2.000 3668.73 C72 197 180 219 97.41 0.822 1.308 1.190 6012.7 256 150 100 1.707 2.000 1.000 1.23 C73 196 238 166 97.20 1.434 1.380 1.243 6175.6 194 198 99.97 0.980 2.000 1.000 4621.96 Average 95.24 5614.32 99.31 3045.99

Table 4.  Details of the modules in a practical layout problem

 No. Layout module Length (m) Width (m) Height (m) 1 Drilling floor 33.00 24 10.00 2 Drilling collar storage area 9.60 2.00 1.10 3 Drilling pipe area No.1 9.60 8.50 1.70 4 Drilling pipe area No.2 9.60 8.50 1.70 5 30in drive pipe area 12.50 2.70 2.70 6 20in drive pipe area 12.50 3.50 3.50 7 13-3/8in drive pipe area 12.50 4.00 4.00 8 9-5/8in drive pipe area 12.00 7.00 6.00 9 7in drive pipe area 10.50 5.00 4.20 10 Flatwise marine riser area 23.00 13.00 7.00 11 Vertical marine riser area 32.00 10.00 23.00 12 Pipe conveyor area 24.00 4.00 10.00 13 Bop area 28.50 10.00 3.80 14 Christmas tree area 20.00 9.50 3.80 15 Mud purification area 18.00 16.50 2.00 16 Living quarters 38.00 11.00 11.00
•  [1] A. Lodi, S. Martello and M. Monaci, Two-dimensional packing problems: A survey, European Journal of Operational Research, 141 (2002), 241-252.  doi: 10.1016/S0377-2217(02)00123-6. [2] K. A. Dowsland and W. B. Dowsland, Packing problems, European Journal of Operational Research, 56 (1992), 2-14. [3] H. F. Lee and E. C. Sewell, The strip-packing problem for a boat manufacturing firm, IIE Transactions, 31 (1999), 639-651.  doi: 10.1080/07408179908969865. [4] D. S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the Association for Computing Machinery, 32 (1985), 130-136.  doi: 10.1145/2455.214106. [5] B. S. Baker, Jr. E. G. Coffman and R. L. Rivest, Orthogonal packing in two dimensions, SIAM Journal on Computing, 9 (1980), 846-855.  doi: 10.1137/0209064. [6] B. Chazelle, The bottom-left bin packing heuristic: An efficient implementation, IEEE Transactions on Computers, 32 (1983), 697-707.  doi: 10.1109/tc.1983.1676307. [7] S. Jakobs, On genetic algorithms for the packing of polygons, European Journal of Operational Research, 88 (1996), 165-181.  doi: 10.1016/0377-2217(94)00166-9. [8] D. Q. Liu and H. F. Teng, An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles, European Journal of Operational Research, 112 (1999), 413-420.  doi: 10.1016/S0377-2217(97)00437-2. [9] E. Hopper and B. Turton, An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem, European Journal of Operational Research, 128 (2001), 34-57.  doi: 10.1016/S0377-2217(99)00357-4. [10] Y. L. Wu, W. Q. Huang, S. C. Lau, C. K. Wong and G. H. Young, An effective quasi-human based heuristic for solving the rectangle packing problem, European Journal of Operational Research, 141 (2002), 341-358.  doi: 10.1016/S0377-2217(02)00129-7. [11] W. Q. Huang and D. B. Chen, An efficient heuristic algorithm for rectangle-packing problem, Simulation Modelling Practice and Theory, 15 (2007), 1356-1365. [12] D. F. Zhang, Y. Kang and A. S. Deng, A new heuristic recursive algorithm for the strip rectangular packing problem, Computers & Operations Research, 33 (2006), 2209-2217. [13] L. J. Wei, D. F. Zhang and Q. S. Chen, A least wasted first heuristic algorithm for the rectangular packing problem, Computers & Operations Research, 36 (2009), 1608-1614.  doi: 10.1016/j.cor.2008.03.004. [14] R. Alvarez-Valdes, F. Parreño and J. M. Tamarit, Reactive GRASP for the strip-packing problem, Computers & Operations Research, 35 (2008), 1065-1083.  doi: 10.1016/j.cor.2006.07.004. [15] K. He, W. Q. Huang and Y. Jin, An efficient deterministic heuristic for two-dimensional rectangular packing, Computers & Operations Research, 39 (2012), 1355-1363.  doi: 10.1016/j.cor.2011.08.005. [16] W. S. Xiao, L. Wu, X. Tian and J. L. Wang, Applying a new adaptive genetic algorithm to study the layout of drilling equipment in semisubmersible drilling platforms, Mathematical Problems in Engineering, 2015 (2015), Article ID 146902, 9 pages. doi: 10.1155/2015/146902. [17] L. Wu, L. Zhang, W.S. Xiao, Q. Liu, C. Mu and Y.W. Yang, A novel heuristic algorithm for two-dimensional rectangle packing area minimization problem with central rectangle, Computers & Industrial Engineering, 102 (2016), 208-218.  doi: 10.1016/j.cie.2016.10.011. [18] E. K. Burke, G. Kendall and G. Whitwell, A new placement heuristic for the orthogonal stock-cutting problem, Operations Research, 52 (2004), 655-671.  doi: 10.1287/opre.1040.0109.

Figures(7)

Tables(4)