Research On Heuristic Algorithms For Packing And Cutting Problem

In the current era,the worldwide economics and trade develop rapidly,a great deal of work in the industrial field tends to be automated.The packing problem,an optimization problem which is often encountered in industrial production,plays a crucial role in improving work efficiency,reducing waste,increasing profits and promote automation.Different from the traditional three-dimensional container packing problem,this paper proposes a new research topic,three-dimensional polybag packing problem.The packing container is a two-dimensional flat plastic bag,and the plastic bag interior space changes according to the shape of the polybag.The three-dimensional polybag packing problem is very common in the logistics and retail industry.The study of this issue has important practical significance.In this paper,based on the original three-dimensional packing algorithm,the residual space dynamic adjustment algorithm is proposed.Based on the lookahead tree search algorithm,the optimal packing strategy is proposed.The test results on real data sets and self-generated data sets prove the effectiveness of our algorithm.Secondly,we apply the block generation algorithm and the residual maximum space representation method,which is used in the 3D packing problem,to the cutting problem of two-dimensional rectangular plates,and use the lookahead tree search algorithm to solve the Two-Dimensional Bin Packing(2BP)problem.The experimental results show that the quality of the partial solutions can outperform or be equal to the latest research results.This paper also studies an extension of Two-dimensional rectangular plate cutting problem--Two-dimensional cutting problem with defects.There are few researches on related topics in this area.For this problem,we apply the Tree Search algorithm at first.Besides,in the light of how to process defects,two solutions are proposed,and the recursive priority heuristic algorithm proposed by Zhang et al.[49]is used to cut the rectangles.Experimental results of this three schemes are compared.This will serve as a reference for the future study of this problem.