nach oben

Erschienen in:

2024 | OriginalPaper | Buchkapitel

Heuristics for Evolutionary Optimization for the Centered Bin Packing Problem

verfasst von : Luke de Jeu, Anil Yaman

Erschienen in: Applications of Evolutionary Computation

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Bin Packing Problem (BPP) is an optimization problem where a number of objects are placed within a finite space. This problem has a wide range of applications, from improving the efficiency of transportation to reducing waste in manufacturing. In this paper, we are considering a variant of the BPP where irregular shaped polygons are required to be placed as close to the center as possible. This variant is motivated by its application in 3D printing, where central placement of the objects improves the printing reliability. To find (near) optimum solutions to this problem, we employ Evolutionary Algorithms, and propose several heuristics. We show how these heuristics interact with each other, and their most effective configurations in providing the best solutions.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Evolving Artificial Neural Networks for Simulating Fish Social Interactions

Nächstes Kapitel A Hierarchical Approach to Evolving Behaviour-Trees for Swarm Control

Nur mit Berechtigung zugänglich

GitHub - tamasmeszaros/libnest2d: 2D irregular bin packaging and nesting library written in modern C++ – github.com. https://github.com/tamasmeszaros/libnest2d. Accessed 13 Oct 2023

GitHub - Ultimaker/pynest2d: Python bindings for libnest2d – github.com. https://github.com/Ultimaker/pynest2d. Accessed 12 Nov 2023

UltiMaker Cura – ultimaker.com. https://ultimaker.com/software/ultimaker-cura/. Accessed 30 Oct 2023

Bäck, T., Schwefel, H.P.: An overview of evolutionary algorithms for parameter optimization. Evol. Comput.1(1), 1–23 (1993). https://doi.org/10.1162/evco.1993.1.1.1. https://doi.org/10.1162/evco.1993.1.1.1

Berkey, J.O., Wang, P.Y.: Two-dimensional finite bin-packing algorithms. J. Operational Res. Soc. 38(5), 423–429 (1987). https://doi.org/10.1057/jors.1987.70

Burke, E., Hellier, R., Kendall, G., Whitwell, G.: A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Oper. Res. 54(3), 587–601 (2006). https://doi.org/10.1287/opre.1060.0293

Costa, L., Oliveira, P.: An evolution strategy for multiobjective optimization. In: Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No.02TH8600). IEEE (2002). https://doi.org/10.1109/cec.2002.1006216

Côté, J.F., Haouari, M., Iori, M.: Combinatorial benders decomposition for the two-dimensional bin packing problem. INFORMS J. Comput.33(3), 963–978 (2021). https://doi.org/10.1287/ijoc.2020.1014

Flores, J.J., Martínez, J., Calderón, F.: Evolutionary computation solutions to the circle packing problem. Soft. Comput. 20, 1521–1535 (2016)CrossRef

10.

Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing problems: a survey. Analysis and Design of Algorithms in Combinatorial Optimization, pp. 147–172 (1981). https://doi.org/10.1007/978-3-7091-2748-3_8

11.

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(2), 500–510 (2013). https://doi.org/10.1016/j.ijpe.2013.04.019

12.

Griffiths, V., Scanlan, J.P., Eres, M.H., Martinez-Sykora, A., Chinchapatnam, P.: Cost-driven build orientation and bin packing of parts in selective laser melting (SLM). Eur. J. Oper. Res. 273(1), 334–352 (2019). https://doi.org/10.1016/j.ejor.2018.07.053

13.

Guo, B., Zhang, Y., Hu, J., Li, J., Wu, F., Peng, Q., Zhang, Q.: Two-dimensional irregular packing problems: a review. Front. Mech. Eng. 8, August 2022. https://doi.org/10.3389/fmech.2022.966691

14.

Kang, K., Moon, I., Wang, H.: A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem. Appl. Math. Comput.219(3), 1287–1299 (2012). https://doi.org/10.1016/j.amc.2012.07.036

