American Institute of Mathematical Sciences

January  2020, 16(1): 409-429. doi: 10.3934/jimo.2018160

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

 1 School of Computer Sciences and information, Anhui Normal University, Anhui Provincial Key Laboratory of Network and Information Security, Wuhu, 241000, China 2 Department of Mathematics and Statistics, Curtin University, Perth, WA 6845, Australia

* Corresponding author: Lin Jiang

Received  March 2017 Revised  April 2018 Published  October 2018

Fund Project: 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.

Citation: Chuanxin Zhao, Lin Jiang, Kok Lay Teo. A hybrid chaos firefly algorithm for three-dimensional irregular packing problem. Journal of Industrial & Management Optimization, 2020, 16 (1) : 409-429. doi: 10.3934/jimo.2018160
References:

show all references

References:
Grid representation of a cylinder
Encoding of the firefly individual
A procedure of back bottom left placement for 3D irregular packing
Architecture of the chaos firefly algorithm for packing problem
An example of comparison between random sequence packing result and optimized sequence packing result
The comparison packing result of instance 6 without rotation
The comparison packing result of instance 8 with rotation
Algorithm convergence over 9 instances
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$
 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$
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
 Parameter Value population size $number\times$(1+$r_{max}$) $T_0$ 0.064 Temperature update ratio 1.6 Iteration 300
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%
 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%
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
 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
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%
 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%
 [1] Mohamed A. Tawhid, Ahmed F. Ali. An effective hybrid firefly algorithm with the cuckoo search for engineering optimization problems. Mathematical Foundations of Computing, 2018, 1 (4) : 349-368. doi: 10.3934/mfc.2018017 [2] Maolin Cheng, Mingyin Xiang. Application of a modified CES production function model based on improved firefly algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019018 [3] Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142 [4] Mao Chen, Xiangyang Tang, Zhizhong Zeng, Sanya Liu. An efficient heuristic algorithm for two-dimensional rectangular packing problem with central rectangle. Journal of Industrial & Management Optimization, 2020, 16 (1) : 495-510. doi: 10.3934/jimo.2018164 [5] Leong-Kwan Li, Sally Shao. Convergence analysis of the weighted state space search algorithm for recurrent neural networks. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 193-207. doi: 10.3934/naco.2014.4.193 [6] Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015 [7] Kien Ming Ng, Trung Hieu Tran. A parallel water flow algorithm with local search for solving the quadratic assignment problem. Journal of Industrial & Management Optimization, 2019, 15 (1) : 235-259. doi: 10.3934/jimo.2018041 [8] Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008 [9] Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial & Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11 [10] Abdel-Rahman Hedar, Ahmed Fouad Ali, Taysir Hassan Abdel-Hamid. Genetic algorithm and Tabu search based methods for molecular 3D-structure prediction. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 191-209. doi: 10.3934/naco.2011.1.191 [11] Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703 [12] Leong-Kwan Li, Sally Shao, K. F. Cedric Yiu. Nonlinear dynamical system modeling via recurrent neural networks and a weighted state space search algorithm. Journal of Industrial & Management Optimization, 2011, 7 (2) : 385-400. doi: 10.3934/jimo.2011.7.385 [13] Behrad Erfani, Sadoullah Ebrahimnejad, Amirhossein Moosavi. An integrated dynamic facility layout and job shop scheduling problem: A hybrid NSGA-II and local search algorithm. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-34. doi: 10.3934/jimo.2019030 [14] David Julitz. Numerical approximation of atmospheric-ocean models with subdivision algorithm. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 429-447. doi: 10.3934/dcds.2007.18.429 [15] Zhenbo Wang. Worst-case performance of the successive approximation algorithm for four identical knapsacks. Journal of Industrial & Management Optimization, 2012, 8 (3) : 651-656. doi: 10.3934/jimo.2012.8.651 [16] Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 [17] Tao Zhang, Yue-Jie Zhang, Qipeng P. Zheng, P. M. Pardalos. A hybrid particle swarm optimization and tabu search algorithm for order planning problems of steel factories based on the Make-To-Stock and Make-To-Order management architecture. Journal of Industrial & Management Optimization, 2011, 7 (1) : 31-51. doi: 10.3934/jimo.2011.7.31 [18] Meng Yu, Jack Xin. Stochastic approximation and a nonlocally weighted soft-constrained recursive algorithm for blind separation of reverberant speech mixtures. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1753-1767. doi: 10.3934/dcds.2010.28.1753 [19] Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117 [20] Jinling Wei, Jinming Zhang, Meishuang Dong, Fan Zhang, Yunmo Chen, Sha Jin, Zhike Han. Applications of mathematics to maritime search. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 957-968. doi: 10.3934/dcdss.2019064

2018 Impact Factor: 1.025

Tools

Article outline

Figures and Tables