启发式算法在矩形件优化排样中的应用.pdf

启发式算法在矩形件优化排样中的应用

摘 要

矩形件优化排样问题就是在一张或几张矩形板材上排放一系列指定数量和
规格的矩形零件，使板材的利用率最高。排样问题属于典型的组合优化问题，
已被证明为一类 NP 完全问题，具有重要的理论研究意义和实际应用价值。对
于小规模排样问题，采用现有的运筹学方法可以得出问题的最优解，对于大规
模排样问题，运用智能算法求近优解是目前较为有效的方法。
本文在学****研究了国内外多种算法的基础上提出了一种新的排样算法，该
算法以最低水平线搜索算法为基础并为其增加了一个评价规则，排样时对所有
未排零件进行评价，选择评价值最高的零件排入当前位置，这样使得算法在搜
索时具有很好的方向性，大大提高了板材的利用率。该算法的实验仿真结果以
及与其他算法的对比分析表明，本文所提出的算法可以得到较好的排样效果，
并且其解决问题的规模越大优化性能越好，适合于求解大规模排样问题。

关键词：矩形排样；评价规则；最低水平线搜索算法
1
The application of heuristic algorithm in rectangular optimal
packing problem

Abstract

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