Algoritmo genético para el problema de empaquetamiento de contenedores de dos dimensiones, aplicado para la optimización de papel en imprentas digitales

En el presente trabajo de investigación se aplica un algoritmo genético para resolver el problema de empaquetamiento de contenedores de dos dimensiones aplicado a la optimización de papel en imprentas digitales. Para dar solución a este problema, se realizó un estudio sobre geometría computacional para evitar el traslape entre figuras amorfas que se inserten en la hoja de papel, y así poder optimizar la función objetivo cumpliendo con las restricciones del problema. Además, se diseñó y se implementó una estructura híbrida de vecindad con movimientos bidimensionales, con el objetivo de mejorar el desempeño del algoritmo genético implementado. Se aplicó una metodología de sintonización, la cual permitió realizar el análisis de sensibilidad de los parámetros de control del algoritmo genético, lo que favorece que el algoritmo trabaje con el mejor desempeño en eficiencia y eficacia. La aportación de este trabajo de investigación es la implementación de un mapeo del problema de empaquetamiento de contenedores de dos dimensiones aplicado a la optimización del desperdicio de papel en imprentas digitales tratado con un algoritmo genético y una estructura híbrida de vecindad con movimientos bidimensionales (Rotación, Traslación, Inserción e Intercambio). Las pruebas experimentales realizadas al algoritmo genético implementado mostraron que es posible obtener buenas soluciones para figuras amorfas.

In the present research work, a genetic algorithm is applied to solve the two- dimensional container packaging problem applied to the optimization of paper in digital printing presses. To solve this problem, a study on computational geometry was carried out to avoid the overlap between amorphous figures that are inserted in the sheet of paper, and thus be able to optimize the objective function complying with the restrictions of the problem, it was also studied, designed and a hybrid neighborhood structure with two-dimensional movements was implemented, to improve the performance of the implemented genetic algorithm. A tuning methodology was applied, which allowed to performance of the sensitivity analysis of the control parameters of the genetic algorithm, which allowed the algorithm to work with the best performance in efficiency and effectiveness. The contribution of this research work is the implementation of a mapping of the two-dimensional container packaging problem applied to the optimization of paper waste in digital printing presses treated with a genetic algorithm and a hybrid neighborhood structure with two-dimensional movements (Rotation, Translation, Insertion, and Exchange). The experimental tests carried out on the implemented genetic algorithm showed that it is possible to obtain good solutions for amorphous figures.