Introducing an approach based on an advanced hybrid model for the two-dimensional bin packing problem

P. López*

Polytechnic University of Puerto Rico, San Juan, Puerto Rico

Abstract

As one of the classical problems in combinatorial optimization, the Bin Packing Problem (BPP) is assumed a branch of computer sciences and a special form of 0-1 knapsack problem and it is derived from the family of NP-Hard. This study aims at achieving optimal packing based on the minimum linear time and maximum applied bins with a focus on increasing the density of the solution set and decreasing in errors. This paper originates from the fact that it tries to achieve the minimum linear time and maximum applied bins for the two-dimensional bin packing problem (2DPP) as the methodology, and also, presents the optimal packing based on the minimum linear time and maximum applied bins for the packing problem in two-dimensional space by means of representation and comparisons based on the particle swarm optimization (PSO) algorithm and the hybrid model. Using the proposed model (the advanced hybrid model), the study covered one of the constraints which were present in the previous research, that is, holding the hard nature of the two-dimensional packing problem, which operates in a way that elongation of time in achieving the optimization state is accompanied with an increase in dimensions of the problems. Finally, the experimental and comparative results in the MATLAB software program approved the success and utility of the proposed model in minimizing the time of achieving the optimal packing and increasing in the number of applied bins in two-dimensional space (dual optimal packing).

Keywords

Two-dimensional bin packing, Advanced hybrid model, Pareto optimization, Particle swarm optimization

Digital Object Identifier (DOI)

https://doi.org/10.21833/AEEE.2019.11.002

Article history

Received 20 March 2019, Received in revised form 22 August 2019, Accepted 23 August 2019

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

López P (2019). Introducing an approach based on an advanced hybrid model for the two-dimensional bin packing problem. Annals of Electrical and Electronic Engineering, 2(11): 7-13

References (16)

  1. Alatas B, Akin E, and Ozer AB (2009). Chaos embedded particle swarm optimization algorithms. Chaos, Solitons & Fractals, 40(4): 1715-1734. https://doi.org/10.1016/j.chaos.2007.09.063   [Google Scholar]
  2. Coello CC and Lechuga MS (2002). MOPSO: A proposal for multiple objective particle swarm optimization. In the Congress on Evolutionary Computation, IEEE, Honolulu, USA: 1051-1056. https://doi.org/10.1109/CEC.2002.1004388   [Google Scholar]
  3. Coffman Jr EG, Csirik J, Rónyai L, and Zsbán A (2008). Random-order bin packing. Discrete Applied Mathematics 156(14): 2810-2816. https://doi.org/10.1016/j.dam.2007.11.004   [Google Scholar]
  4. Correa JR and Epstein L (2008). Bin packing with controllable item sizes. Information and Computation, 206(8): 1003-1016. https://doi.org/10.1016/j.ic.2008.04.005   [Google Scholar]
  5. Deb K, Burke EK, and Kendall G (2005). Multi-objective optimization in search methodologies. Springer-Verlag, New York, USA.   [Google Scholar]
  6. Dósa G and He Y (2006). Bin packing problems with rejection penalties and their dual problems. Information and Computation, 204(5): 795-815. https://doi.org/10.1016/j.ic.2006.02.003   [Google Scholar]
  7. Fan HY and Shi YH (2001). Study on Vmax of particle swarm optimization.  In the Workshop on Particle Swarm Optimization. Purdue School of Engineering and Technology, Indianapolis, USA.   [Google Scholar]
  8. Hong S, Zhang D, Lau HC, Zeng X, and Si YW (2014). A hybrid heuristic algorithm for the 2D variable sized bin packing problem. European Journal of Operational Research, 238(1): 95-103. https://doi.org/10.1016/j.ejor.2014.03.049   [Google Scholar]
  9. Kennedy J and Eberhart R (1995). Particle swarm optimization (PSO). In the IEEE International Conference on Neural Networks, Perth, Australia: 1942-1948.   [Google Scholar]
  10. Kennedy J and Mendes R (2002). Population structure and particle swarm performance. In the Congress on Evolutionary Computation, IEEE, Honolulu, USA: 1671-1676. https://doi.org/10.1109/CEC.2002.1004493   [Google Scholar]
  11. Lin M, Yang Y, and Xu J (2010). On lazy bin covering and packing problems. Theoretical Computer Science, 411(1): 277-284. https://doi.org/10.1016/j.tcs.2009.10.006   [Google Scholar]
  12. Rao RL and Iyengar SS (1994). Bin-packing by simulated annealing. Computers and Mathematics with Applications, 27(5): 71-82. https://doi.org/10.1016/0898-1221(94)90077-9   [Google Scholar]
  13. Ratnaweera A, Halgamuge SK, and Watson HC (2004). Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients. IEEE Transactions on Evolutionary Computation, 8(3): 240-255. https://doi.org/10.1109/TEVC.2004.826071   [Google Scholar]
  14. Shi Y and Eberhart RC (1998). Parameter selection in particle swarm optimization. In: Porto VW, Saravanan N, Waagen D, and Eiben AE (Eds.), Evolutionary Programming VII. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg. Germany. https://doi.org/10.1007/BFb0040810   [Google Scholar]
  15. Shi Y and Eberhart RC (2001). Particle swarm optimization with fuzzy adaptive inertia weight. In the Workshop on Particle Swarm Optimization. Purdue School of Engineering and Technology, Indianapolis, USA.   [Google Scholar]
  16. Wang S, Wang L, Shi R, and Ge M (2010). Study on improved ant colony optimization for bin-packing problem. In the International Conference on Computer Design and Applications, IEEE, Qinhuangdao, China. https://doi.org/10.1109/ICCDA.2010.5540875   [Google Scholar]