基于人工干预的钣金零件排样算法

谢友宝，吕永海，张 睿，徐丽笑

(南昌航空大学航空制造工程学院，南昌 330063)

基于人工干预的钣金零件排样算法

谢友宝，吕永海，张 睿，徐丽笑

(南昌航空大学航空制造工程学院，南昌 330063)

针对飞机钣金零件排样中存在大量的凹形零件，这些零件尺寸差异较大，将人工干预排样与改进的最低水平线搜索算法相结合，对凹形零件内部再加以利用，提出一种可满足实际生产需要的排样算法。该算法利用最小包络矩形把不规则零件转化成矩形零件，并由人工选择凹形零件的凹形区域，利用传统的最低水平线搜索算法改进后的算法进行排样，若遇到凹形零件则在其中插入尺寸相对较小的零件，直到零件排至板材末端。自动排样完毕进入人工干预阶段，在一些空白区域再次排入零件，从而得到利用率较高的排料图。实验结果表明，将该算法应用到钣金零件排样系统中，无论是在系统运行时间上还是在排样利用率方面都能得到满意的效果。

凹形零件;人工干预;最低水平线搜索算法;最小包络矩形

0 引言

钣金零件大量地应用于机械制造、航空航天等许多行业中。零件排样结果的好坏对这些行业生产的合理性与经济性等指标皆具有重要影响。因此开发出一套高效、高利用率的排样方案是机械制造领域的一项重要课题，排样技术的研究具有非常重要的实际意义。

所谓板材排样是指将板材分割成各种形状的毛坯零件，其中的钣金零件包括规则零件和不规则零件。在我国许多企业的机械制造生产中，钣金零件排样很多是依靠人工经验试凑排样，经过多次反复后找出一个主观认为较好的排样方案［1］。随着计算机技术的不断发展，CAD/CAM已在越来越多的领域发挥作用，可以形象而逼真地完成自动优化排样过程。目前，规则零件的排料，其中比较典型的有校核碰撞法［2］、分支定界法［3］、人工智能算法等，从而使得规则零件的自动排样问题得到很好地解决。但是在一般情况下，大部分的待加工的钣金零件都是不规则零件。尤其是在飞机钣金零件的下料中，零件形状极不规则，很多零件内部还存在很大的凹形未利用区域，使得零件的排料算法运算异常复杂，生产效率大大降低。因此，国内外一些学者进行了大量的研究，其中运用最多的还是最小包络矩形法即先将不规则零件转化为矩形件(对零件进行图形聚合处理［4］求组合后的包络矩形)，再按规则零件排样算法进行排样。但是，该种排样方法在包络矩形内部的局部利用率大大降低，即使可以对部分零件进行图形聚合，但是该方法对很多零件而言具有很大的局限性。所以本文对不规则零件内部存在大的空余块进行再利用，对最最低水平线搜索算法进行了改进，并结合ObjectARX二次开发技术中图形数据库碰撞技术以及图块插入技术。采用人工干预排样，解决包络矩形局部利用率低的问题，开发出软件用时少，排样利用率高的算法。实验证明该算法是针对形状各异、大小不一的零件排样的有效算法。

1 排样问题描述

在钣金零件的排样中，假设参与排样的第i个零件为 Pi，则在板材 B 上参与排样的零件 P1，P2，P3，…Pi，…Pn必须满足以下约束条件［5］:

(1)Pi，Pj互不干涉，i，j=1，2，…，n 且 i≠ j。

(2)零件 Pi必须完全在板材 B 内，i=1，2，…，n。

(3)零件的排样必须满足一定的工艺要求，比如零件间距，板材边距等参数。

假设Si为零件i的实际面积，板材的长和宽分别为L，W，zi为零件i在板材上的插入因子，值为1或0。则原材料利用率R的目标函数为:

若 Di(xi，yi，αi，si，ei)为零件 i在板材中的具体位置，(xi，yi)为零件经旋转αi的内部各个点的坐标，(si，ei)为代表零件的工艺参数(本文只考虑零件间的间距和板材的边距)，则零件排样约束条件的数学表达式如下:

