Algorithms for cutting and packing problems

Abstract

This thesis analyzes two fundamental problems in the "Cutting and Packing" (C&P) field: first, a specific problem called Pallet Building Problem which has practical constraints is approached; then base variants of the so-called Rectangular Cutting Problem are addressed.

In C&P problems, there are sets of small objects (items) that must be cut/packed from/onto large objects (containers). We address the case where containers are identical one another: in terms of PBP, the geometric shapes for both the items and containers are 3-dimensional boxes; on the other hand, in the case of RCP, the geometric shapes are 2-dimensional rectangles, somewhat simplifying the problem, but not making it easy per se.

In the PBP, the aim is to pack a given set of items into layers and then build pallets by stacking layers one on top of the other, by minimizing the number of pallets used. In the RCP, the aim is to cut a set of items from a container, while maximizing a profit function. We are considering a base set of constraints for both problems. They are as follows: (a) items must fit entirely within the container; (b) items cannot overlap.

When addressing PBP, we take into account a larger set of constraints. In this case, some non-trivial operational constraints that originate from a real-world automated application are also included: in practice, items are grouped into families and must be packed into horizontal layers. To facilitate loading/unloading operations, items from the same family packed into the same layer should be contiguous with one another and at least one of them must be visible from the outside. In addition to these, we consider stackability and fill factor constraints.

The techniques we develop to solve the target problems are heuristic, exact, metaheuristic and matheuristic algorithms.

Due to a more complex set of constraints, we divide the PBP into two phases: (i) layer building; (ii) pallet building. In simple terms, items are first grouped into horizontal layers, and then layers are stacked one over the other to form pallets. To solve this problem, we propose heuristics and matheuristics based on heuristics and integer linear models. The main heuristic we highlight is the adaptation of the Extreme Points Heuristic (Crainic et al. 2008) to meet the new constraints. In regards to the mathematical models, we propose them for solving specific parts of the problem, since a single model for the entire problem might be unfeasible. We then propose matheuristic algorithms by taking advantage of these efficient heuristics and the mathematical models. In addition to that, a significant improvement in the solution was noticed when adapting the PBP to the GRASP metaheuristic with reactive method.

When it comes to RCP, we propose a new technique to generate both the guillotine and first-order non-guillotine (G5 pattern) cuts. Based on the original and innovative idea of floating cuts, this model is a tree search where branching occurs by successive cuts (detailed in Chapter 8). However, unlike all known models, the exact position of the cuts is not fixed, instead it remains floating until a concrete small rectangle (also known as item) is assigned to a child node. This model does not include decision variables neither for the position coordinates of the items nor for the coordinates of the cuts. Under this framework, it is possible to address problems where: items have fixed orientations or can be rotated by 90 degrees; the value of each item is either proportional to its area or arbitrary; the demand of each item type is either equal to one or has a multiplicity greater than one. We present the entire formulation, along with algorithms that support the management of the variables’ indices, required when tree search procedures are modeled as mixed-integer problems. In addition to that, we add a set of valid inequalities to the model to reduce symmetry and to strengthen the formulation.

Extensive computational experiments were performed using real life instances from an Italian company as well as benchmark instances taken from literature in order to evaluate the algorithms effectiveness. We carried out a comprehensive analysis of the results using the proposed techniques, detailing their pros and cons. In a general analysis, the results confirm the power and flexibility of the algorithms and models. However, even more importantly, this is a new way of looking at these problems which could serve as a catalyst to even better approaches, with the consequent economic and environmental benefits.