| Summary: |
Cutting and Packing problems are hard Combinatorial Optimization problems that naturally arise in all industries and services where pieces of material or space must be divided into smaller non-overlapping pieces, so that waste is minimized. All the Cutting and Packing problems have in common the existence of a geometric sub-problem, originated by the natural item non-overlapping constraints. An important class of Cutting and Packing problems are the Nesting problems which occurs when raw materials have to be cut into pieces with irregular shapes, see file nesting.pdf. Nesting problems, also known as Irregular Packing problems, naturally arises in the garment, footwear, tools manufacturing and shipbuilding industries. Besides being a hard combinatorial optimization problem, like other Cutting and Packing problems, the non-rectangularity (i.e. the irregularity) of the pieces increases the difficulty of the geometric problem. In fact, given two non-convex polygons and their relative positions, to know if they overlap is a non-trivial time-consuming task that enormously limits the computational effort that can be dedicated to optimizing nesting solutions.
Several challenges remain open in the Nesting problems field. Some of these challenges are common with all Cutting and Packing problems and are due to the combinatorial nature of these problems. Naturally, the challenges that are specific to Nesting problems are the geometric ones, due to the non-regularity geometry of the pieces involved. Moreover these geometric challenges do not allow the combinatorial ones being properly tackled. This fact explains the reason for the majority of nesting approaches being based on heuristics, rather than in optimization algorithms. Additionally, the lack of appropriate geometric tools leads to the frequent necessity to simplify some geometric issues. For instance, pieces with non-straight borders (arcs and splines) are commonly approximated by a set of external straight lines. A  |
Summary
Cutting and Packing problems are hard Combinatorial Optimization problems that naturally arise in all industries and services where pieces of material or space must be divided into smaller non-overlapping pieces, so that waste is minimized. All the Cutting and Packing problems have in common the existence of a geometric sub-problem, originated by the natural item non-overlapping constraints. An important class of Cutting and Packing problems are the Nesting problems which occurs when raw materials have to be cut into pieces with irregular shapes, see file nesting.pdf. Nesting problems, also known as Irregular Packing problems, naturally arises in the garment, footwear, tools manufacturing and shipbuilding industries. Besides being a hard combinatorial optimization problem, like other Cutting and Packing problems, the non-rectangularity (i.e. the irregularity) of the pieces increases the difficulty of the geometric problem. In fact, given two non-convex polygons and their relative positions, to know if they overlap is a non-trivial time-consuming task that enormously limits the computational effort that can be dedicated to optimizing nesting solutions.
Several challenges remain open in the Nesting problems field. Some of these challenges are common with all Cutting and Packing problems and are due to the combinatorial nature of these problems. Naturally, the challenges that are specific to Nesting problems are the geometric ones, due to the non-regularity geometry of the pieces involved. Moreover these geometric challenges do not allow the combinatorial ones being properly tackled. This fact explains the reason for the majority of nesting approaches being based on heuristics, rather than in optimization algorithms. Additionally, the lack of appropriate geometric tools leads to the frequent necessity to simplify some geometric issues. For instance, pieces with non-straight borders (arcs and splines) are commonly approximated by a set of external straight lines. Another example is the usual necessity to restrict the admissible placement orientations to a small set of discrete admissible rotations. From the above open challenges, we propose to tackle the geometric ones, by providing tools to directly deal with non-straight lines and admissible continuous placement orientations. This will allow for an improved quality of nesting algorithms solutions, with less waste and therefore a positive impact, both economic and environmental. |