Nesting problemsexact and heuristic algorithms

Zusammenfassung

Nesting problems are two-dimensional cutting and packing problems involving irregular shapes. This thesis is focused on real applications on Nesting problems such as the garment industry or the glass cutting. The aim is to study different mathematical methodologies to obtain good lower bounds by exact procedures and upper bounds by heuristic algorithms. The core of the thesis is a mathematical model, a Mixed Integer Programming model, which is adapted in each one of the parts of the thesis. This study has three main parts: first, an exact algorithm for Nesting problems when rotation for the pieces is not allowed; second, an Iterated Greedy algorithm to deal with more complex Nesting problems when pieces can rotate at several angles; third, a constructive algorithm to solve the two-dimensional irregular bin packing problem with guillotine cuts. This thesis is organized as follows. The first part is focused on developing exact algorithms. In Chapter 2 we present two Mixed Integer Programming (MIP) models, based on the Fischetti and Luzzi MIP model. We consider horizontal lines in order to define the horizontal slices which are used to separate each pair of pieces. The second model, presented in Section 2.3, uses the structure of the horizontal slices in order to lift the bound constraints. Section 2.5 shows that if we solve these formulations with CPLEX, we obtain better results than the formulation proposed by Gomes and Oliveira. The main objective is to design a Branch and Cut algorithm based on the MIP, but first a Branch and Bound algorithm is developed in Chapter 3. Therefore, we study different branching strategies and design an algorithm which updates the bounds on the coordinates of the reference point of the pieces in order to find incompatible variables which are fixed to 0 in the current branch of the tree. The resulting Branch and Bound produces an important improvement with respect to previous algorithms and is able to solve to optimality problems with up to 16 pieces in a reasonable time. In order to develop the Branch and Cut algorithm we have found several classes of valid inequalities. Chapter 4 presents the different inequalities and in Chapter 5 we propose separation algorithms for some of these inequalities. However, our computational experience shows that although the number of nodes is reduced, the computational time increases considerably and the Branch and Cut algorithm becomes slower. The second part is focused on building an Iterated Greedy algorithm for Nesting problems. In Chapter 6 a constructive algorithm based on the MIP model is proposed. We study different versions depending on the objective function and the number of pieces which are going to be considered in the initial MIP. A new 11 idea for the insertion is presented, trunk insertion, which allows certain movements of the pieces already placed. Chapter 7 contains different movements for the local search based on the reinsertion of a given number of pieces and compaction. In Chapter 8 we present a math-heuristic algorithm, which is an Iterated Greedy algorithm because we iterate over the constructive algorithm using a destructive algorithm. We have developed a local search based on the reinsertion of one and two pieces. In the constructive algorithm, for the reinsertion of the pieces after the destruction of the solution and the local search movements, we use several parameters that change along the algorithm, depending on the time required to prove optimality in the corresponding MIP models. That is, somehow we adjust the parameters, depending on the difficulty of the current MIP model. The computational results show that this algorithm is competitive with other algorithms and provides the best known results on several known instances. The third part is included in Chapter 9. We present an efficient constructive algorithm for the two dimensional irregular bin packing problem with guillotine cuts. This problem arises in the glass cutting industry. We have used a similar MIP model with a new strategy to ensure a guillotine cut structure. The results obtained improve on the best known results. Furthermore, the algorithm is competitive with state of the art procedures for rectangular bin packing problems.