Research Of Packing Problem Of Difform Parts Based On Controur Feature Location Algorithm

Two dimensional packing problem, a kind of Non-deterministic Polynomial Complete problem with the highest computational complexity, has a wide cross traditional boundaries of the subjects such as computational geometry, artificial intelligence, neural network and operations research. It is extensively applied to these fields of the packing problem such as apparel, mechanical manufacture, glass and other industries. Researching on the nesting problem not only brings incalculable economic values and social values, but also promotes the social development oriented to the environmental protection and saving resource direction. With the constant development and update of the computer technologies, packing pattern has been developed from nesting by hand to computer aided optimal layout, from simple search algorithm to intelligent heuristic search algorithm. Otherwise, packing complexity increases as the shaping and computational complexity increases. The paper researches on the packing problem of difform parts based on Contour feature location algorithm, the main work and achievements are as follows:Firstly, the paper studies deeply on the status and trend of the packing problem home and abroad, and proposes the nesting system of difform parts, then establishes the nesting system's framework, describes the basic contents and theories in detail, which are important prerequisites for the computer aided layout of difform parts.Secondly, the paper puts forward an immune backtracking genetic algorithm as a core of the genetic algorithm. It introduces the operators of recruiting new members and memory to adjust the population characteristics of genetic algorithm, which is of benefit to enhancing abilities of the global search and convergence of the genetic algorithm. Besides, introducing the punishment mechanism of the backtracking algorithm regulates the local features of genetic algorithm. Those operators make the immune backtracking genetic algorithm converge at the global optimal result in a better and faster way, in addition to reduce the algorithm's time complexity.Thirdly, according to the "optimization theory" of dynamic programming, the paper establishes a mathematical model of the nesting algorithm, and proposes the thoughts of filling the valley areas formed by parts and sheet contours in order to provide maximum nesting space for the follow-up parts. Furthermore, the paper puts forward a contour feature location algorithm, whose principle is to fill the sheet contour's valley areas as a main aim and the convex areas as a supplement method. The strongpoint of the algorithm is that it makes full use of attribute information of the sheets and parts'nodes to achieve fast and accurately location.Fourthly, the paper describes the part's complexity based on its attribute information, and analyses the factors that affect the nesting utilization. Besides, the paper also researches the algorithm parameters influencing the nesting utilization by experimental data, and then sets up the selective basis of the algorithm parameters such as the population, cycle index, crossover and mutation parameter of the global algorithm. Finally, the paper deduces an approximate time formula of the nesting algorithm.Fifthly, the nesting algorithm can search all the possible directions of the parts, using heuristic information to calculate the rotation angle to find a better location. Nesting programs are written under the platform of Visual C++6.0, and finally achieves the outputs of the nesting information such as global sequences, sheet utilization, cycle index and graphical display.