Study Of Packing Optimization Algorithm In Hull Building Automatic Packing System

Packing of the parts is also called the blanking,widely existing in all walks of life.The quality of packing scheme is directly related to the amount of material consumed.To improve the utilization rate of sheet material in packing can effectively reduce the production cost and directly bring to the factory substantial profits.With the development of industrial automation and the progress of computer technology,researchers have done more and more work on packing optimization.In allusion to practical of packing in all walks of life many optimization algorithm have been proposed.This article is mainly in regard to the study of packing in hull building.At frist,hull parts described by vector format is simplified to a polygon,then for rectangular envelope.according to the characteristics of the hull parts graphics are clustering by k-means.On the basis of the clustering results the hull parts are combined for rectangular envelope.the next is to fill the holes of the parts with small parts.And considering the influence of the edges preparation of the hull to the packing,it should be done to extend part geometry.All of the above is to prepare for packing.The hull parts which have been enveloped are packed by surplus rectangle algorithm.And it proposes improvement of the algorithm:adding evaluational principle about how to choosing surplus rectangle.It introduces a inarching algorithm based on extraction of the lines polygonal and a method computing the distance from point to line segment according to angle.And it is applied to the combination of parts for envelope and paking algorithm.All of the above is to solve the problem of local optimization in packing that the parts are fixed on sorting and rotating.Finally,genetic algorithm jions in the surplus rectangle algorithm in combination with inarching algorithm.Genetic algorithm is designed according to the concrete issue in packing of hull parts,for working out the best way of parts’ sorting and rotating.All of the above is to solve the problem of global optimization in packing that the parts are not fixed on sorting and rotating.