Research on Genetic Hybrid Algorithm for Rectangle Packing Problem with Multiple Constraints

A hybrid algorithm based on an improved three-stage nesting algorithm and an improved genetic algorithm is proposed for the optimization problem of two-dimensional rectangular parts nesting. Firstly, an integer programming model with the objective of maximum utilization rate is established, and then the genetic algorithm is used as the nesting algorithm to determine the nesting order of rectangular parts. In order to improve the performance of the genetic algorithm, the improved SFM chaotic mapping method is used to initialize the population, and the triple tournament selection operation and Gaussian disturbance strategy are introduced to improve the convergence speed and global search ability of the algorithm. For the positioning of rectangular parts on the blank, a three-stage cutting and nesting algorithm is proposed, which introduces the concept of "layer" and restricts the length of the blank to meet the requirements of guillotine-cut and rotation of rectangular parts. Finally, the proposed algorithm is compared with other advanced algorithms, and the results show the effectiveness of the proposed algorithm.

1 Introduction

The optimization layout problem of rectangular components, also known as the cutting problem or the filling problem [1], refers to the situation where a certain type and quantity of rectangular components are laid out on a given rectangular container (motherboard) with a fixed width and height, in order to maximize the utilization of the motherboard or minimize the number of boards used. This problem is widely used in industrial scenarios such as sheet metal cutting, metal cutting, and newspaper layout [2]. This problem is also an NP-hard [3] problem, attracting scholars at home and abroad to continuously research and solve it.