Research On Two-dimensional Irregular Parts Parking Problems

Two-dimensional irregular parts parking problem is the important one which was applieded in many fields of productions and practices, it belongs to the NP-hard problems, it is very difficult to figure out this problem, so the research for this problem has broad applied background and academic meaning. Based on the methods at home and abroad, this paper does works mostly as follows:This article analyse the three stages of 2D irregular parts nesting,pretreatment of nesting parts, contact of parts, algorithm controlling of parts nesting. Mostly study the pretreatment methods of 2D irregular parts such as empty, arc-shaped profile and rectangular enveloping; Introduce the boundary expression of 2D irregular parts in nesting space, rotary space and some kinds of familiar colliding methods; Emphasize the basic operation and characteristics of Genetic Algorithm, according the limitations of GA, bring forward two methods of betterment: First, put the new method which named extremal optimization (EO)algorithm and GA together, EO could strengthen the local optimization, so the limitation of local defects in GA can be improved by doing this. Second, Combining GAs and generated boundary nesting algorithm which base on the BL rules, parking irregular parts on stock directly, uses GAs to locate the local optimal position, comparing to the commonly GAS, this new algorithm takes shorten runtime.