零件排样的目标为:在(2)、(3)、(4)三个约束条件下，使得板材利用率R达到(1)式的结果。

2 算法的求解过程

2.1 零件预处理

本文所涉及的算法基于最小包络矩形法，凹形区域采用人工选取，对于零件形状的描述只需解析零件包络矩形的特征。任何一个复杂的不规则零件都可以得到其最小包络矩形，方法是将零件在其AutoCAD图形中绕零件上面的任何一点以1°为单位进行旋转90°从而遍历所有可能的包络矩形，并依次计算其包络矩形面积从而得到其最小的。在本文中若最小包络矩形长度小于宽度，则将零件再旋转90°。获得最小包络矩形后采用SQL Server2000保存其信息(如长度、宽度、面积、零件类型等)。通过零件预览，若零件内部空余块很大可再加以利用，则将该零件标志为凹形零件，选取其最大的空白区域如图1所示，通过直接点击鼠标获取该面域。图中包含有该零件的包络矩形，其中虚线区域为所选的零件凹形区域。

图1 选取凹形区域

2.2 算法的实现

(1)零件的排序

零件的排序很大程度上影响和决定着排料图最终布局的合理性，根据每个零件对排料图最终布局的影响程度，我们对零件赋予不同的优先权。在排料实践中形成了很多对赋予待排零件优先权的规则，其中比较理想并且应用最多的有如下几种［6］:①按零件最小包络矩形面积递减顺序;②按零件最小包络矩形长度递减顺序;③按零件最小包络矩形宽度递减顺序。但以上三个规则都有其局限性，都忽略了其他两个因素对排料的影响。在本文中，考虑长条零件对排样结果影响较大，在考虑零件的面积时兼顾零件的长度，为了使长条零件获得排样优先权，定义如下条件作为判断标准:

其中l，w分别为零件最小包络矩形的长度和宽度，l≥w(零件预处理中将包络矩形长度小于宽度的情况进行了转换)。t作为条件中的判断指数，在应用中可根据需要自定。所以本文中优先按(5)式计算结果大小递减顺序排放长条零件，而后其他零件根据零件面积顺序排样。排样算法的定序同时也要兼顾定位的方式，与定位规则以及其他约束条件相匹配，才能使算法运行可靠。

(2)改进的最低水平线搜索算法

最低水平线法是一种不断更新水平线集的排放算法［7］，是目前算法中应用广泛的一种零件定位规则，而最低水平线搜索算法则是在它的基础上增加了一个搜索策略，其基本思想就是优先选择最低的水平线进行插入零件，若水平线长度小于当前零件的长度则优先搜索后面未排样的合适的零件，将该合适的零件与当前前待排零件进行置换，直到未找到合适零件再将水平线提升，并依次继续以上过程。

本文所涉及算法在传统的最低水平线搜索算法增加了以下几个策略:在排样过程中若板材已排放凹形零件后，则在后续每次排放零件时都优先搜索凹形零件并判断凹形零件中是否能排放该零件，把凹形区域作为新一板材进行排样，并在其中应用具有旋转策略的最低水平线算法，若在所有凹形零件中都无法插入待排零件，则将该零件转入到板材中进行排样;在搜索过程中考虑尽量将大零件优先排放，减小大零件对后续排样的影响，所以增加零件旋转策略即在水平线长度小于零件最小包络矩形长度时，则考虑包络矩形的宽度是否小于水平线长度，若满足则对零件进行旋转排样，否则再搜索下一零件;将搜索的可插入零件先排入板材中，随后将其从零件列表中删除，而不与当前待排零件进行置换。

在排样过程中，将未排零件集、凹形零件集、水平线集分别使用动态链表表示。零件集链表中零件顺序按照以上零件的排序规则，每排入一个零件则将其结点删除，当零件链表为空时零件排样结束;在凹形零件集中凹形区域顺序按照对应零件插入顺序，每遇到排入凹形零件则将链表末尾增加一结点;而在板材水平线集链表中水平线顺序按照从左到右的顺序，每插入一零件则将链表更新。排样的具体实现过程如下:

2.3 算例分析

