Abstract
The two-dimensional bin packing problem (2D-BPP) consists of packing, without overlapping, a set of rectangular items with different sizes into smallest number of rectangular containers, called “bins”, having identical dimensions. According to the real-word requirements, the items may either have a fixed orientation or they can be rotated by 90°. In addition, it may or not be subjugate to the guillotine cutting. In this article, we consider the two-dimensional bin packing problem with fixed orientation and free cutting. In fact, we propose a hybrid approach by combining two bio-inspired algorithms that are the crow search algorithm (CSA) and the genetic algorithm (GA) to solve the considered problem. So, the main idea behind this hybridization is to expect reaching a sort of cooperative synergy between the operators of the two combined algorithms. That is, the CSA is discretized and adapted to the 2D-BPP context, while using genetic operators to improve individuals (i.e. crows) adaptation. The average performance of the proposed hybrid approach is evaluated on the standard benchmark instances of the considered problem and compared with two other bio-inspired algorithms having closely similar nature; namely standard genetic algorithm and binary particle swarm optimization algorithm. The obtained results are very promising.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Wäscher, G., Haußner, H., Schumann, H.: An improved typology of cutting and packing problems. Eur. J. Oper. Res. 183, 1109–1130 (2007)
Crainic, T.G., et al.: Bin packing problems with uncertainty on item characteristics: An application to capacity planning in logistics. Procedia-Soc. Behav. Sci. 111, 654–662 (2014)
Wee, T.S., Magazine, M.J.: Assembly line balancing as generalized bin packing. Oper. Res. Lett. 1, 56–58 (1982)
Song, W., et al.: Adaptive resource provisioning for the cloud using online bin packing. IEEE Trans. Comput. 63, 2647–2660 (2014)
Lodi, A., Martello, S., Vigo, D.: Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems. INFORMS J. Comput. 11, 345–357 (1999)
Epstein, L., Van Stee, R.: Optimal online algorithms for multidimensional packing problems. SIAM J. Comput. 35, 431–448 (2005)
Laabadi, S.: A new algorithm for the Bin-packing problem with fragile objects. In: 3rd International Conference on Logistics Operations Management, pp. 1–7. IEEE, Fez (2016)
Bansal, N., Liu, Z., Sankar, A.: Bin-packing with fragile objects and frequency allocation in cellular networks. Wirel. Netw. 15, 821–830 (2009)
Shakhsi, N.M., Joulaei, F., Razmi, J.: Extending two-dimensional bin packing problem: consideration of priority for items. J. Ind. Syst. Eng. 3, 72–84 (2009)
Hamdi-Dhaoui, K., Labadie, N., Yalaoui, A.: Algorithms for the two dimensional bin packing problem with partial conflicts. RAIRO-Oper. Res. 46, 41–62 (2012)
Khanafer, A., Clautiaux, F., Talbi, E.G.: Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts. Comput. Oper. Res. 39, 54–63 (2012)
Berkey, J.O., Wang, P.Y.: Two-dimensional finite bin-packing algorithms. J. Oper. Res. Soc. 38, 423–429 (1987)
Monaci, M., Toth, P.: A set-covering-based heuristic approach for bin-packing problems. INFORMS J. Comput. 18, 71–85 (2006)
Baumgartner, L., Schmid, V., Blum, C.: Solving the two-dimensional bin packing problem with a probabilistic multi-start heuristic. In: Coello, C.A.C. (ed.) LION 2011. LNCS, vol. 6683, pp. 76–90. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25566-3_6
Wong, L.: Heuristic placement routines for two-dimensional rectangular bin packing problems. Ph.D. thesis, Universiti Putra Malaysia (2009)
Parreño, F., et al.: A hybrid GRASP/VND algorithm for two-and three-dimensional bin packing. Ann. Oper. Res. 179, 203–220 (2010)
Lai, K.K., Chan, J.W.: Developing a simulated annealing algorithm for the cutting stock problem. Comput. Ind. Eng. 32, 115–127 (1997)
Gonçalves, J.F., Resende, M.G.: A biased random key genetic algorithm for 2D and 3D bin-packing problems. Int. J. Prod. Econ. 145, 500–510 (2013)
Soke, A., Bingul, Z.: Hybrid genetic algorithm and simulated annealing for two-dimensional non-guillotine rectangular packing problems. Eng. Appl. Artif. Intell. 19, 557–567 (2006)
Blum, C., Schmid, V.: Solving the 2D bin packing problem by means of a hybrid evolutionary algorithm. Procedia Comput. Sci. 18, 899–908 (2013)
Shin, Y.B., Kita, E.: Solving two-dimensional packing problem using particle swarm optimization. Comput. Assist. Methods Eng. Sci. 19, 241–255 (2017)
Liu, D.S., et al.: On solving multiobjective bin packing problems using evolutionary particle swarm optimization. Eur. J. Oper. Res. 190, 357–382 (2008)
Reeves, C., Rowe, J.E.: Genetic Algorithms: Principles and Perspectives: A Guide to GA Theory. Springer, New York (2002). https://doi.org/10.1007/b101880
Askarzadeh, A.: A novel metaheuristic method for solving constrained engineering optimization problems: crow search algorithm. Comput. Struct. 169, 1–12 (2016)
De Souza, R.C.T., et al.: A V-shaped binary crow search algorithm for feature selection. In: IEEE Congress on Evolutionary Computation, pp. 1–8. IEEE, Rio de Janeiro (2018)
Goldberg, D., Lingle, R.: Alleles, loci, and the travelling salesman problem. In: First International Conference on Genetic Algorithms and their Applications, pp. 154–159. Lawrence Erlbaum Associates, Hillsdale (1985)
http://or.dei.unibo.it/library/two-dimensional-bin-packing-problem
Martello, S., Vigo, D.: Exact solution of the two-dimensional finite bin packing problem. Manag. Sci. 44, 388–399 (1998)
Kennedy, J., Eberhart, R.C.: A discrete binary version of the particle swarm algorithm. In: International Conference on Systems, Man, and Cybernetics. Computational Cybernetics and Simulation, vol. 5, pp. 4104–4108 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Laabadi, S., Naimi, M., El Amri, H., Achchab, B. (2019). A Crow Search-Based Genetic Algorithm for Solving Two-Dimensional Bin Packing Problem. In: Benzmüller, C., Stuckenschmidt, H. (eds) KI 2019: Advances in Artificial Intelligence. KI 2019. Lecture Notes in Computer Science(), vol 11793. Springer, Cham. https://doi.org/10.1007/978-3-030-30179-8_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-30179-8_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-30178-1
Online ISBN: 978-3-030-30179-8
eBook Packages: Computer ScienceComputer Science (R0)