Resolviendo problemas bidimensionales de empaquetamiento y corte

Abstract

RESUMEN: En este proyecto se aborda el problema bidimensional de empaquetamiento (2DBPP) que consiste en colocar, sin solapamientos, un conjunto finito de rectángulos en el mínimo número posible de contenedores bidimensionales rectangulares idénticos. Estos problemas tienen numerosas aplicaciones industriales: en el sector de corte (madera, cristal, etc.), en el transporte de mercancías, en las telecomunicaciones, etc. El problema es NP-duro y muy difícil de resolver en la práctica en un tiempo razonable. Aún hoy en día la determinación de una buena formulación MIP es un reto. En este trabajo se ha optado por utilizar la formulación y el método de resolución presentado en [10], que es considerado el estado actual del arte en la resolución de (2DBPP) [5]. A lo largo del mismo se han utilizado distintos algoritmos como generación de columnas, MAC, ramificación y poda y heurísticos, junto con métodos de programación lineal continua y entera, alguno de ellos con implementación propia usando los lenguajes de programación Matlab y C. Además, se han realizado experimentos numéricos utilizando la colección de problemas NGCUT [2].

ABSTRACT: This project addresses the two-dimensional packaging problem (2DBPP) which consists of allocating, without overlaps, a finite set of rectangles into the minimum number of identical two-dimensional rectangular containers. These problems have many industrial applications: in the cutting area (wood, glass, etc.), in the transportation of goods, in telecommunications, etc. The problem is NP-hard and very difficult to solve in a reasonable time. Even today determining a good MIP formulation is challenging. We use in this work the formulation and resolution method presented in [10], which is considered the current state of the art for solving (2DBPP) [5]. Throughout it, different algorithms have been used such as column generation, MAC, Branch and Bound and heuristics, along with continuous and integer linear programming methods, some of them with our Matlab and C codes. In addition, numerical experiments have been performed on NGCUT problem set [2].