Research Of Two-Dimensional Irregular Pakcing Problem With Guillotine Constraints

The problem of two-dimensional irregular packing is a kind of packing problem,which means that a series of parts with different sizes and shapes are placed in a given space to reduce the waste of raw materials by finding the scheme with the highest utilization rate.Packing problem belongs to NP complete problem,which is widely used in many fields of industrial production and manufacturing,and it is also a hot research topic.This paper mainly focuses on the two-dimensional irregular pracking problem with guillotine constraints.Firstly,aiming at the judging method of two polygons,this paper had give the definition of the maximum moving distance between polygons.On this basis,an algorithm based on the maximum calculating the maximum moving distance required for a convex polygon to slide into another convex polygon.The disposable position of the placement position avoids the traditional NFP preprocessing and intersection judgment method.Secondly,due to the constraints of packing problem under guillotine constraints,aseries of cutting is required for packing space in each round of packing process.In the paper,the packing tree is constructed to store and maintain the cutting space and packing position after the packing process.Finally,aiming at the problem that the traditional heuristic positioning algorithm will lead to unreasonable layout results,this paper proposes a heuristic positioning algorithm based on sliding track to increase the fitness by defining the maximum moving distance on the basis of the traditional heuristic algorithm.On the basis of the standard test data set,a series of packing effect maps are obtained through the experiments of several groups of experimental data.After analysis and comparison,the following conclusions can be drawn: under different groups of experimental data,the heuristic algorithm constructed in the paper has reached the lower bonud of theory and achieved high utilizaition rate of packing results;based on maximum shift.The heuristic algorithm of moving distance can greatly reduce the time complexity,thus greatly reducing the overall time consumption of the packing process.