Research And Application Of Two-Dimensional Packing Algorithm Based On Beam Search

With the advent of industry 4.0,research related to industrial production is paying more attention to automation and intelligence.The study of two-dimensional packing problems plays an important role in this area.Solving such problems can provide an accurate and effective solution to realistic production,improve the utilization rate of related resources and promote the development of the industry.This paper studies three two-dimensional packing variant problems derived from practical stone cutting application problems.The irregularity of the outline of natural materials such as stone and the randomness of the internal defect area increase the difficulty of solving,traditional packing algorithms cannot be directly applied to such practical problems.This paper uses beam search as the basic search framework and designs different heuristic algorithms to solve the packing problems in different application scenarios.The main contributions of this paper can be included as follows:(1)A new heuristic evaluation based on the upper bound of the cutting line is proposed for the packing problem with guillotine constraint.It can adaptively guide the algorithm to select the cutting line according to the data situation without setting a fixed heuristic rule.Subsequently,we design a heuristic algorithm based on beam search and combine the proposed heuristic evaluation.The experimental results show that the proposed heuristic algorithm can obtain the optimal value of some test cases in a shorter execution time.(2)A method based on beam search is proposed to improve the two defect processing heuristic algorithms for the packing problem with guillotine constrain.The improvement combines the proposed cutting line heuristic evaluation and designs the evaluation function and search strategy of the two algorithms respectively.The experiment shows that the improved algorithm is better than the two original algorithms in most test cases.And there is an increase of 4.45%-15.7%for the average utilization rate under different constraints.(3)A novelty algorithm is proposed for the first time for the packing problem with irregular shape involved defects and cutting constraints.And a beam search algorithm based on strips and corresponding heuristic evaluation functions and search strategies is designed.The experimental results show that the proposed algorithm can find solutions in a shorter time,and achieve similar results under cutting constraints to the free cutting heuristic algorithm.The average utilization gap between the two algorithms is 0.3%.And in some test cases,the proposed algorithm is better than the free cutting heuristic algorithm.