In this project we have developed a new method to solve the problem of cutting non-convex objects, based on genetic algorithms. The results obtained show a higher performance than the research paper used as reference. The performance of our method guarantees an additional 5% savings in raw material with respect to the reference method.

The filling factor obtained In the next figure was 72.7%, the algorithm executed 402 evaluations of the fitness function, each evaluation took 2-5 seconds. At the top of the figure we can observe that there is room for another piece, which could lead to an efficiency close to 80%.

To model the solution we have proposed a variant of the “Traveling Salesman Problem” or TSP, using the gateway to the city as an additional criteria for optimization. That is, the traveling salesman can use the north entrance, south, east, south-west, etc., and the algorithm will determine the most convenient gateway to minimize costs. The gateway represents the angle of each element in the cutting problem.

Our GA algorithm uses permutation chromosomes. Each gene of the chromosome will be encoded using 16 bits. The lower byte defines the city to visit (up to 256 options), and in the high byte, 7 bits are used for the angle and one bit is reserved. As fitness function we have selected the sheet length.

We define a crossover operation for the high byte, and a crossover operation for the low byte. In the high byte we use a crossover with a single cut. In the low byte the crossover operation produce two new permutations.

The following video shows the algorithm in progress.

The next figure shows, on the left, the result obtained from an paper of reference, where the reported efficiency was 69%. On the right we can see the result obtained with our algorithm, which is different from the first figure, the efficiency obtained was 73.7%. This result shows that our method provides a 4.7% of savings in raw material.