15.

Kao, C.Y., Horng, J.T.: On solving rectangle bin packing problems using genetic algorithms. In: Proceedings of IEEE International Conference on Systems, Man and Cybernetics (1994). https://doi.org/10.1109/icsmc.1994.400073

16.

Laabadi, S., Naimi, M., Amri, H.E., Achchab, B.: A binary crow search algorithm for solving two-dimensional bin packing problem with fixed orientation. Procedia Comput. Sci. 167, 809–818 (2020). https://doi.org/10.1016/j.procs.2020.03.420

17.

Lamas-Fernandez, C., Bennell, J.A., Martinez-Sykora, A.: Voxel-based solution approaches to the three-dimensional irregular packing problem. Oper. Res. 71(4), 1298–1317 (2023). https://doi.org/10.1287/opre.2022.2260

18.

Lodi, A., Martello, S., Vigo, D.: Approximation algorithms for the oriented two-dimensional bin packing problem. Eur. J. Oper. Res. 112(1), 158–166 (1999). https://doi.org/10.1016/s0377-2217(97)00388-3

19.

Lopez, E., Ochoa, G., Terashima-Marín, H., Burke, E.: An effective heuristic for the two-dimensional irregular bin packing problem. Ann. Oper. Res. 206, 241–264 (2013). https://doi.org/10.1007/s10479-013-1341-4

20.

Mpofu, T.P., Mawere, C., Mukosera, M.: The impact and application of 3d printing technology. Int. J. Sci. Res., June 2014

21.

Munien, C., Ezugwu, A.E.: Metaheuristic algorithms for one-dimensional bin-packing problems: a survey of recent advances and applications. J. Intell. Syst. 30(1), 636–663 (2021). https://doi.org/10.1515/jisys-2020-0117

22.

Puchinger, J., Raidl, G.R., Koller, G.: Solving a real-world glass cutting problem. In: Evolutionary Computation in Combinatorial Optimization, pp. 165–176. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24652-7_17

23.

Tamir, T.S., Xiong, G., Fang, Q., Dong, X., Shen, Z., Wang, F.Y.: A feedback-based print quality improving strategy for FDM 3d printing: an optimal design approach. The International J. Adv. Manuf. Technol. 120(3-4), 2777–2791 (2022). https://doi.org/10.1007/s00170-021-08332-4

24.

Terashima-Marín, H., Ross, P., Farías-Zárate, C., López-Camacho, E., Valenzuela-Rendón, M.: Generalized hyper-heuristics for solving 2d regular and irregular packing problems. Ann. Oper. Res. 179, 369–392 (2010)MathSciNetCrossRef

25.

Trivella, A., Pisinger, D.: The load-balanced multi-dimensional bin-packing problem. Comput. Oper. Res. 74, 152–164 (2016). https://doi.org/10.1016/j.cor.2016.04.020

26.

Volna, E.: Genetic algorithms for two dimensional bin packing problem. In: AIP Conference Proceedings, vol. 1648, p. 550002 (2015). https://pubs.aip.org/aip/acp/article/1648/1/550002/802815/Genetic-algorithms-for-two-dimensional-bin-packing

27.

Zhang, J., Wang, X.Z., Yu, W.W., Deng, Y.H.: Numerical investigation of the influence of process conditions on the temperature variation in fused deposition modeling. Mater. Des. 130, 59–68 (2017). https://doi.org/10.1016/j.matdes.2017.05.040

Titel: Heuristics for Evolutionary Optimization for the Centered Bin Packing Problem
verfasst von: Luke de Jeu
Anil Yaman
Verlag: Springer Nature Switzerland
Buch: Applications of Evolutionary Computation
Print ISBN: 978-3-031-56851-0

Electronic ISBN: 978-3-031-56852-7

Copyright-Jahr: 2024
DOI: https://doi.org/10.1007/978-3-031-56852-7_11

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner