New constructive algorithms for leather nesting in the automotive industry

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.