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

Chuanxin Zhao; Lin Jiang; Kok Lay Teo

doi:10.3934/jimo.2018160

Article Contents

2020, Volume 16, Issue 1: 409-429. Doi: 10.3934/jimo.2018160

This issue Previous Article A $p$-spherical section property for matrix Schatten-$p$ quasi-norm minimization Next Article A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids

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
* Corresponding author: Lin Jiang

Received: February 28, 2017

Revised: March 31, 2018

Early access: October 2018

Published: October 2019

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.

Abstract Full Text(HTML) Figure(8) / Table(5) Related Papers Cited by

Abstract

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.

Keywords:

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

Citation:

Full Text(HTML)

Figure 1. Grid representation of a cylinder

Download: Full-size image PowerPoint slide

Figure 2. Encoding of the firefly individual

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

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

Download: Full-size image PowerPoint slide

Figure 8. Algorithm convergence over 9 instances

Download: Full-size image PowerPoint slide

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$

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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


Instance	GA		PSO		FA		HFA
Instance	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%

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

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%

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	Y. Abdelsadek, F. Herrmann, I. Kacem and B. Otjacques, Branch-and-bound algorithm for the maximum triangle packing problem, Computers & Industrial Engineering, 81 (2015), 147-157. doi: 10.1016/j.cie.2014.12.006.
[2]	R. Alvarez-Valdes, A. Martinez and J. M. Tamarit, A branch and bound algorithm for cutting and packing irregularly shaped pieces, Computers & Operations Research, 145 (2013), 463-477. doi: 10.1016/j.ijpe.2013.04.007.
[3]	I. Araya and M. C. Riff, A beam search approach to the container loading problem, Computers & Operations Research, 43 (2014), 100-107. doi: 10.1016/j.cor.2013.09.003.
[4]	T. Back, Evolutionary algorithms in theory and practice: Evolution strategies, evolutionary programming, genetic algorithms, The Clarendon Press, Oxford University Press, New York, 1996.
[5]	J. C. Bean, Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6 (1994), 150-160. doi: 10.1287/ijoc.6.2.154.
[6]	E. K. Burke, R. S. R. Hellier, G. Kendall and G. Whitwell, Irregular packing using the line and arc no-fit polygon, Operations Research, 58 (2010), 948-970. doi: 10.1287/opre.1090.0770.
[7]	P. Chen, Z. Fu, A. Lim and B. Rodrigues, The two dimensional packing problem for irregular objects, International Journal on Artificial Intelligent Tools, 13 (2004), 429-448. doi: 10.1142/S0218213004001624.
[8]	N. Chernov, Y. Stoyan and T. Romanova, Mathematical model and efficient algorithms for object packing problem, Computational Geometry, 43 (2010), 535-553. doi: 10.1016/j.comgeo.2009.12.003.
[9]	D. Cinar, J. A. Oliveira, Y. I. Topcu and P. M. Pardalos, A priority-based genetic algorithm for a flexible job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 1391-1415. doi: 10.3934/jimo.2016.12.1391.
[10]	L. D. S. Coelho and V. C. Mariani, Firefly algorithm approach based on chaotic Tinkerbell map applied to multivariable PID controller tuning, Computers & Mathematics with Applications, 64 (2012), 2371-2382. doi: 10.1016/j.camwa.2012.05.007.
[11]	T. Dereli and G. S. Das, A hybrid 'bee(s) algorithm' for solving container loading problems, Applied Soft Computing, 11 (2011), 2854-2862. doi: 10.1016/j.asoc.2010.11.017.
[12]	T. Dokeroglu and A. Cosar, Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms, Computers & Industrial Engineering, 75 (2014), 176-186. doi: 10.1016/j.cie.2014.06.002.
[13]	A. Elkeran, A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering, European Journal of Operational Research, 231 (2013), 757-769. doi: 10.1016/j.ejor.2013.06.020.
[14]	I. Fister, S. M. Kamal and I. Fister, A review of chaos-based firefly algorithms: Perspectives and research challenges, Applied Mathematics and Computation, 252 (2015), 155-165. doi: 10.1016/j.amc.2014.12.006.
[15]	J. F. Gonçalves and M. G. Resende, A biased random key genetic algorithm for 2D and 3D bin packing problems, International Journal of Production Economics, 145 (2013), 500-510.
[16]	H. Hasni and H. Sabri, On a hybrid Genetic Algorithm for solving the container loading problem with no orientation constraints, Journal of Mathematical Modelling and Algorithms in Operations Research, 12 (2013), 67-84.
[17]	W. Huang and K. He, A new heuristic algorithm for cuboids packing with no orientation constraints, Computers & Operations Research, 36 (2009), 425-432. doi: 10.1016/j.cor.2007.09.008.
[18]	R. Karmakar and S. Chattopadhyay, Window-based peak power model and Particle Swarm Optimization guided 3-dimensional bin packing for SoC test scheduling, Integration, the VLSI Journal, 50 (2015), 61-73. doi: 10.1016/j.vlsi.2015.01.006.
[19]	P. Laxmi, S. Indira and K. Jyothsna, Ant colony optimization for optimum service times in a Bernoulli schedule vacation interruption queue with balking and reneging, Journal of Industrial and Management Optimization, 12 (2016), 1199-1214. doi: 10.3934/jimo.2016.12.1199.
[20]	T. W. Leung, K. C. Chi and M. D. Troutt, A mixed simulated annealing-genetic algorithm approach to the multi-buyer multi-item joint replenishment problem: advantages of meta-heuristics, Journal of Industrial and Management Optimization, 4 (2008), 53-66. doi: 10.3934/jimo.2008.4.53.
[21]	S. C. H. Leung, Y. Lin and D. Zhang, Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem, Computers & Operations Research, 39 (2012), 678-686. doi: 10.1016/j.cor.2011.05.025.
[22]	Y. K. Lin and C. S. Chong, A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem, Journal of Industrial and Management Optimization, 12 (2016), 703-717. doi: 10.3934/jimo.2016.12.703.
[23]	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.
[24]	Q. Long and C. Wu, A hybrid method combining genetic algorithm and Hooke-Jeeves method for constrained global optimization, Journal of Industrial and Management Optimization, 10 (2014), 1279-1296. doi: 10.3934/jimo.2014.10.1279.
[25]	Q. Long, C. Wu, T. Huang and X. Wang, A genetic algorithm for unconstrained multi-objective optimization, Swarm and Evolutionary Computation, 22 (2015), 1-14. doi: 10.1016/j.swevo.2015.01.002.
[26]	S. Martello and M. Monaci, Models and algorithms for packing rectangles into the smallest square, Computers & Operations Research, 63 (2015), 161-171. doi: 10.1016/j.cor.2015.04.024.
[27]	A. Moura and J. F. Oliveira, Optimization of one-dimensional Bin Packing Problem with island parallel grouping genetic algorithms, Computers & Industrial Engineering, 75 (2014), 176-186.
[28]	E. Osaba, X. S. Yang, F. Diaz, E. Onieva, A. D. Masegosa and A. Perallos, A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy, Soft Computing, 21 (2017), 5295-5308. doi: 10.1007/s00500-016-2114-1.
[29]	J. Senthilnath, S. N. Omkar and V. Mani, Clustering using firefly algorithm: Performance study, Swarm and Evolutionary Computation, 1 (2011), 164-171. doi: 10.1016/j.swevo.2011.06.003.
[30]	S. Tao, C. Wu, Z. Sheng and X. Wang, Stochastic Project Scheduling with Hierarchical Alternatives, Applied Mathematical Modelling, 58 (2018), 181-202. doi: 10.1016/j.apm.2017.09.015.
[31]	S. Tao, C. Wu, Z. Sheng and X. Wang, Space-Time Repetitive Project Scheduling Considering Location and Congestion, Journal of Computing in Civil Engineering, 32 (2018), 04018017. doi: 10.1061/(ASCE)CP.1943-5487.0000745.
[32]	H. Terashima-Marín, P. Ross, C. J. Farías-Zárate, E. López-Camacho and M. Valenzuela-Rendón, Generalized hyper-heuristics for solving 2D Regular and irregular Packing Problems, Annals of Operations Research, 179 (2010), 369-392. doi: 10.1007/s10479-008-0475-2.
[33]	A. Trivella and D. Pisinger, The load-balanced multi-dimensional bin-packing problem, Computers & Operations Research, 74 (2014), 152-164. doi: 10.1016/j.cor.2016.04.020.
[34]	W. K. Wong, X. X. Wang, P. Y. Mok, S. Y. S. Leung and C. K. Kwong, Solving the two-dimensional irregular objects allocation problems by using a two-stage packing approach, Expert Systems with Applications, 36 (2009), 3489-3496. doi: 10.1016/j.eswa.2008.02.068.
[35]	X. S. Yang, Swarm-based metaheuristic algorithms and no-free-lunch theorems, in Theory and New Applications of Swarm Intelligence(Eds. R. Parpinelli and H. S.Lopes), Intech Open Science, 192 (2012), 1-2. doi: 10.1016/j.ins.2012.02.002.
[36]	X. S. Yang and X. He, Firefly algorithm: Recent advances and applications, International Journal of Swarm Intelligence, 1 (2013), 36-50. doi: 10.1504/IJSI.2013.055801.
[37]	M. A. Zaman and M. A. Matin, Nonuniformly spaced linear antenna array design using firefly algorithm, International Journal of Microwave Science and Technology, 2012 (2012), Article ID 256759, 8 pages. doi: 10.1155/2012/256759.
[38]	C. Zhao, C. Wu, J. Chai, X. Wang, X. Yang and J. M. Lee, et al., Decomposition-based multi-objective firefly algorithm for RFID network planning with uncertainty, Applied Soft Computing, 55 (2017), 549-564.
[39]	C. Zhao, C. Wu, X. Wang, W. K. Ling, K. L.Teo and J. M. Lee, et al., Maximizing lifetime of a wireless sensor network via joint optimizing sink placement and sensor-to-sink routing, Applied Mathematical Modelling, 49 (2017), 319-337. doi: 10.1016/j.apm.2017.05.001.