矩形件排样算法探讨

开篇：润墨网以专业的文秘视角，为您筛选了一篇矩形件排样算法探讨范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【摘 要】针对二维矩形件优化排样问题，提出一种新型的算法――矩形动态匹配算法。通过对零件的矩形化预处理，并自动正交排布使零件紧密靠接和定位，从而实现复杂不规则船体零件的矩形化排样，该算法亦可扩展用于三维空间零件的排样求解，实例证明其有效性。

【关键词】排样；矩形零件；优化；算法

【Abstract】For optimal nesting of rectangular parts of a two dimensional problem， a new kind of algorithm is put forward. The rectangular pretreatment and automatically orthogonal configuration make the location of parts more close， the rectangular optimization nesting of complex irregular ship parts is realized， the algorithm can be extended to 3d space parts. Examples show its effectiveness.

【Key words】Parking； Rectangular parts； Optimization； Algorithm

0 引言

排样优化技术是工业产品设计、制造中如何节约原材料、优化利用资源的重要手段。现实零件形状复杂，多为不规则零件，且制造特征和方法各异，如何采用有效的算法实现最优布局、提高原材料的利用率尤为重要[1-3]。文中基于对排样零件矩形化预处理提出了矩形动态匹配算法来实现零件的定位，具有较高的材料利用率。

1 算法简介

1.1 实现算法的前提条件

将一个矩形零件排放在矩形板材中，需要解决的问题有：

（1）多个矩形零件排放时的排放次序。

（2）矩形零件的排放位置问题。

1.2 入排矩形零件必要约束条件

（1）规定矩形零件仅有横放、竖放两个状态。如图1所示，A为竖放状态S，C为横放状态H，B为非法放置。采用左下角和右上角两端点坐标（Xli，Yli）（Xhi，Yhi）描述一个矩形。通过比较Xhi- Xli与Yhi- Yli的大小来确定矩形零件的状态。

（2）排样时，各个矩形零件之间不得相互重叠。为了满足任意两个矩形零件不重叠放置，须满足如下数学关系：假设两个矩形分别为A（xli，yli）（xhi，yhi）；B（xlj，ylj）（xhj，yhj），Max[xli-xhj，xlj-xhi，yli-yhj，ylj-yhi]>=0 i，j=1，2，3…N，i不等于j；

（3）排样时，各个矩形零件不得超出板材区域。

1.3 算法实现过程

在板材上的定位（排列）具体算法步骤[4-5]：

（1）输入给定板材件宽度B，确定原点（0，0）；

（2）输入各矩形零件Xi（ai，bi） i=1，2，3；

（3）计算面积Si=ai*bi；

（4）由大到小排列[Si] （即新数列S1>S2>S3……）；

（5）读入第一个矩形（最大的矩形）A1（xl1，yl1）（xh1，yh1），当xh1

（6）读入下一个矩形，检测板材是否有矩形状空穴，交叉比较矩形零件与空穴的长宽大小，若满足空穴条件，矩形零件排入空穴（优先横放状态），若不满足空穴条件，零件靠接这一层第一个矩形零件顶部排入靠近板材左端；

（7）读入下一个矩形重复上一步骤直到所有矩形零件排完。

2 零件的矩形化处理

零件组合矩形包络过程根据算法的复杂程度可以通过自动排样完成，也可以通过人工交互完成，通常采用方法有[6-9]：

3 应用实例

选择板材宽度1000 mm，长度不限，输入待排零件39个。基于上述排样算法，文中实现了39个零件排样定位并输出排样图。图4为39个零件的排样图，板材的利用率为89.18%。

4 结论

定位算法是求解最佳排样布局的核心技术，对于不规则零件更是难点。文中采用较为简单的定位算法，同时对待排零件进行矩形化预处理，大大降低了排样计算的复杂度，能解决一般矩形件的排样问题，具有较高的原材料利用率。

【参考文献】

[1]贾志欣，殷国富，罗阳.二维不规则零件排样问题的遗传算法求解[J].计算机辅助设计与图形学学报，2002，14（5）：467-470.

[2]毛定山，崔先国，李行，等.简单多边形集凸包的快速算法[J].工程图学学报，2007（6）：96-101.

[3]陈端兵，黄文奇.求解矩形packing问题的贪心算法[J].计算机工程，2007，33（4）：160-162.

[4]曾敏，王乘，刘琼梅.大规模定制板材排样的多种群蚁群优化算法[J].制造业自动化，2011，33（5）：59-62.

[5]曾凤华.剩余矩形匹配算法在矩形件排样中的应用[J].机电工程技术，2006，35（3）：64-65.

[6]李满江，孟祥旭.矩形件和任意多边形排样问题的算法及应用[J].贵州工业大学学报：自然科学版，2002，31（4）：126-130.

[7]岳为，余仁龙，崔永庆，等.锅炉下料中的非矩形件的排样优化算法[J].节能技术，1997（2）：44-45.

[8]罗为.二维不规则形状计算机自动排样系统的研究与设计[J].计算机工程，1995，21（6）：3-9.

[9]刘.基于HAPE的二维不规则零件排样算法及其性能研究[D].广州：华南理工大学，2011.