Algorithms for 2D Irregular Packing Problems
This project studies a heuristic based in the meta-heuristic genetic algorithm for the Strip Packing, Knapsack and Bin Packing problems. In all these problems, we consider two-dimensional irregular items to be packed in a bin of rectangular shape. In general, the proposed heuristic takes a list of items to be packed and builds the solution to the problem, taking into account the order of items in the list and some geometric features of the items already packed in a partial solution. We apply a local search on the solution using three operators that change the order of items in the list, allowing the generation of new solutions.
As an extension, we adapted the strip packing version of the heuristic to compact bins while packing new items when solving the Bin Packing and Knapsack problems. We conduct computational experiments to compare the proposed heuristics with others of the literature. Our heuristic for the Knapsack problem has obtained better results than previous heuristics. For the other problems, our heuristic obtained competitive results when compared to the ones of the literature.
In addition, we analysed the performance of three algorithms to generate the geometric structures called “No-Fit Polygons” (NFPs), which can be used for the verification of overlap among items when solving irregular packing problems.