Article Contents
Article Contents

# A hybrid chaos firefly algorithm for three-dimensional irregular packing problem

• * Corresponding author: Lin Jiang
The first author is supported by NSFC grant (61871412, 61772034, 61572036, 61672039, 61473326), Anhui Provincial Natural Science Foundation(1708085MF156, 1808085MF172), Australian Research Council Linkage Program LP140100873.
• The packing problem study how to pack multiple objects without overlap. Various exact and approximate algorithms have been developed for two-dimensional regular and irregular packing as well as three-dimensional bin packing. However, few results are reported for three-dimensional irregular packing problems. This paper will develop a method for solving three-dimensional irregular packing problems. A three-grid approximation technique is first introduced to approximate irregular objects. Then, a hybrid heuristic method is developed to place and compact each individual objects where chaos search is embedded into firefly algorithm in order to enhance the algorithm's diversity for optimizing packing sequence and orientations. Results from several computational experiments demonstrate the effectiveness of the hybrid algorithm.

Mathematics Subject Classification: Primary: 80M50; Secondary: 90C27.

 Citation:

• Figure 1.  Grid representation of a cylinder

Figure 2.  Encoding of the firefly individual

Figure 3.  A procedure of back bottom left placement for 3D irregular packing

Figure 4.  Architecture of the chaos firefly algorithm for packing problem

Figure 5.  An example of comparison between random sequence packing result and optimized sequence packing result

Figure 6.  The comparison packing result of instance 6 without rotation

Figure 7.  The comparison packing result of instance 8 with rotation

Figure 8.  Algorithm convergence over 9 instances

Table 1.  Data sets specification

 Instance Type Number Rotation Object scale 1 cylinder 1 50 0 ${50^ * }{50^ * }50$ 2 cylinder 2 80 0 ${50^ * }{50^ * }50$ 3 cylinder 3 100 0 ${50^ * }{50^ * }50$ 4 irregular 1 (cylinder, complex structure) 50 0 ${50^ * }{50^ * }50$ 5 irregular 2 (cylinder, complex structure) 80 0 ${50^ * }{50^ * }50$ 6 irregular 3 (cylinder, complex structure) 100 0 ${50^ * }{50^ * }50$ 7 irregular 4 (cylinder, complex structure) 40 0, 3 ${50^ * }{50^ * }50$ 8 irregular 5 (cylinder, complex structure) 60 0, 3 ${50^ * }{50^ * }50$ 9 irregular 6 (cylinder, complex structure) 80 0, 3 ${50^ * }{50^ * }50$

Table 2.  Parameters of the hybrid firefly algorithm

 Parameter Value population size $number\times$(1+$r_{max}$) $T_0$ 0.064 Temperature update ratio 1.6 Iteration 300

Table 3.  The maximal height and the efficiency achieved by three algorithms in 10 runs

 Instance GA PSO FA HFA Height efficiency Height efficiency Height efficiency Height efficiency 1 122 52.5% 120 55.4% 117 56.8% 120 55.4% 2 169 68.0% 171 67.2% 170 67.6% 167 68.8% 3 222 64.0% 219 64.9% 221 64.4% 219 64.9% 4 210 50.1% 207 50.8% 215 48.9% 198 53.1% 5 366 53.3% 363 54.3% 365 53.4% 356 55.4% 6 446 51.8% 439 52.6% 448 51.5% 442 52.2% 7 160 59.9% 160 59.9% 161 59.6% 157 61.1% 8 230 61.0% 231 60.7% 234 59.9% 225 62.3% 9 310 58.9% 308 59.3% 304 60.1% 304 60.1%

Table 4.  The statistical performance of the algorithm without rotation

 Ins. GA PSO FA HFA Best Avg Stdev Best Avg Stdev Best Avg Stdev Best Avg Stdev 1 120 122.1 2.172 120 121.3 1.341 117 120.8 2.049 120 120.3 0.547 2 171 172.5 2.918 171 172.1 2.121 170 172.5 3.140 167 170 2.387 3 220 224.6 2.671 219 223.1 1.923 221 222.3 2.100 219 221.2 1.483 4 210 219.8 3.019 207 218.6 2.074 215 220.9 8.648 198 215.2 6.638 5 362 371.1 4.017 363 371.4 6.058 365 368.8 6.025 356 365.5 2.191 6 445 465.2 8.423 439 461.2 8.820 448 459.4 9.597 442 452 4.264 7 162 168.1 9.150 160 168.2 9.517 161 167.6 8.961 157 162.9 4.868 8 232 245.1 6.901 231 242 7.615 234 244.2 3.421 225 234.2 2.863 9 311 314.6 6.119 308 313.8 5.354 304 316.2 7.190 304 307.6 3.050

Table 5.  Comparison between the proposed approach and placement strategy

 Instance enclosure without rotation enhance(%) with rotation enhance(%) 1 124.2 120.3 3.14% N/A N/A 2 173.4 170.0 1.96% N/A N/A 3 225.3 221.2 1.82% N/A N/A 4 225.2 215.2 4.44% 210.2 2.32% 5 381.6 365.5 4.40% 358.3 1.97% 6 466.3 452.0 3.16% 445.9 1.35% 7 170.9 162.9 4.68% 156.4 3.99% 8 246.0 234.2 4.80% 230.6 1.54% 9 319.6 307.6 3.90% 301.7 1.92%

Figures(8)

Tables(5)