Research On Two-dimension Irregular Bin Packing Problem

Two-dimensional irregular bin packing problem(2DIBPP)is a kind of twodimensional packing problem,which is widely used in industrial production.Such as furniture plate processing,shipbuilding industry,automobile industry,sheet metal processing industry,clothing production,leather processing,etc.,it is necessary to deal with cutting and packing problems.Although the packing problem in different industrial fields has various restrictions and constraints,the common basic problem is to find an effective method for placing the required part pieces into the raw material bins,which makes area utilization of the raw material bins high to save as much material as possible.For the 2DIBPP problem,this paper proposes a heuristic placement algorithm(LS)for two-dimensional irregular pieces of a single bin size bin,which consists of three main parts.The first part is the assignment strategy algorithm,which uses the fast and well known best fit decreasing algorithm(BFD).BFD directly sorts all pieces according to the decreasing area of pieces,and assigns pieces according to area to rectangular bins according to the arranged order.The second part is one bin packing algorithm.Firstly,bottom-left algorithm is used to place the pieces into each bin to obtain the initial position of the pieces.Then two pieces are exchanged inside the bin.Finally,the overlap minimization algorithm is used to find their new positions under the condition of the minimum overlap value,so as to obtain an initial feasible solution.The third part is the local search algorithm,which performs a one-to-many exchange of polygonal pieces between two rectangular bins,and then calls the one bin packing algorithm of the second part to obtain a better feasible solution,until the utilization F is no longer i mproved or the time limit is reached,and the iteration is stopped and ended.Before introducing the packing algorithm,the geometric concepts of points,line segments,polygons and so on related to the subject are defined in this paper,because piecess and bins can be regarded as composed of irregular polygons.Then the packing problem and the packing solution are defined.Finally,the evaluation index of the feasible solution is defined,and the evaluation index F,which is more economical for materials,is selected.At the same time,this paper introduces the related overlapping collision technique and the least squares method.There are three kinds of classical overlapping collision techniques: enveloping rectangle method,pixel method and not-fit polygon(NFP)method.The overlap values are defined by the not-fit polygon.Then we introduce the normal equation algorithm for the linear least square problem and the gauss newton method for the nonlinear least square problem,and use them to design overlap minimization algorithms.There are two kinds of experimental data sets in this paper: the nested instance and the jigsaw puzzle instance.The two experimental data sets are used to test the LS algorithm,and the algorithm with the best solution in the lite rature is compared.In the nesting instance set,our results have a clear advantage,and for the jigsaw puzzle instance set,we have a better possible solution,but in a slightly longer time.Finally,our algorithm is applied in the process of cutting and packinging of panel furniture and good results are obtained.