Solving Cutting and Packing Problems With Neural Networks

Abstract

This thesis focuses on using neural networks to solve cutting and packing problems (C&P problems). C&P problems are a set of combinatorial optimization problems that generally aim to fit as many smaller objects into larger containers. These problems are common in manufacturing processes like leather cutting, car manufacturing, and container packing. In this thesis, we have attempted to improve upon commonly used methods to solve C&P problems as efficiently as possible. There are two main areas to improve. The first is the time it takes to solve a problem. The second is the final score, commonly measured by the percentage of the container filled. C&P problems have two aspects to them, checking methods and solution methods. Checking methods check whether different pieces do not overlap with each other or the container's border. Solution methods decide what item will be placed and where it will be placed in the container. We have conducted seven experiments. The first five experiments aimed to improve checking methods, and the last two experiments focused on improving solution methods. We have found that it is probably not feasible to replace current checking methods with neural networks due to the high precision required. We do believe, however, that solution methods might benefit from including neural networks. We have created a neural network based solution method that could not improve the score (percentage of the container filled) of non-neural network solution methods. However, it did manage to solve problems 61 times faster. These results indicate a strong possibility that solution methods can be improved upon by the use of neural networks, which would allow C&P problems to be solved faster and with higher scores.