Algoritmos heurísticos y exactos para problemas de corte no guillotina en dos dimensiones

Abstract

El problema de corte bidimensional consiste en satisfacer una demanda de objetos pequeños, piezas, a partir de un conjunto de objetos grandes, tableros, de forma que se maximice el beneficio o se minimice la pérdida del material sobrante. En esta Tesis se han abordado dos problemas concretos de corte en dos dimensiones. En ellos suponemos que las piezas a cortar y los tableros son rectangulares y que se permiten cortes que no sean de tipo guillotina. <br/>El primer problema tratado ha sido aquél en el que se dispone de un tablero del que se ha de cortar el máximo número de piezas de un solo tipo. Este problema es conocido como el Pallet Loading Problem, ya que su aplicación más habitual surge cuando un pallet rectangular se ha de llenar en la fábrica con el mayor número posible de cajas de un solo producto.. Nuestro trabajo ha consistido, en primer lugar, en el desarrollo de un algoritmo exacto, basado en procedimientos Branch and Cut, que no habían sido aplicados hasta ahora a este problema. Este algoritmo ha permitido resolver óptimamente problemas de hasta 100 cajas que no habían sido resueltos en los trabajos publicados hasta la fecha. En segundo lugar, se ha desarrollado un algoritmo heurístico basado en Tabu Search que resuelve de forma eficiente problemas de hasta 150 cajas.<br/>El segundo problema tratado es el problema en el que se dispone de un tablero, del que se ha de cortar un subconjunto de las piezas demandadas. Este problema admite, a su vez, cuatro subproblemas, dependiendo de la función objetivo (maximizar el valor de las piezas cortadas o minimizar el área no utilizada del tablero) y de la existencia o no de cotas superiores en el número de piezas a cortar de cada tipo. Se han desarrollado algoritmos heurísticos que resuelven las cuatro versiones del problema. Inicialmente se han desarrollado algoritmos constructivos rápidos, que pueden servir como subrutinas de algoritmos más complejos. En una segunda fase, se ha diseñado un algoritmo metaheurístico más complejo, GRASP, para obtener soluciones, que superan en calidad y menor tiempo de computación a las de los mejores algoritmos publicados.

The constrained two-dimensional cutting problem consists of satisfying the demands of small pieces from a set of large stock sheets with the objective of maximizing the total value of the pieces cut. In this work we have studied two particular two-dimensional cutting problems in which both pieces and stock sheets are rectangular and non-guillotine cuts are allowed.<br/> <br/>The Pallet Loading Problem (PLP) arises whenever identical rectangular boxes have to be packed on a rectangular pallet. Though the problem is initially three-dimensional, practical considerations usually mean that the boxes must be placed orthogonally with respect to the edges of the pallet, and in layers in which the vertical orientation of the boxes is fixed. With these restrictions the problem becomes the two-dimensional problem of packing a large rectangle, pallet, with the maximum number of small identical rectangles, boxes. The problem has many practical applications in distribution and logistics. <br/><br/>We have developed a branch and cut algorithm for that problem. The 0-1 formulation proposed by Beasley for cutting problems is adapted to the problem, adding new constraints and new procedures for variable reduction. We then take advantage of the relationship between this problem and the maximum independent set problem to use the partial linear description of its associated polyhedron. Finally, we exploit the specific structure of our problem to define the solution graph and to develop efficient separation procedures. We present computational results for the complete sets Cover I (up to 50 boxes) and Cover II (up to 100 boxes) which .had not been previously solved. In a second phase, we have developed a heuristic algorithm, based on Tabu Search, that solves efficiently problems with up to 150 boxes. <br/><br/>In the second problem studied several types of pieces can be cut from the large stock rectangle. For this problem we have developed a greedy randomized adaptive search procedure (GRASP). We investigate several strategies for the constructive and improvement phases and several choices for critical search parameters. We perform extensive computational experiments with well known instances previously reported, which show that our algorithm improves the best known results in terms of quality and computing time.