New constructive algorithms for leather nesting in the automotive industry

Abstract

In this paper, we address one of the hardest two-dimensional cutting stock problems that can be found in industry. The problem is called the Leather Nesting Problem, and it consists in finding the best layouts for a set of irregular shapes within large natural leather hides with highly irregular contours, and which may have holes and quality zones. Here, we focus on a real case from the automotive industry, and in particular on the production of car seats. In this case, the irregular shapes that have to be cut from the hides are pieces of the car seats.

The practical relevance of this problem, and the potential value of the savings that good solutions may generate, contrasts with the very small number of contributions that have been reported in the literature. In this paper, we aim to contribute to the efficient resolution of this problem by exploring in depth many new different constructive procedures. Our approaches rely on the computation of no-fit polygons, and try to use the information provided by these polygons as much as possible. Different strategies for sorting, selecting and placing the pieces, and for evaluating the placement of these pieces are proposed and discussed. We also report on an extensive set of computational experiments using real instances. To evaluate our approaches, we applied the real criteria used by companies operating in this sector. These experiments show that our approaches can generate very high quality layouts within the same time limits as those needed by human operators.

Introduction

The cutting and packing area is a very active field of research within the combinatorial optimization community. In their recently proposed typology, Wäscher et al. [10] could identify more than 400 papers published in this area in the decade from 1995 to 2004. Despite this, the Leather Nesting Problem which is addressed in this paper and which belongs to this class of problems remains a very poorly studied problem. As shown below, only very few publications address this problem, and many of them focus on special cases with some additional constraints that simplify the problem in practice. This situation contrasts with both the practical relevance of the problem and the potential value of the savings that may result from the generation of good solutions given the value of the raw material involved.

The Leather Nesting Problem (LNP) is a two-dimensional cutting stock problem that consists in finding the best layouts for a set of irregular shapes within the boundaries of natural leather hides, whose contour is also irregular. A natural leather hide may have holes and zones with different quality levels. In fact, the surface of the leather hides can be very heterogeneous. Indeed, there can be a large number of different quality zones and holes with different sizes and shapes. Furthermore, their distribution through the hide may vary significantly. The degree of irregularity of the contour of the hides is also very high. As a consequence, two leather hides are typically very different from each other.

The characteristics of the irregular shapes that have to be cut from these hides depend typically on the application that is considered. In this paper, we address the real case of a large multinational company that produces seats for the automotive industry. Here, the irregular shapes to be cut from the leather hides are pieces of these car seats. The pieces may have holes and must also satisfy minimum quality requirements defined by the clients. These requirements translate into quality zones within the pieces, which in turn restrict the position of the pieces within the hides. According to the typology presented in [10], the LNP addressed in this paper can be classified as a 2D-RCSP (two-dimensional residual cutting stock problem). All the details of this particular LNP will be discussed in Section 2.

To the best of our knowledge, the first results published in the literature concerning the solution of the LNP are due to Heistermann and Lengauer [7]. The authors proposed a greedy algorithm to solve the problem. Their approach starts by identifying a limited and empty region of the hide in order to place one of the available pieces. This region is called the focus, and it may be fixed if it is always located in the same part of the hide, or variable if its position within the hide may be different from one iteration to another. In the latter, the best focus is chosen among all the possible foci by evaluating a multi-criteria quality function for each focus. The authors restrict the placement of the pieces to a limited region of the hide to improve the efficiency of their algorithm.

Once the focus has been determined, a subset of pieces is selected from the whole set of pieces that remain to be placed. These pieces are selected by first inspecting the geometry of their contour, and by comparing it with the geometry of the focus. This comparison is made by analyzing the inner angles of the pieces, and the lengths of the corresponding edges. The pieces whose geometry best approximates the geometry of the focus are selected. Among the selected pieces, only those that favor the construction of potentially good layouts are chosen. The area of the pieces and its quality zones are used as criteria in this second step.

The placement of each selected piece is then evaluated using different criteria such as the area of the piece and the distance between its contour and the borders of the hide and the current partial layout. Note that this placement may be infeasible. The authors overcome this problem by applying compaction techniques.

