Solución al problema de empaquetamiento bidimensional guillotinado mediante el uso de un algoritmo de búsqueda tabú

El presente trabajo busca la solución al problema de empaquetamiento rectangular bidimensional restricto con corte guillotinado, el cual se fundamenta en la ubicación de piezas rectangulares en un contenedor rectangular más grande divido en múltiples subespacios determinados por cortes tipo guillotina. Con el objetivo de realizar una asignación optima de las piezas se implementó un algoritmo de Búsqueda Tabú poblacional obteniendo resultados significativos para cada caso de prueba evaluado.The present work seeks the solution to the restricted two-dimensional rectangular packing problem with guillotine cut, which is based on the location of rectangular pieces in a larger rectangular container divided into multiple subspaces determined by guillotine-type cuts. In order to perform an optimal assignment of the pieces, a population taboo search algorithm was implemented, obtaining significant results for each evaluated test case.MaestríaMagíster en Investigación Operativa y EstadísticaÍNDICE GENERAL 1 INTRODUCCIÓN 1 1.1 Planteamiento del problema 1 1.2 Delimitación 1 1.3 Motivación 2 1.4 Objetivos 3 1.4.1 Objetivo General 3 1.4.2 Objetivos Específicos 3 1.5 Metodología 3 2 MARCO DE REFERENCIA 5 2.1 Antecedentes 5 2.2 Definiciones generales 6 2.2.1 Metaheurística 6 2.2.2 Problemas de empaquetamiento relacionados 8 2.3 Estado del Arte 10 3 METODOLOGIA DE SOLUCION PROPUESTA 23 3.1 Implementación 2DBPOG Guillotinado 23 3.2 Descripción de la metodología utilizada 27 3.3 Lenguaje de programación de la implementación 30 4 ANÁLISIS DE RESULTADOS 31 4.1 Calibración de parámetros 31 4.1.1 Parámetros del algoritmo 31 4.2 Resultados computacionales 43 4.3 Calibración de resultados para algunos rangos exponenciales 43 4.3.1 Detalles de la implementación 47 4.3.2 Análisis de casos de prueba 47 4.4 Propuesta adicional del algoritmo implementado 52 4.4.1 Calibración de parámetros propuesta adicional 52 4.4.2 Análisis de casos de prueba propuesta adicional 56 5 CONCLUSIONES 61 6 BIBLIOGRAFÍA 6