The Application Of Heuristic Algorithm In Rectangular Optimal Packing Problem

The optimal rectangular packing problem is to pack a series of rectangular items on the rectangular materials, to achieve the highest utilization. Rectangular packing problem belongs to typical combinatorial optimization problem. It has been proved for a class of NP-complete problem. Whether in theoretical research or in practical application, the problem has important significance. For small-scale packing problem, the use of existing operations research methods can be derived the optimal solution. For large-scale packing problem, the use of intelligent algorithm seek near optimal solution is more effective.Firstly, we study a variety of algorithms at home and abroad, and then proposed a new algorithm. The new algorithm intends to solve the rectangular packing problem by utilizing the lowest horizontal search algorithm and design an evaluation rule for it. During the packing procedure, the one with highest value will be chosen and packed in the current position after all the items to be packed being evaluated by the rule, which overcomes the randomness of the search process and optimizes the search direction. The experimental results and the comparative analysis of other algorithms show that the improved algorithm gives better placement pattern. In addition, the larger the problem is, the better the algorithm will perform. Therefore, the improved algorithm is suitable for solving large scale packing problems.