Login Register Cart 0
Generic placeholder image

Recent Advances in Computer Science and Communications

Editor-in-Chief

ISSN (Print): 2666-2558
ISSN (Online): 2666-2566

Back
Journal Home About Journal Editorial Board Current Issue Volumes/Issues
Subscribe
Research Article

On Performance of Binary Flower Pollination Algorithm for Rectangular Packing Problem

Author(s): Amandeep K. Virk* and Kawaljeet Singh

Volume 13, Issue 1, 2020

Page: [22 - 34] Pages: 13

DOI: 10.2174/2213275911666181114143239

Price: $65

Abstract

Background: Metaheuristic algorithms are optimization algorithms capable of finding near-optimal solutions for real world problems. Rectangle Packing Problem is a widely used industrial problem in which a number of small rectangles are placed into a large rectangular sheet to maximize the total area usage of the rectangular sheet. Metaheuristics have been widely used to solve the Rectangle Packing Problem.

Objective: A recent metaheuristic approach, Binary Flower Pollination Algorithm, has been used to solve for rectangle packing optimization problem and its performance has been assessed.

Methods: A heuristic placement strategy has been used for rectangle placement. Then, the Binary Flower Pollination Algorithm searches the optimal placement order and optimal layout.

Result: Benchmark datasets have been used for experimentation to test the efficacy of Binary Flower Pollination Algorithm on the basis of utilization factor and number of bins used. The simulation results obtained show that the Binary Flower Pollination Algorithm outperforms in comparison to the other well-known algorithms.

Conclusion: BFPA gave superior results and outperformed the existing state-of-the-art algorithms in many instances. Thus, the potential of a new nature based metaheuristic technique has been discovered.

Keywords: Flower pollination algorithm, rectangle packing, non-guillotine cutting, heuristic, BLF, utilization factor.

Graphical Abstract

