Un algoritmo genético eficiente para el strip-packing problem

Dado un conjunto de piezas rectangulares y un contenedor de ancho fijo y largo variable, el problema del Strip Packing (SP) consiste en posicionar ortogonalmente todas las piezas dentro del contenedor, sin solaparlas, para así minimizar la altura alcanzada dentro del contenedor. Diversos métodos se...

Full description

Autores:
Gatica, Gustavo
Villagrán, Gonzalo
Contreras-Bolton, Carlos
Linfati, Rodrigo
Escobar, John Willmer
Tipo de recurso:
Article of journal
Fecha de publicación:
2015
Institución:
Pontificia Universidad Javeriana
Repositorio:
Repositorio Universidad Javeriana
Idioma:
eng
OAI Identifier:
oai:repository.javeriana.edu.co:10554/25636
Acceso en línea:
http://revistas.javeriana.edu.co/index.php/iyu/article/view/10853
http://hdl.handle.net/10554/25636
Palabra clave:
Rights
openAccess
License
Atribución-NoComercial-SinDerivadas 4.0 Internacional
id JAVERIANA2_3df57db0a323abf7af95a0a3a241cf4d
oai_identifier_str oai:repository.javeriana.edu.co:10554/25636
network_acronym_str JAVERIANA2
network_name_str Repositorio Universidad Javeriana
repository_id_str
spelling Atribución-NoComercial-SinDerivadas 4.0 Internacionalinfo:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Gatica, GustavoVillagrán, GonzaloContreras-Bolton, CarlosLinfati, RodrigoEscobar, John Willmer2020-04-16T17:28:18Z2020-04-16T17:28:18Z2015-12-07http://revistas.javeriana.edu.co/index.php/iyu/article/view/1085310.11144/Javeriana.iyu20-1.ngpg2011-27690123-2126http://hdl.handle.net/10554/25636Dado un conjunto de piezas rectangulares y un contenedor de ancho fijo y largo variable, el problema del Strip Packing (SP) consiste en posicionar ortogonalmente todas las piezas dentro del contenedor, sin solaparlas, para así minimizar la altura alcanzada dentro del contenedor. Diversos métodos se han utilizado para su resolución, siendo algunos de los más populares los Algoritmos Genéticos, debido a su efectividad en otros problemas combinatoriales. Se han utilizado representaciones numéricas que obligan a la utilización de operadores genéticos  que alteran la representación para preservar la factibilidad de las soluciones, coartando la naturaleza de la evolución. Nosotros proponemos un enfoque del tipo genotipo-fenotipo que no altera la evolución darwiniana, permitiendo el uso de operadores genéticos tradicionales. Los resultados computacionales se ejecutaron con dos grupos de problemas que corresponden a los benchmarking propuestos en la literatura.  Los resultados obtenidos mostraron que el algoritmo supera el 100% de los casos resueltos por algoritmos genéticos clásicos con representación numérica.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. PDFapplication/pdfengPontificia Universidad Javerianahttp://revistas.javeriana.edu.co/index.php/iyu/article/view/10853/12530Ingenieria y Universidad; Vol 20 No 1 (2016): January-June; 119-138Ingenieria y Universidad; Vol. 20 Núm. 1 (2016): Enero-Julilo; 119-138Un algoritmo genético eficiente para el strip-packing problemA New Genotype-Phenotype Genetic Algorithm for the Two-Dimensional Strip Packing Problem with Rotation of 90°http://purl.org/coar/version/c_970fb48d4fbd8a85Artículo de revistahttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1info:eu-repo/semantics/articlePeer-reviewed Article10554/25636oai:repository.javeriana.edu.co:10554/256362023-03-29 12:44:12.923Repositorio Institucional - Pontificia Universidad Javerianarepositorio@javeriana.edu.co
dc.title.spa.fl_str_mv Un algoritmo genético eficiente para el strip-packing problem
dc.title.english.eng.fl_str_mv A New Genotype-Phenotype Genetic Algorithm for the Two-Dimensional Strip Packing Problem with Rotation of 90°
title Un algoritmo genético eficiente para el strip-packing problem
spellingShingle Un algoritmo genético eficiente para el strip-packing problem
title_short Un algoritmo genético eficiente para el strip-packing problem
title_full Un algoritmo genético eficiente para el strip-packing problem
title_fullStr Un algoritmo genético eficiente para el strip-packing problem
title_full_unstemmed Un algoritmo genético eficiente para el strip-packing problem
title_sort Un algoritmo genético eficiente para el strip-packing problem
dc.creator.fl_str_mv Gatica, Gustavo
Villagrán, Gonzalo
Contreras-Bolton, Carlos
Linfati, Rodrigo
Escobar, John Willmer
dc.contributor.author.none.fl_str_mv Gatica, Gustavo
Villagrán, Gonzalo
Contreras-Bolton, Carlos
Linfati, Rodrigo
Escobar, John Willmer
description Dado un conjunto de piezas rectangulares y un contenedor de ancho fijo y largo variable, el problema del Strip Packing (SP) consiste en posicionar ortogonalmente todas las piezas dentro del contenedor, sin solaparlas, para así minimizar la altura alcanzada dentro del contenedor. Diversos métodos se han utilizado para su resolución, siendo algunos de los más populares los Algoritmos Genéticos, debido a su efectividad en otros problemas combinatoriales. Se han utilizado representaciones numéricas que obligan a la utilización de operadores genéticos  que alteran la representación para preservar la factibilidad de las soluciones, coartando la naturaleza de la evolución. Nosotros proponemos un enfoque del tipo genotipo-fenotipo que no altera la evolución darwiniana, permitiendo el uso de operadores genéticos tradicionales. Los resultados computacionales se ejecutaron con dos grupos de problemas que corresponden a los benchmarking propuestos en la literatura.  Los resultados obtenidos mostraron que el algoritmo supera el 100% de los casos resueltos por algoritmos genéticos clásicos con representación numérica.
publishDate 2015
dc.date.created.none.fl_str_mv 2015-12-07
dc.date.accessioned.none.fl_str_mv 2020-04-16T17:28:18Z
dc.date.available.none.fl_str_mv 2020-04-16T17:28:18Z
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.hasversion.none.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.local.spa.fl_str_mv Artículo de revista
dc.type.coar.none.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.type.driver.none.fl_str_mv info:eu-repo/semantics/article
dc.type.other.none.fl_str_mv Peer-reviewed Article
format http://purl.org/coar/resource_type/c_6501
dc.identifier.none.fl_str_mv http://revistas.javeriana.edu.co/index.php/iyu/article/view/10853
10.11144/Javeriana.iyu20-1.ngpg
dc.identifier.issn.none.fl_str_mv 2011-2769
0123-2126
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/10554/25636
url http://revistas.javeriana.edu.co/index.php/iyu/article/view/10853
http://hdl.handle.net/10554/25636
identifier_str_mv 10.11144/Javeriana.iyu20-1.ngpg
2011-2769
0123-2126
dc.language.iso.none.fl_str_mv eng
language eng
dc.relation.uri.none.fl_str_mv http://revistas.javeriana.edu.co/index.php/iyu/article/view/10853/12530
dc.relation.citationissue.eng.fl_str_mv Ingenieria y Universidad; Vol 20 No 1 (2016): January-June; 119-138
dc.relation.citationissue.spa.fl_str_mv Ingenieria y Universidad; Vol. 20 Núm. 1 (2016): Enero-Julilo; 119-138
dc.rights.licence.*.fl_str_mv Atribución-NoComercial-SinDerivadas 4.0 Internacional
dc.rights.accessrights.none.fl_str_mv info:eu-repo/semantics/openAccess
dc.rights.coar.spa.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv Atribución-NoComercial-SinDerivadas 4.0 Internacional
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.spa.fl_str_mv PDF
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.eng.fl_str_mv Pontificia Universidad Javeriana
institution Pontificia Universidad Javeriana
repository.name.fl_str_mv Repositorio Institucional - Pontificia Universidad Javeriana
repository.mail.fl_str_mv repositorio@javeriana.edu.co
_version_ 1811671106337112064

Publicaciones similares