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

Un nuevo algoritmo genético de genotipo-fenotipo para el problema de Strip Packing de dos dimensiones con rotación de 90o

Dado un conjunto de piezas rectangulares con ancho fijo y con longitud infinita, el problema de strip-packing (SPP) de dos dimensiones, con una rotación de las piezas de 90°, consiste en la colocación ortogonal de todas las piezas en la tira, sin sobreponerlas, a fin de minimizar la altura de la tira usada. Se han propuesto varios algoritmos para resolver este problema, pero los genéticos constituyen uno de los enfoques más populares, debido a su eficacia en la solución en problemas NP-hard. En este trabajo se presentan tres representaciones binarias, una operación crossover clásica y operadores de mutación. Las tres representaciones binarias se comparan en un subconjunto de instancias de benchmarking. La representación R2 supera los resultados obtenidos por la representación R1 y R3. De hecho, se mejoran algunos de los mejores resultados encontrados por los trabajos publicados anteriormente.

INTRODUCCIÓN

El Problema de Empaquetamiento en Tiras (SPP) se deriva de los problemas de corte y empaquetamiento, y es considerado como NP-Hard debido a su dificultad combinatoria [1]. Este problema se encuentra en las industrias productivas, donde la optimización de las materias primas se convierte en beneficios económicos al reducir los costes de producción [2]. El SPP considera dos casos: bidimensional y tridimensional. Aunque los casos tridimensionales suelen ser más atractivos para la comunidad investigadora debido a su practicidad, los casos bidimensionales han logrado avances significativos en los enfoques algorítmicos y en el tamaño de las instancias resueltas, aumentando el número de elementos [3]. En particular, el Problema de Empaquetamiento en Tiras en dos dimensiones (2D-SPP) se define como una región rectangular con una anchura W y una altura infinita, donde todas las piezas rectangulares i ∈ I = {1,2,..., n} con una anchura W y una altura h_i definidas, no deben solaparse y pueden girar 90°. El objetivo de este problema es minimizar la altura H obtenida de la tira posicionando todas las piezas sobre ella [4]. El 2D-SPP ha sido formulado matemáticamente en [5]. El 2D-SPP requiere que se coloquen n rectángulos minimizando la altura de la tira H. Si consideramos la esquina inferior izquierda de la tira como el origen de la región del plano xy, x debe corresponder al ancho de la dirección de la región, y a la dirección de la altura. Además, la ubicación de cada rectángulo en la franja estaría representada por una coordenada (x_i, y_i) desde la esquina inferior izquierda. El conjunto de coordenadas π = {(x_i, y_i) ∨ i ∈ I} se denomina colocación de I. El 2D-SPP puede formularse como sigue:

minimizar H                        (1)