A New Genotype-Phenotype Genetic Algorithm for the Two-Dimensional Strip Packing Problem with Rotation of 90°

Gustavo Gatica, Gonzalo Villagrán, Carlos Contreras-Bolton, Rodrigo Linfati, John Willmer Escobar

Abstract


Given a set of rectangular pieces and a fixed width with infinite length, the strip-packing problem (SPP) of two dimensions (2D), with a rotation of pieces in 90° consists of orthogonally placing all the pieces on the strip, without overlapping them, minimizing the height of the strip used. Several algorithms have been proposed to solve this problem, being Genetic Algorithms one of the most popular approach due to it effectiveness solving NP-Hard problems. In this paper, three binary representations, and classic crossover and mutation operators are introduced. A comparison of the three binary representations on a subset of benchmarking instances is performed. The representation R2 outperforms the results obtained by representation R1 and R3. Indeed, some of the best-known results found by previous published approaches are improved. 


Keywords


strip packing problem; genotype-phenotype; genetic algorithm; phenotype generation

Full Text:

PDF


DOI: http://dx.doi.org/10.11144/Javeriana.iyu20-1.ngpg

Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM


Add comment



Creative Commons
This work is registered under Creative Commons Attribution 4.0 International.
Created from http://revistas.javeriana.edu.co/.

 

The journal Ingeniería y Universidad is registered under a Creative Commons Attribution 4.0 International Public License. Thus, this work may be reproduced, distributed, and publicly shared in digital format, as long as the names of the authors and Pontificia Universidad Javeriana are acknowledged. Others are allowed to quote, adapt, transform, auto-archive, republish, and create based on this material, for any purpose (even commercial ones), provided the authorship is duly acknowledged, a link to the original work is provided, and it is specified if changes have been made. Pontificia Universidad Javeriana does not hold the rights of published works and the authors are solely responsible for the contents of their works; they keep the moral, intellectual, privacy, and publicity rights.

Approving the intervention of the work (review, copy-editing, translation, layout) and the following outreach, are granted through an use license and not through an assignment of rights. This means the journal and Pontificia Universidad Javeriana cannot be held responsible for any ethical malpractice by the authors. As a consequence of the protection granted by the use license, the journal is not required to publish recantations or modify information already published, unless the errata stems from the editorial management process. Publishing contents in this journal does not generate royalties for contributors.