Research On Two-dimensional Irregular Packing Problem With Holes And Cavities

The packing problem is the NP-complete problem with the highest time complexity,which is widely used in many industries such as stone,garment and aerospace to increase the economic efficiency of enterprises by reducing the scrap rate of materials,achieving a win-win situation of protecting the environment and increasing profits.The two-dimensional irregular packing problem with holes and cavities means that,given a two-dimensional raw material and a series of pieces to be scheduled with holes/cavities of different sizes and shapes,the pieces to be scheduled are placed into the raw material to maximize the overall utilization of the raw material,provided that they do not overlap with each other in the raw material area.In a geometric sense,a hole is a case where the part to be arranged has a separate embedded polygon,while a cavity is a case where the part to be arranged has a small entrance at the boundary and extends to a large internal area.In this paper,we study the problem of the displacement of a part to be scheduled with holes and cavities,and the main research work is as follows.1.A data structure representation of the part to be scheduled with holes and cavities is given.2.On the basis of the ray method,a positioning algorithm with the minimum moving distance adapted to the characteristics of holes and cavities is given;this algorithm can not only calculate the direct positioning algorithm of an arbitrary polygon moving through the slide to the contact position of another polygon,but also deal with the case with holes and cavities,avoiding the traditional NFP preprocessing and the corresponding polygon intersection algorithm in dealing with holes and cavities difficulties of traditional NFP preprocessing and corresponding polygon discriminant algorithms in handling holes and cavities,effectively reducing the overall computational time consumption.3.A new heuristic algorithm is constructed;a gap-filling algorithm is proposed to reduce the blank area generated by the row of samples;and benchmark sample data are selected for algorithm experiments and result comparison.On the basis of the benchmark test data set,the following conclusions can be obtained after analysis and comparison: the proposed algorithm can quickly deal with the non-regular nesting problem with hole and cavity characteristics,and the nesting results are more satisfactory,the time consumed is stable,and the raw material utilization rate is more satisfactory,which can effectively reduce the waste of raw materials and achieve the expected purpose.