Exploring new constructive algorithms for the leather nesting problem in the automotive industry

Abstract

In this paper, we address the leather nesting problem that arise typically in the automotive companies. In this problem, irregular shapes (parts of car seats) have to be cut from another larger shape (natural leather hide). The problem is defined over two dimensions, and all the shapes are irregular and may contain different quality zones due to the natural origin of the leather hides and to particular quality requirements for the different parts of the seats. Our study is based on the real case of a large multinational company. We explore different approaches to solve this problem based on constructive procedures. The details of each of these procedures are discussed. We also briefly describe how to use the no-fit polygon in the context of these particular nesting problems. Some preliminary results on real instances are discussed at the end of the paper.