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.