[1]
J. Kennedy, and R.C. Eberhart, "A discrete binary version of the particle swarm algorithm", In: IEEE International Conference on Systems, Man, Computational Cybernetics and Simulation, vol. 5. pp. 4104-4108. 1997
[2]
G. Pampará, and A.P. Engelbrecht, "Binary artificial bee colony optimization", In: IEEE symposium on Swarm Intelligence (SIS),., pp. 1-8. 2011
[3]
R. Falcon, M. Almeida, and A. Nayak, "Fault identification with binary adaptive fireflies in parallel and distributed systems", In: IEEE Congress on Evolutionary Computation (CEC), pp. 1359-1366. 2011
[4]
D. Rodrigues, "etal BCS: A binary cuckoo search algorithm for feature selection in Circuits and Systems (ISCAS), 2013 IEEE International Symposium on, ", pp. 465-468, 2013.
[5]
S. Sabba, and S. Chikhi, "A discrete binary version of bat algorithm for multidimensional knapsack problem", Int. J. Bio-inspired Comput., vol. 6, no. 2, pp. 140-152, 2014.
[6]
X.-S. Yang, "Flower pollination algorithm for global optimization", International conference on unconventional computing and natural computation, pp. 240-249. 2012
[7]
A. Lodi, S. Martello, and D. Vigo, "Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems", Inf. J. Comput., vol. 11, no. 4, pp. 345-357, 1999.
[8]
X.-S. Yang, M. Karamanoglu, and X. He, "Flower pollination algorithm: a novel approach for multiobjective optimization", Eng. Optim., vol. 46, no. 9, pp. 1222-1237, 2014.
[9]
D.F. Alam, D.A. Yousri, and M.B. Eteiba, "Flower pollination algorithm based solar PV parameter estimation", Energy Convers. Manage., vol. 101, pp. 410-422, 2015.
[10]
R. Prathiba, M.B. Moses, and S. Sakthivel, "Flower pollination algorithm applied for different economic load dispatch problems", Int. J. Eng. Technol., vol. 6, no. 2, pp. 1009-1016, 2014.
[11]
H.M. Dubey, M. Pandit, and B.K. Panigrahi, "A biologically inspired modified flower pollination algorithm for solving economic dispatch problems in modern power systems", Cognit. Comput., vol. 7, no. 5, pp. 594-608, 2015.
[12]
A.Y. Abdelaziz, E.S. Ali, and S.A. Elazim, "Combined economic and emission dispatch solution using flower pollination algorithm", Int. J. Electr. Power Energy Syst., vol. 80, pp. 264-274, 2016.
[13]
S. Lukasik, and P.A. Kowalski, "Study of flower pollination algorithm for continuous optimization", In: Intelligent Systems’ 2014., Springer, pp. 451-459. 2015
[14]
O. Abdel-Raouf, and M. Abdel-Baset, "“A new hybrid flower pollination algorithm for solving constrained global optimization problems”, Int. J. Appl. Oper. Res.-", Open Access J., vol. 4, no. 2, pp. 1-13, 2014.
[15]
O. Abdel-Raouf, I. El-Henawy, and M. Abdel-Baset, "A novel hybrid flower pollination algorithm with chaotic harmony search for solving sudoku puzzles", Int. J. Mod. Educ. Comput. Sci., vol. 6, no. 3, p. 38, 2014.
[16]
R. Wang, and Y. Zhou, Flower pollination algorithm with dimension by dimension improvement.Math. Probl. Eng., . Vol. 2014,2014.
[17]
E. Nabil, "A modified flower pollination algorithm for global optimization", Expert Syst. Appl., vol. 57, pp. 192-203, 2016.
[18]
M. Abdel-Baset, and I.M. Hezam, "An improved flower pollination algorithm for ratios optimization problems", Appl. Math. Inf. Sci. Lett. Int. J., vol. 3, no. 2, pp. 83-91, 2015.
[19]
R. Wang, Y. Zhou, S. Qiao, and K. Huang, "Flower pollination algorithm with bee pollinator for cluster analysis", Inf. Process. Lett., vol. 116, no. 1, pp. 1-14, 2016.
[20]
W. Zhang, Z. Qu, K. Zhang, W. Mao, Y. Ma, and X. Fan, "A combined model based on CEEMDAN and modified flower pollination algorithm for wind speed forecasting", Energy Convers. Manage., vol. 136, pp. 439-451, 2017.
[21]
D. Rodrigues, X-S. Yang, A.N. De Souza, and J.P. Papa, Binary flower pollination algorithm and its application to feature selection.in Recent advances in swarm intelligence and evolutionary computation.Springer, . pp. 85-100, 2015.
[22]
D. Rodrigues, G.F. Silva, J.P. Papa, A.N. Marana, and X-S. Yang, "EEG-based person identification through binary flower pollination algorithm", Expert Syst. Appl., vol. 62, pp. 81-90, 2016.
[23]
S.A-F. Sayed, E. Nabil, and A. Badr, "A binary clonal flower pollination algorithm for feature selection", Pattern Recognit. Lett., vol. 77, pp. 21-27, 2016.
[24]
Z.A.E.M. Dahi, C. Mezioud, and A. Draa, "On the efficiency of the binary flower pollination algorithm: application on the antenna positioning problem", Appl. Soft Comput., vol. 47, pp. 395-414, 2016.
[25]
C. Shilaja, and K. Ravi, "Optimization of emission/economic dispatch using euclidean affine flower pollination algorithm (eFPA) and binary FPA (BFPA) in solar photo voltaic generation", Renew. Energy, vol. 107, pp. 550-566, 2017.
[26]
B.S. Baker, E.G. Coffman, and R.L. Rivest, "Orthogonal packings in two dimensions", SIAM J. Comput., vol. 9, no. 4, pp. 846-855, 1980.
[27]
B. Chazelle, "The bottomn-left bin-packing heuristic: An efficient implementation", IEEE Trans. Comput., no. 8, pp. 697-707, 1983.
[28]
E.G. Coffman, M.R. Garey, and D.S. Johnson, Approximation algorithms for bin-packing—an updated survey. in Algorithm design for computer system design.Springer, . pp. 49-106, 1984.
[29]
D. Zhang, A. Deng, and Y. Kang, "A hybrid heuristic algorithm for the rectangular packing problem", In: International Conference on Computational Science. pp. 783-791, 2005.
[30]
D. Chen, and W. Huang, "A new heuristic algorithm for constrained rectangle-packing problem", Asia-Pac. J. Oper. Res., vol. 24, no. 04, pp. 463-478, 2007.
[31]
L. Wei, D. Zhang, and Q. Chen, "A least wasted first heuristic algorithm for the rectangular packing problem", Comput. Oper. Res., vol. 36, no. 5, pp. 1608-1614, 2009.
[32]
Y-P. Cui, Y. Cui, and T. Tang, "Sequential heuristic for the two-dimensional bin-packing problem", Eur. J. Oper. Res., vol. 240, no. 1, pp. 43-53, 2015.
[33]
E. Hopper, and B.C. Turton, "An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem", Eur. J. Oper. Res., vol. 128, no. 1, pp. 34-57, 2001.
[34]
D. Smith, "Bin packing with adaptive search", In: Proc. of the 1st International Conference on Genetic Algorithms and Their Applications. Pittsburgh PA, pp. 202-207, 1985.
[35]
S-M. Hwang, C-Y. Kao, and J-T. Horng, "On solving rectangle bin packing problems using genetic algorithms", In: Systems, Man,and Cybernetics, 1994. Humans, Information and Technology.,1994 IEEE International Conference on, . Vol. 2, pp. 1583-1590,1994.
[36]
S. Jakobs, "On genetic algorithms for the packing of polygons", Eur. J. Oper. Res., vol. 88, no. 1, pp. 165-181, 1996.
[37]
K.K. Lai, and J.W. Chan, "Developing a simulated annealing algorithm for the cutting stock problem", Comput. Ind. Eng., vol. 32, no. 1, pp. 115-127, 1997.
[38]
D. Liu, and H. Teng, "An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles1", Eur. J. Oper. Res., vol. 112, no. 2, pp. 413-420, 1999.
[39]
T.W. Leung, C.H. Yung, and C.K. Chan, Applications of genetic algorithm and simulated annealing to the 2-dimensional non-guillotine cutting stock problem. IFORS’99, 1999.
[40]
K.A. Dowsland, E.A. Herbert, G. Kendall, and E. Burke, "Using tree search bounds to enhance a genetic algorithm approach to two rectangle packing problems", Eur. J. Oper. Res., vol. 168, no. 2, pp. 390-402, 2006.
[41]
W. Chen, P. Zhai, H. Zhu, and Y. Zhang, "Hybrid algorithm for the two-dimensional rectangular layer-packing problem", J. Oper. Res. Soc., vol. 65, no. 7, pp. 1068-1077, 2014.
[42]
J. Błażewicz, P. Hawryluk, and R. Walkowiak, "Using a tabu search approach for solving the two-dimensional irregular cutting problem", Ann. Oper. Res., vol. 41, no. 4, pp. 313-325, 1993.
[43]
Y. Shigehiro, S. Koshiyama, and T. Masuda, "A New Approach to Rectangle Packing Problem Based on Stochastic Tabu Search", Trans. Soc. Instrum. Control Eng., vol. 40, no. 7, pp. 747-754, 2004.
[44]
V. Pureza, and R. Morabito, "Some experiments with a simple tabu search algorithm for the manufacturer’s pallet loading problem", Comput. Oper. Res., vol. 33, no. 3, pp. 804-819, 2006.
[45]
R. Alvarez-Valdés, F. Parreño, and J.M. Tamarit, "A tabu search algorithm for a two-dimensional non-guillotine cutting problem", Eur. J. Oper. Res., vol. 183, no. 3, pp. 1167-1182, 2007.
[46]
J.A. Bennell, and K.A. Dowsland, "Hybridising tabu search with optimisation techniques for irregular stock cutting", Manage. Sci., vol. 47, no. 8, pp. 1160-1172, 2001.
[47]
J-P. Hamiez, J. Robet, and J-K. Hao, "A tabu search algorithm with direct representation for strip packing", In: European Conference on Evolutionary Computation in Combinatorial Optimization. pp. 61-72, 2009.
[48]
C.H. Dagli, and A. Hajakbari, "Simulated annealing approach for solving stock cutting problem", In: Systems, Man and Cybernetics,1990. Conference Proceedings., IEEE International Conference on,. pp. 221-223, 1990
[49]
H. Foerster, and G. Wäscher, "Simulated annealing for order spread minimization in sequencing cutting patterns", Eur. J. Oper. Res., vol. 110, no. 2, pp. 272-281, 1998.
[50]
V. Parada, M. Sepúlveda, M. Solar, and A. Gómes, "Solution for the constrained guillotine cutting problem by simulated annealing", Comput. Oper. Res., vol. 25, no. 1, pp. 37-47, 1998.
[51]
L. Faina, "An application of simulated annealing to the cutting stock problem", Eur. J. Oper. Res., vol. 114, no. 3, pp. 542-556, 1999.
[52]
T.W. Leung, C.H. Yung, and M.D. Troutt, "Applications of genetic search and simulated annealing to the two-dimensional non-guillotine cutting stock problem", Comput. Ind. Eng., vol. 40, no. 3, pp. 201-214, 2001.
[53]
A. Soke, and Z. Bingul, "Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems", Eng. Appl. Artif. Intell., vol. 19, no. 5, pp. 557-567, 2006.
[54]
E.K. Burke, G. Kendall, and G. Whitwell, "A simulated annealing enhancement of the best-fit heuristic for the orthogonal stock-cutting problem", Inf. J. Comput., vol. 21, no. 3, pp. 505-516, 2009.
[55]
S.C. Leung, D. Zhang, C. Zhou, and T. Wu, "A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem", Comput. Oper. Res., vol. 39, no. 1, pp. 64-73, 2012.
[56]
S. Hong, D. Zhang, H.C. Lau, X. Zeng, and Y-W. Si, "A hybrid heuristic algorithm for the 2D variable-sized bin packing problem", Eur. J. Oper. Res., vol. 238, no. 1, pp. 95-103, 2014.
[57]
A.K. Virk, and K. Singh, Solving Two-Dimensional Rectangle Packing Problem Using Nature-Inspired Metaheuristic Algorithms.Vol. 238, No. 1, pp. 95-103, 2014.. Eur. J. Oper. Res.,
[58]
M.A. Carravilla, C. Ribeiro, and J.F. Oliveira, "Solving nesting problems with non-convex polygons by constraint logic programming", Int. Trans. Oper. Res., Vol. 10, No. 6, pp. 651-663, 2003.
[59]
J.O. Berkey, and P.Y. Wang, "Two-dimensional finite bin-packing algorithms", J. Oper. Res. Soc., vol. 38, no. 5, pp. 423-429, 1987.
[60]
S. Martello, and D. Vigo, "Exact solution of the two-dimensional finite bin packing problem", Manage. Sci., vol. 44, no. 3, pp. 388-399, 1998.
[61]
J.A. Bennell, L.S. Lee, and C.N. Potts, "A genetic algorithm for two-dimensional bin packing with due dates", Int. J. Prod. Econ., vol. 145, no. 2, pp. 547-560, 2013.
[62]
E. Falkenauer, and A. Delchambre, "A genetic algorithm for bin packing and line balancing", In: in Robotics and Automation, 1992.Proceedings., 1992 IEEE International Conference on, . pp. 1186-1192, 1992.

Rights & Permissions Print Cite
Article Metrics
5
© 2024 Bentham Science Publishers | Privacy Policy