Heistermann and Lengauer [7] report on computational experiments conducted on real instances from the furniture and automotive industry. However, they do not distinguish between the results obtained for each type of instances. Note that in the furniture industry, the pieces tend to be much larger than in the automotive industry. To evaluate their approach, they used the average material usage per hide. The authors claim that their approach was becoming competitive with human operators.

In [5], Crispin et al. describe two genetic algorithms based on different coding methodologies to solve the LNP arising in the shoe manufacturing industry. Beyond the quality and non-overlapping constraints that apply to the LNP addressed in this paper, the problem tackled by Crispin et al. considers additional directionality constraints that reduce the solution space by imposing specific directions for the pieces in given regions of the hides.

The first algorithm suggested in [5] is based on the placement of pieces within a limited window area. The pieces are placed so as to maximize the space utilization locally. Their second algorithm relies on connectivity graphs built using no-fit polygons and whose edges are related to pieces that may touch in a feasible layout. In both cases, no-fit polygons are used to ensure that the placement of the pieces is always valid. The authors report on computational experiments, and claim that their approaches generate solutions with values of material usage comparable with the results obtained by human operators.

In [12], Yuping et al. proposed a simulated annealing algorithm for the LNP with no quality zones. To generate valid placements, the authors perform translation and rotations of the pieces using auxiliary sliding procedures. Their approach is based on a so-called re-annealing schedule which is faster than other classical annealing schedules. The authors compared their approach with the results obtained when the nesting is done manually. On average, they achieved a better material usage in nearly the same time limits as those needed by human nesters which are between 15 and 30 min. The authors claim that their approach is effective when the number of pieces is moderate.

More recently, Yuping and Caijun [11] proposed a new solution procedure based on genetic algorithms and simulated annealing for the case where the hides have defects but no quality zones. The shapes representing the pieces and hides of the problem are discretized using grids of pixels in a way that is similar to the approach proposed in [2]. The pieces are placed on the hides using a bottom-left heuristic. To look for good sequences of pieces to place on the hides, the authors developed a novel approach combining a genetic algorithm with simulated annealing. The cooling schedule of their simulated annealing algorithm controls the mutation rate of their genetic algorithm, and according to the authors, it improves the convergence to global optimal solutions. Computational results are described for a case with two hides. The authors indicate that their approach can find solutions with a percentage of material usage greater than 70% within 1 h.

In [9], Lee et al. described an heuristic for placing irregular shapes on multiple sheets. Their approach consists in placing the shapes one-by-one on the sheet using a simple nesting rule, and then moving and rotating the shape so to as to improve its placement. Although the authors claim that their approach can be used when the sheets are irregular, they report only on a single experience with one instance for this particular case. Furthermore, they do not consider the existence of quality zones either on the sheets or on the shapes.

Although many different approaches have been proposed to solve two-dimensional cutting stock problems with irregular shapes (see [8], for example), the problems that are addressed do not typically fit the specificities and requirements of the LNP. Even among all the contributions described above, only Heistermann and Lengauer [7] proposed a solution approach for the same problem as the one addressed here.

In this paper, we describe a new set of constructive algorithms for the general LNP in which the hides and the pieces may have holes and quality zones. We explore in particular different strategies for grouping, selecting and placing the pieces within the hides, and for evaluating the quality of the placement of a piece at a given point. Our approaches are based on the computation of no-fit polygons (see [4] for a comprehensive survey). To the best of our knowledge, these are the first algorithms reported in the literature for this general LNP that use this technique.

The results described in this paper are based on the real case study described above. In this context, the problem consists in finding the best layouts for a set of pieces (from a given production order) on a set of leather hides. Hence, the LNP reduces to a cutting stock problem on multiple hides. Furthermore, the criteria used to evaluate the quality of the solutions are not only based on the percentage of material usage on a single hide, but it also takes into account the usable space left on the last hide used to cut the order. All our algorithms have been implemented and tested using real instances.

The paper is organized as follows. In the next section, we describe all the elements that define the general LNP addressed in this paper. In Section 3, we discuss the approaches used to deal with the geometric aspects of the problem. In Section 4, we describe in detail the different parts that define our constructive algorithms. In Section 5, we describe the criteria used to assess the quality of a solution. Our computational experiments conducted on real instances are reported in Section 6. Some final conclusions are drawn in Section 7.