Solving Single Nesting Problem Using a Genetic Algorithm

Şerban, C.; Dumitriu, C.Ş.; Bărbulescu, A.

doi:10.2478/auom-2022-0029

Abstract

Since the Bin Packing Problem (BPP) has application to industry and supply chain management problems (to mention only the most important ones), it attracted attention from its formulation. The Single Nesting Problem treated here is a particular case of this optimization problem, which different methods, mainly combinatorial, can solve. In this article, we propose using a genetic algorithm for solving the single nesting problem formulated in a previous article by the authors. The results comparisons prove that this approach is an excellent alternative to the combinatorial ones.

References

[1] M. Abdel-Basset, G. Manogaran, L. Abdel-Fatah, and S. Mirjalili, An improved nature inspired meta-heuristic algorithm for 1-D bin packing problems, Pers Ubiquit. Comput 22 (2018), 11171132.10.1007/s00779-018-1132-7
Search in Google Scholar Back to article
[2] A. C. F. Alvim, C. C. Ribeiro, F. Glover, and D. J. Aloise, A hybrid improvement heuristic for the one-dimensional bin packing problem, https://leeds-faculty.colorado.edu/glover/TS%20-%20bin%20packing%20-%20Ceslso.pdf
Search in Google Scholar Back to article
[3] A. Bărbulescu, C. Ş. Dumitriu, On the connection between the GEP Performances and the Time Series Properties, Mathematics 9(16) (2021), 1853, https://doi.org/10.3390/math9161853.10.3390/math9161853
Search in Google Scholar Back to article
[4] A. Bărbulescu, C. Ş. Dumitriu, Mathematical aspects of the study of the cavitation in liquids, in Series on Mathematical Modelling of Environmental and Life Sciences Problems, Proceedings of the 4th Workshop, Sept. 2005, Constanta, Romania, S. Ion, G. Marinoschi, C. Popa (eds.), Ed. Academiei Romne, Bucureti (2006), 7-15.
Search in Google Scholar Back to article
[5] A. Bărbulescu, C. Şerban, M.-L. Indrecan, Improving spatial interpolation quality. IDW versus a genetic algorithm, Water 13 (2021), 863, https://doi.org/10.3390/w13060863.10.3390/w13060863
Search in Google Scholar Back to article
[6] A. Bărbulescu, C. Şerban, S. Caramihai, Assessing the soil pollution using a genetic algorithm, Romanian Journal of Physics 66(3-4) (2021), 806.
Search in Google Scholar Back to article
[7] H. Ben Amor and J. Valério de Carvalho, Cutting Stock Problems. In: G. Desaulniers, J. Desrosiers, M. M. Solomon (eds), Column Generation. Springer, Boston, MA. (2005), 131-161.10.1007/0-387-25486-2_5
Search in Google Scholar Back to article
[8] H. Cambazard and B. O’ Sullivan, Propagating the Bin Packing Constraint Using Linear Programming. In: D. Cohen (ed), Principles and Practice of Constraint Programming CP 2010. CP 2010. Lecture Notes in Computer Science, 6308. Springer, Berlin, Heidelberg, (2010), 129-136.
Search in Google Scholar Back to article
[9] E. G. Co man Jr., J.Csirik, G. Galambos, S. Martello, and D. Vigo, Bin Packing Approximation Algorithms: Survey and Classification. In: P. Pardalos, D. Z. Du, R. Graham (eds), Handbook of Combinatorial Optimization. Springer, New York, NY. (2013), 455-531.10.1007/978-1-4419-7997-1_35
Search in Google Scholar Back to article
[10] F.-L. Dragomir, G. Alexandrescu, Applications of artificial intelligence in the decision fundamentation, Bulletin of “Carol I” National Defence University 4(2) (2017), 56-61 (in Romanian).
Search in Google Scholar Back to article
[11] F.-L. Dragomir, The modeling of the decisional problems, Bulletin of “Carol I” National Defence University, 01 (2017), 72-75.
Search in Google Scholar Back to article
[12] F.-L. Dragomir, The axiomatic character of decision, Bulletin of “Carol I” National Defence University 4(2) (2017), 56-61.
Search in Google Scholar Back to article
[13] C. Ş. Dumitriu, A. Bărbulescu, A method for the single direction nesting computation, The 7th Balkan Conference on Operational Research, BACOR 05, Constanta, May 2005, Romania, https://www.academia.edu/44635040/A_Method_for_the_Single_Direction_Nesting_Computation.
Search in Google Scholar Back to article
[14] C. Ş. Dumitriu, A. Bărbulescu, Studies about the copper base alloys used in naval constructions modeling the loss mass in different media, Sitech, Craiova (2007).
Search in Google Scholar Back to article
[15] S. Eilon and N. Christofides, The loading problem, Manag. Sci. 17(5) (1971), 259-278.10.1287/mnsc.17.5.259
Search in Google Scholar Back to article
[16] H. Feng, H. Ni, R. Zhao, and X. Zhu, An Enhanced Grasshopper Optimization Algorithm to the Bin Packing Problem, J. Control Sci. Eng., 3894987 (2020).10.1155/2020/3894987
Search in Google Scholar Back to article
[17] D. E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Pearson Education, Singapore (2002).
Search in Google Scholar Back to article
[18] M. S. Hung and J. R. Brown, An algorithm for a class of loading problems, Naval Res. Logist. Q. 25(2) (1978), 289-297.10.1002/nav.3800250209
Search in Google Scholar Back to article
[19] M. Hyde, G. Ochoa, J. Vázquez-Rodriguez, and T. Curtois, A HyFlex Module for the One Dimensional Bin Packing Problem, (2011), http://www.asap.cs.nott.ac.uk/external/chesc2011/reports/BinPackingHyFlex.pdf.
Search in Google Scholar Back to article
[20] J. Joines and C. Houck, On the Use of Non-Stationary Penalty Functions to Solve Constrained Optimization Problems with Genetic Algorithms, Proceedings of the 1st IEEE Conference on Evolutionary Computation, Orlando, 27-29 June 1994, 579-584.
Search in Google Scholar Back to article
[21] S. Martello, Packing problems in one or more dimensions, (2018), http://www.or.deis.unibo.it/staff_pages/martello/Slides_Estoril_Martello.pdf.
Search in Google Scholar Back to article
[22] S. Martello and P. Toth, Knapsack problems. Algorithms and Computer Implementation, John Willey & Sons, Chichester, West England (1990).
Search in Google Scholar Back to article
[23] E. A. Mukhacheva, G. N. Belov, V. M. Kartack, and A. S. Mukhacheva, Linear one-dimensional cutting-packing problems: numerical experiments with the sequential value correction method (SVC) and a modified branch-and-bound method (MBB), Pesqui. Oper. 20(2) (2000), 153 - 168.10.1590/S0101-74382000000200002
Search in Google Scholar Back to article
[24] C. Munien, S. Mahabeer, E. Dzitiro, S. Singh, S. Zungu, and A. El-Shamir Ezugwu, Metaheuristic Approaches for One-Dimensional Bin Packing Problem: A Comparative Performance Study, IEEE Access 8, 227438 (2020).
Search in Google Scholar Back to article
[25] G. Scheithauer, Introduction to Cutting and Packing Optimization. Problems, Modeling Approaches, Solution Methods, Springer International Publishing (2018).10.1007/978-3-319-64403-5_1
Search in Google Scholar Back to article
[26] S. N. Sivanandam and S. N. Deepa, Introduction to Genetic Algorithms, Springer-Verlag Berlin Heidelberg (2008).
Search in Google Scholar Back to article
[27] S. L. Yadav and A. Sohal, Comparative Study of Different Selection Techniques in Genetic Algorithm, Int. J. Eng. Sci. Math. 6(3) (2017), 174-180.
Search in Google Scholar Back to article

Solving Single Nesting Problem Using a Genetic Algorithm

Abstract

Paradigm

My account