The Study Of 2D Irregular Packing Problem

The 2D Irregular Packing Problem is the main contents of this paper. The Packing Problem is widely spread in industry. It is a NP-complete combinational optimization problem. Packing Problem is widely used in garment manufacturing, sheet metal cutting, shoe manufacturing, and furniture making. The main objectives of this problem is how to maximize space utilization and minimize the wastage. In recently years, the research of the 2D Irregular Packing Problem is always the hot spot.This paper points out some disadvantages of the approximation algorithm and heuristic approach and presents using intelligence optimal algorithms to solve the problem. The intelligent optimal algorithms in charge of the rotating angle and computational geometry methods for irregular polygons such as rotating and shifting.In this paper, the Genetic Algorithm (GA) and Particle Swarm Optimization (PSO) algorithm are used to discuss the overall nesting process. Besides, a hybrid algorithm based on GA and PSO is introduced and selected to generate the best nesting results. To avoid the problem of trapping into local optimum at the end of the iterative process of the GAPSO, this paper proposes an improved hybrid genetic particle swarm optimization algorithm based on virtual force (VFGAPSO), and it is applied to the nesting field. Compare with the hybrid genetic particle swarm optimization algorithm, this one brings out a higher material utilization rate.In order to compare and quantitatively analyze the different results of the two algorithms, some experiments are made in this paper. Finally, the corresponding conclusion is drawn as following: (1)The nesting results of the single optimization algorithm is worse than the hybrid intelligent algorithm; (2) The nesting results of hybrid genetic particle swarm optimization algorithm based on virtual force is better than the hybrid genetic particle swarm optimization algorithm.