Research On Heuristic Algorithms For Two Types Of Rectangle-packing Problem

Packing problem is a classic combinatorial optimistic problem and is claimed as NP-hard. Because the problem can be applied to many engineering fields, such as stock cutting, transport tool and satellite cabin layout design, etc., many researchers from engineering, math and computer science are researching the problem and have proposed numerous good methods for the problem. In this thesis, two types of typical packing problems, the Pallet Loading Problem and the Strip-Packing Problem, are studied, and algorithm is designed for each of them. The experiment results demonstrate the two algorithms are efficient. On one hand the two algorithms can be used in the actual engineering layouts. On the other hand they are beneficial to the further understanding of the problem's complexity and solution strategy. Contents of the thesis are as following:Firstly, research purpose is brought forward based on summarizing and analyzing current research status both domestic and abroad.Secondly, the research methods of the pallet loading problem are induced. Branch and Bound Method is analysed. Upper bounds for the Pallet Loading Problem are summerizaed.Thirdly, G&K algorithm is analysed and the algorithm's shortage is pointed out. Then G&K's sub-algorithm is improved by supplement packing pattern and proposing some new strategy and the instances are gived to demonstrate that the improvement is efficient. Based on the full theory analysis, a new combining sub-algorithm is proposed by combining the improved sub-algorithm and HB algorithm to replace G&K's sub-algorithm. G&K algorithm is completely improved by designing the main-algorithm at last. The experiment results demonstrate that the improved algorithm can find more instances with optimal solution and is faster to some instances.Fourthly, the general GRASP metaheuristic is analysed and the GRASP algorithm proposed by Valdes et al for the strip packing problem is researched. Basing on having studied theory knowledge, some new strategy is proposed to improve the Valdes's algorithm and to get a new GRASP algorithm. Comparing the thesis's experimental results with improvement front results shows that the thesis's algorithm is efficient.In the end, conclusions are drawn and the future research directions are suggested.