Orthogonal Rectangular Strip Packing Problem
Cutting and packing a given stock material are crucial processes in manufacturing and producing. Paper, plastic, wood, glass, steel and leather are some of the most commonly used stock materials in the industries. Different types of cutting and packing problems arise due to the nature of the stock material, such as different constraints and objectives. Orthogonal Rectangular Strip Packing Problem (SPP) involves in finding the best orthogonal placement of a set of rectangles with given widths and heights in a suitable orientation on a strip of rectangular stock sheet with a fixed width and an infinite height. Orthogonal placement requires the sides of the rectangles to be parallel to the edges of the strip. Based on the recent categorization of the cutting and packing problems provided by Waescher, Haussner and Schumann (2007), SPP is identified as two-dimensional, open dimension problem.
Bidirectional Best-fit Heuristic for Orthogonal Rectangular Strip Packing
Önder Barış Aşık, Ender Özcan
(Under Review)
If the rotation of rectangles by 90-degrees is allowed and guillotine cutting (edge-to-edge) is not required as constraints during the placement process, this type of problems is referred to as RF subtype. In this study, a new heuristic is presented for solving orthogonal rectangular strip packing problem of RF subtype: Bidirectional Best-fit Heuristic (BBF). BBF achieves better results than the existing heuristics and delivers a better or matching performance as compared to the most of the previously proposed meta-heuristics for solving RF-SPPs.
Experimental Data
|
Data source |
Problem(s) |
Optimal height |
|
Pinto and Oliveira (2005) |
PO1 |
600 |
|
|
PO2 |
|
|
|
PO3 |
|
|
|
PO4 |
|
|
|
PO5 |
|
|
|
PO6 |
|
|
|
PO7 |
|
|
Burke, Kendall and Whitwell (2004) |
N1 |
40 |
|
|
N2 |
50 |
|
|
N3 |
50 |
|
|
N4 |
80 |
|
|
N5 |
100 |
|
|
N6 |
100 |
|
|
N7 |
100 |
|
|
N8 |
80 |
|
|
N9 |
150 |
|
|
N10 |
150 |
|
|
N11 |
150 |
|
|
N12 |
300 |
|
|
N13 |
960 |
|
Valenzuela and Wang (2001) |
VN1, VP1 |
100 |
|
|
VN2, VP2 |
|
|
|
VN3, VP3 |
|
|
|
VN4, VP4 |
|
|
|
VN5, VP5 |
|
|
|
VN6, VP6 |
|
|
Hopper and Turton (2001a) |
C1P1 |
20 |
|
C1 |
C1P2 |
|
|
|
C1P3 |
|
|
C2 |
C2-P1, P2, P3 |
15 |
|
|
C3P1 |
30 |
|
C3 |
C3P2 |
|
|
|
C3P3 |
|
|
C4 |
C4-P1, P2, P3 |
60 |
|
|
C5P1 |
90 |
|
C5 |
C5P2 |
|
|
|
C5P3 |
|
|
C6 |
C6-P1, P2, P3 |
120 |
|
|
C7P1 |
240 |
|
C7 |
C7P2 |
|
|
|
C7P3 |
|
|
Hopper (2000) |
H1 |
200 |
|
Explanation: There are 5 problem instances in each problem category |
H2 |
|
|
H3 |
||
|
H4 |
||
|
|
H5 |
|
|
|
H6 |
|
|
|
H7 |
|
|
Ramesh Babu and Ramesh Babu (1999) |
RB |
375 |
|
Jakobs (1996) |
J1 |
15 |
|
|
J2 |
Comparison of BBF to some previous heuristics
The proposed heuristic either improves the solutions or generates a tie for all problem instances obtained from the previous heuristics.
Table A HR: heuristic of Zhang, Kang and Deng (2006), BL: bottom left, BLF: bottom left fill, D-W: decreasing – width, BLD* : Lesh et al. (2005)
Hopper and Turton data set, %-gap
|
label |
no. of shapes |
BL |
BL-DW |
BL-DH |
BLF |
BLF-DW |
BLF-DH |
BBF |
HR |
|
C1P1 |
16 |
45 |
30 |
15 |
30 |
10 |
10 |
0 |
|
|
C1P2 |
17 |
40 |
20 |
10 |
35 |
15 |
10 |
5 |
|
|
C1P3 |
16 |
35 |
20 |
5 |
25 |
15 |
5 |
5 |
|
|
C1 |
avr |
40.0 |
23.3 |
10.0 |
30.0 |
13.3 |
8.3 |
3.3 |
8.3 |
|
C2P1 |
25 |
53 |
13 |
13 |
47 |
13 |
13 |
6.7 |
|
|
C2P2 |
25 |
80 |
27 |
73 |
73 |
20 |
73 |
6.7 |
|
|
C2P3 |
25 |
67 |
27 |
13 |
47 |
20 |
13 |
0 |
|
|
C2 |
avr |
66.7 |
22.3 |
33.0 |
55.7 |
17.7 |
33.0 |
4.4 |
4.5 |
|
C3P1 |
28 |
40 |
10 |
10 |
37 |
10 |
10 |
0 |
|
|
C3P2 |
29 |
43 |
20 |
10 |
50 |
13 |
6.7 |
10 |
|
|
C3P3 |
28 |
40 |
17 |
13 |
33 |
13 |
13 |
3.3 |
|
|
C3 |
avr |
41.0 |
15.7 |
11.0 |
40.0 |
12.0 |
9.9 |
4.4 |
6.7 |
|
C4P1 |
49 |
32 |
17 |
12 |
25 |
10 |
10 |
3.3 |
|
|
C4P2 |
49 |
37 |
22 |
13 |
25 |
5 |
5 |
3.3 |
|
|
C4P3 |
49 |
30 |
22 |
6.7 |
27 |
10 |
5 |
1.7 |
|
|
C4 |
avr |
33.0 |
20.33 |
10.57 |
25.67 |
8.33 |
6.7 |
2.8 |
2.2 |
|
C5P1 |
72 |
27 |
16 |
4.4 |
20 |
5.6 |
4.4 |
1.1 |
|
|
C5P2 |
73 |
32 |
18 |
10 |
23 |
6.7 |
5.6 |
2.2 |
|
|
C5P3 |
72 |
30 |
13 |
7.8 |
21 |
5.6 |
4.4 |
1.1 |
|
|
C5 |
avr |
29.7 |
15.7 |
7.4 |
21.3 |
6.0 |
4.8 |
1.5 |
1.9 |
|
C6P1 |
97 |
33 |
22 |
8.3 |
20 |
5 |
5 |
1.7 |
|
|
C6P2 |
97 |
39 |
25 |
8.3 |
18 |
4.2 |
2.5 |
0.8 |
|
|
C6P3 |
97 |
34 |
18 |
9.2 |
21 |
4.2 |
6.7 |
1.7 |
|
|
C6 |
avr |
35.3 |
21.7 |
8.6 |
19.7 |
4.5 |
4.7 |
1.4 |
2.5 |
|
C7P1 |
196 |
22 |
16 |
5 |
15 |
4.6 |
3.8 |
1.2 |
|
|
C7P2 |
197 |
41 |
19 |
10 |
20 |
3.3 |
2.9 |
1.7 |
|
|
C7P3 |
196 |
31 |
17 |
7.1 |
17 |
2.9 |
3.8 |
1.7 |
|
|
C7 |
avr |
31.3 |
17.3 |
7.4 |
17.3 |
3.6 |
3.5 |
1.5 |
1.8 |
|
label |
no. of shapes |
Optimum |
BBF |
BL |
|
PO1 |
50 |
|
7.2 |
12.3 |
|
PO2 |
100 |
|
7.5 |
13.2 |
|
PO3 |
500 |
|
3.0 |
15.3 |
|
PO4 |
1,000 |
600 |
0.0 |
15.0 |
|
PO5 |
5,000 |
|
0.0 |
14.5 |
|
PO6 |
10,000 |
|
0.0 |
13.5 |
|
PO7 |
15,000 |
|
0.0 |
10.0 |
|
|
|
|
2.5 |
13.4 |
|
|
no. of |
|
BBF |
|
|
|
BLD* |
|
|
label |
shapes |
optimum |
|
Mean |
Best |
|
60 s |
3600 s |
|
H1 |
17 |
|
|
8.3 |
6.0 |
|
6.0 |
4.5 |
|
H2 |
25 |
|
|
8.0 |
6.5 |
|
6.4 |
4.7 |
|
H3 |
29 |
|
|
7.3 |
5.0 |
|
6.0 |
4.6 |
|
H4 |
49 |
200 |
|
4.5 |
2.5 |
|
5.1 |
3.9 |
|
H5 |
73 |
|
|
4.7 |
3.5 |
|
4.6 |
4.0 |
|
H6 |
97 |
|
|
2.9 |
2.5 |
|
4.0 |
3.0 |
|
H7 |
197 |
|
|
1.6 |
1.5 |
|
2.3 |
1.8 |
|
|
|
|
|
avr |
3.9 |
|
4.9 |
3.8 |
Comparison of BBF to BF
BBF outperforms the best fit heuristic. This performance variation is also statistically significant within a confidence interval of 99.99%.
Table B
|
label |
BBF result |
BF result |
%-impr. |
|
M1 |
9 |
13 |
%-impr. |
|
N1 |
40 |
45 |
30.77 |
|
N2 |
52 |
53 |
11.11 |
|
N3 |
52 |
52 |
1.89 |
|
N4 |
82 |
83 |
0.00 |
|
N5 |
104 |
105 |
1.20 |
|
N6 |
102 |
103 |
0.95 |
|
N7 |
106 |
107 |
0.97 |
|
N8 |
82 |
84 |
0.93 |
|
N9 |
152 |
152 |
2.38 |
|
N10 |
151 |
152 |
0.00 |
|
N11 |
151 |
152 |
0.66 |
|
N12 |
303 |
306 |
0.66 |
|
N13 |
964 |
964 |
0.98 |
|
C1P1 |
20 |
21 |
0.00 |
|
C1P2 |
21 |
22 |
4.76 |
|
C1P3 |
21 |
24 |
4.55 |
|
C2P1 |
16 |
16 |
12.50 |
|
C2P2 |
16 |
16 |
0.00 |
|
C2P3 |
15 |
16 |
0.00 |
|
C3P1 |
30 |
32 |
6.25 |
|
C3P2 |
33 |
34 |
6.25 |
|
C3P3 |
31 |
33 |
2.94 |
|
C4P1 |
62 |
63 |
6.06 |
|
C4P2 |
62 |
62 |
1.59 |
|
C4P3 |
61 |
62 |
0.00 |
|
C5P1 |
91 |
93 |
1.61 |
|
C5P2 |
92 |
92 |
2.15 |
|
C5P3 |
91 |
93 |
0.00 |
|
C6P1 |
122 |
123 |
2.15 |
|
C6P2 |
121 |
122 |
0.81 |
|
C6P3 |
122 |
124 |
0.82 |
|
C7P1 |
243 |
247 |
1.61 |
|
C7P2 |
244 |
244 |
1.62 |
|
C7P3 |
244 |
245 |
0.00 |
|
VN1 |
1073 |
1074 |
0.41 |
|
VN2 |
1080 |
1085 |
0.09 |
|
VN3 |
1069 |
1070 |
0.46 |
|
VN4 |
1056 |
1053 |
0.09 |
|
VN5 |
1031 |
1035 |
- |
|
VN6 |
1036 |
1037 |
0.39 |
|
VP1 |
1093 |
1101 |
0.10 |
|
VP2 |
1074 |
1138 |
0.73 |
|
VP3 |
1080 |
1073 |
5.62 |
|
VP4 |
1053 |
1041 |
- |
|
VP5 |
1031 |
1037 |
- |
|
VP6 |
1026 |
1028 |
0.58 |
|
RB |
400 |
400 |
0.19 |
Comparison of BBF to the meta-heuristics
GA+BL: Jakobs (1996)
GA+iBL : Liu and Teng (1999)
SA/GA+BLF : Hopper and Turton (2001a)
SA/GA+BLF : Burke et al. (2004)
vGRASP: Beltrán et al. (2004)
SPGAL: Bortfeldt (2006)
rGRASP: Alvarez-Valdes et al. (2006)
BBF: proposed approach
Imahori et al. (2005) employed iterated local search for solving RF-SPPs. According to their results, iterated local search improves SA+BLF by %0.49 based on their evaluation scheme, whereas BBF performs slightly better with a %0.75 improvement over SA+BLF based on average %-gap considering Hopper and Turton problem instances. The results show that BBF performs better than six older meta-heuristics. Burke et al. (2006) experimented with a multistage scheme. BF is executed for a predetermined number of rectangles, and then a meta-heuristic with BLF decoder is invoked. Different meta-heuristics are tested, namely; GA, SA and tabu search (TS). This scheme yielded a better performance as compared to BF. For all data sets in Table 5, excluding M1, BF-GA+BLF, BF-TS+BLF and BF-SA+BLF returns an average gap of 3.61%, 3.29% and 2.86%, respectively. BBF with an average gap of 3.54% performs slightly better than BF-GA+BLF and slightly worse than the others, yet we can say that it has a comparable performance to these approaches.
Table C Performance comparison based on %-gap.
|
label |
BBF |
GA+BL |
GA+iBL |
|
J1 |
6.7 |
13.3 |
6.7 |
|
J2 |
6.7 |
13.3 |
6.7 |
|
|
|
Hopper |
|
|
Burke |
|
|
|
|
label |
BBF |
GA+BLF |
SA+BLF |
vGRASP |
GA+BLF |
SA+BLF |
SPGAL |
rGRASP |
|
C1 |
3.33 |
4 |
4 |
14.40 |
1.7 |
1.7 |
1.7 |
0.00 |
|
C2 |
4.44 |
7 |
6 |
17.33 |
6.7 |
6.7 |
0.0 |
0.00 |
|
C3 |
4.44 |
5 |
5 |
12.93 |
6.7 |
6.7 |
2.2 |
1.08 |
|
C4 |
2.78 |
3 |
3 |
6.80 |
5.0 |
6.1 |
0.0 |
1.64 |
|
C5 |
1.48 |
4 |
3 |
4.51 |
5.6 |
5.2 |
0.0 |
1.10 |
|
C6 |
1.39 |
4 |
3 |
3.55 |
5.3 |
5.3 |
0.3 |
0.83 |
|
C7 |
1.53 |
5 |
4 |
2.89 |
5.6 |
6.0 |
0.3 |
1.23 |
|
avr |
2.77 |
4.57 |
4.00 |
8.92 |
5.20 |
5.36 |
0.64 |
0.84 |
|
label |
no. of shapes |
rGRASP |
BBF |
|
PO1 |
50 |
2.83 |
7.17 |
|
PO2 |
100 |
2.83 |
7.50 |
|
PO3 |
500 |
0.83 |
3.00 |
|
PO4 |
1,000 |
0.33 |
0.00 |
|
PO5 |
5,000 |
0.00 |
0.00 |
|
PO6 |
10,000 |
0.00 |
0.00 |
|
PO7 |
15,000 |
0.00 |
0.00 |
|
|
avr |
0.98 |
2.52 |
References
Alvarez-Valdes, R., Parreno, F. & Tamarit, J.M. (2008). Reactive GRASP for the strip-packing problem. Computers and Operations Research, 35, 1065–1083.
Beltrán, J. D., Calderón, J. E. , Cabrera, R. J. , Moreno-Pérez, J. A., & Moreno-Vega, J. M. (2004). GRASP-VNS hybrid for the Strip Packing Problem. Proc. of the workshop on Hybrid Metaheuristics (pp. 79–90).
Bortfeld, A. (2006). A genetic algorithm fot the two-dimensional strip packing problem with rectangular pieces. Eur J Oper Res, 172, 814–837.
Burke, E. K., Kendall, G., & Whitwell, G. (2004). A new placement heuristic for the orthogonal stock-cutting problem. Operations Research, 52(4), 655–671.
Burke, E. K., Kendall, G., & Whitwell, G. (2006). Metaheuristic enhancements of the best-fit heuristic for the orthogonal stock cutting problem computer science. Technical Report No NOTTCS-TR-2006-3.
Hopper, E. (2000). Two-dimensional packing utilising evolutionary algorithms and other meta-heuristic methods, PhD thesis, Cardiff University, School of Engineering.
Hopper, E., & Turton, B. C. H. (2001a). An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem. Eur J Oper Res, 128, 34–57.
Imahori, S., Yagiura, M., & Ibaraki, T. (2005). Improved local search algorithms for the rectangle packing problem with general spatial costs. Eur J Oper Res, 167, 48–67.
Jakobs, S. (1996). On genetic algorithms for the packing of polygons. Eur J Oper Res,88,165–181.
Liu, D., & Teng, H. (1999). An improved bottom left algorithm for genetic algorithm of the orthogonal packing of rectangle. Eur J Oper Res, 112, 413–419.
Pinto, E., & Oliveira, J. F. (2005). Algorithm based on graphs for the non-guillotinable two-dimensional packing problem, 2nd ESICUP Meeting, Southampton.
Ramesh Babu, A., & Ramesh Babu, N. (1999). Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms. Int J Production Res, 37(7), 1625–1643.
Valenzuela, C. L., & Wang, P. Y. (2001). Heuristics for large strip packing problems with guillotine patterns: An empirical study. Proceedings of the 4th Metaheuristics Int. Conf., University of Porto, Porto, Portugal (pp. 417–421).
Waescher, G., Haussner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. Eur J Oper Res, 183, 1109–1130.