The Research Of Automatic Packing System Based On 2D Irregular Objects

Widely used in industry production, packing problem is an optimization problem which is concerned with finding a good arrangement of multiple different-sized objects in a large containing region without overlap. A good solution of this problem has a far-reaching meaning in greatly reducing the production cost in industry. It has been proved that the automatic packing problem is one of the NP-complete problems and has been widely studied through the years, especially the automatic packing problem of two-dimensional irregular shaped objects.The key to solve this automatic packing problem of two-dimensional irregular shaped objects, which is a NP-complete problem, is to do with the problem of capability and intractability. First, the calculate complexity should be reduced and the operation speed should be increased. Then, the use efficiency of the material should be greatly improved compared with manual-packing. To have a good time complexity and use efficiency, an algorithm for automatic packing problem based on heuristic search methods from artificial intelligence research is brought forward in the thesis. It has been proved to be an effective way to resolve packing problems. Through creating the outline polygon, confirming the choice criterion and orientation criterion, the parts automatic packing is completed. Considering the real application in shoemaking industry, the algorithm is extended from rectangular material to irregular material. The use efficiency of the material was improved through taking into consideration of the experience information. Using the heuristic search method, the next shoe-part being laid out was confirmed quickly. In the move algorithm, first move big steps then tiny steps to reduce many blind examines and improve precision.The solution to this heuristic based algorithm can be easily adjusted to other packing problems including pallet loading, textile cutting and container stuffing. Finally, some packing examples were produced to validate the algorithm through comparing the use efficiency of the material and the time complexity of the operation.