将该算法应用于飞机钣金零件下料软件系统中，该系统采用AutoCAD二次开发工具中的ObjectARX开发技术，与VC++相结合在AutoCAD中生成排料图。自动排样过程采用ObjectARX插入块技术，生成排料图。本文算例排料图如图2所示。从排样结果可以看出，部分零件的形状极不规则但其内部空白区域得到了较合理的利用，其利用率为67%。

图2 自动排样的排样效果

3 人工干预

尽管在以上改进最低水平线搜索算法的应用下，不规则零件的排样得到了改善，但是从图中可以看出有部分区域仍然可以得到利用。在ObjectARX二次开发技术中，图形轮廓的判交相对算法较复杂，若由系统遍历所有可排样位置，计算量大，系统运行慢，但是在人工干预中由用户指定零件的排样区域，系统自动调整其排样位置，可使得排样的利用率在保证工作效率的情况下得到进一步的提高。图3所示为经人工干预后的排料图，其利用率达到了71%。

图3 人工干预后的排样效果

4 结束语

本文以最低水平线搜索算法为基础，结合不规则零件凹形区域的再次利用策略，提出改进的最低水平线搜索算法，将凹形区域的搜索融入其中。并且在自动排样完毕后采用人工干预，利用ObjectARX的零件判交技术，使得不规则零件得到更合理的排样。实验结果表明，本文所提出的算法在排样利用率以及排样效率方面都比较优秀，能解决零件之间尺寸相对大的排样问题，对飞机钣金零件的下料具有很重要的实际意义。

［1］郭乃成，王定强.计算机辅助冲裁排样优化［J］.锻压技术，1988，8(1):25-29.

［2］黄健.集CAD/CAM/CNC于一体的板材下料系统［J］.机械工业自动化，1997，19(3):20-22.

［3］Cihan H.Dagli.Knowledge-based Systems for Cutting Stock Problems.European Journal of Operation Research，1990，44(1/2):160-166.

［4］贾桂红.基于VC++/Object ARX的二维排料与NC自动编程系统设计［J］. 煤矿机械，2008，29(7):95-96.

［5］郑文清，陈建华.满足工艺品剪切要求的二维不规则排料算法［J］. 计算机技术与发展，2008，18(11):26-31.

［6］刘崇伦.计算机辅助二维排料与数控自动编程系统的实现［D］.华北电力大学，2005.

［7］王竹婷，刘林.改进的最低水平线搜索算法求解矩形排样问题［J］. 工程设计学报，2009，16(2):98-103.

Sheet Metal Parts Layout Algorithm based on Manual Intervention

XIE You-bao，LV Yong-hai，ZHANG Rui，XU Li-xiao
(Nanchang HangKong University，School of Aeronautical Manufacturing Engineering，Nanchang 330063，China)

Aiming at the existence of numerous concave parts which have large distance of dimensional gap between each of them in aircraft sheet metal parts layout，a layout algorithm is proposed which make use of the pack space of the concave parts secondarily while integrating Human-Computer Interaction with Improved Lowest Horizontal Search Algorithm to meet needs of actual production.Transforming irregular part into rectangular part with minimum envelop rectangle and picking the pack space of concave parts artificially，this algorithm take advantage of the improved conventional lowest horizontal search algorithm to insert parts on plate until the end of the plate is occupied while the concave part is inserted by the part with smaller dimension if that is lie.The stage of manual intervention proceeds to insert some parts in pack space when automatic layout stage is completed so as to get the layout graph with high layout utilization.The experimental results show that the improved algorithm could give satisfied results whether shorten the time of system running or improve the layout utilization when it is applied by the sheet metal parts layout system.

concave parts;manual intervention;the lowest horizontal search algorithm;minimum envelop rectangle

TP391.73

A

1001-2265(2011)02-0086-03

2010-08-16

谢友宝(1968—)，男，江西安福人，南昌航空大学航空制造工程学院教授，主要研究方向为机电一体化设备研制、数控技术、CAD/CAM技术、计算机软硬件系统开发等，(E-mail)xyb68@tom.com。

(编辑 赵蓉)