（机械制造及其自动化专业论文）海洋钻井平台二维零件切割排料技术研究.pdf

中文摘要 本文在总结前人关于排料问题的研究成果的基础上，根据海洋钻井平台工程的 行业特点，对二维不规则零件的排料问题和切割问题展开研究，搭建了相应的自动 排料及数控编程系统框架，并对排料问题深入研究，开发了系统的自动排料部分。 论文首先对海洋钻井平台工程中的二维不规则零件特征进行分析，应用 a u t o c a d 二次开发技术实现了图形数据获得、数据管理并设计了高效实用的零件操 作算法。在此基础上，针对海洋钻井平台二维不规则零件的排料问题提出了一种高 效实用的算法，即启发式搜索算法与遗传算法相结合的排料算法。首先根据行业特 点定义合适的启发规则，利用启发式搜索算法对零件进行初次排料，形成初始排料 方案。然后利用遗传算法对初始排料方案进行优化。初始排料方案作为遗传算法初 始种群的一个母本，对其进行受迫变异产生一个相对优秀的初始种群，再进行遗传 操作。为了充分发挥遗传算法的全局搜索的优势，同时又能得到较高的搜索效率， 提出“染色体成长法”对染色体进行解码。把体现零件种类信息的染色体转化为实 际待排零件的序列，再把这个零件实体序列通过启发式搜索空白区域的方法进行填 充，把染色体的最大优势发挥出来。这样既充分利用了遗传算法的全局搜索能力， 又利用启发式搜索算法大大提高了搜索效率。 本文在科学的排料算法研究的基础上，根据人机交互的设计原则，在a u t o c a d 平台上开发出了与a u t o c a d 完全兼容并且简单易用的排料系统。最后总结了算法 与系统的优缺点，对算法和系统的改进提出了一些建议。 关键词：排料算法火焰切割启发式搜索遗传算法海洋钻井平台 a b s t r a c t t h i sp a p e rs u m m a r i z e st h ep r o d u c t i o no ft h ef o r m e rs c h o l a r sa b o u tt h en e s t i n g p r o b l e m b a s e do nt h ec h a r a c t e r i s t i co fi n d u s t r yo fo f f s h o r ed r i l l i n gp l a t f o r m ，t h i sp a p e r s t u d i e st h et h en e s t i n gp r o b l e ma n di n c i s i n gp r o b l e mo ft h et w o - d i m e n s i o n a li r r e g u l a r p a r t s ，b u i l d s a s y s t e m f r a m ef o r t h ea u t o m a t i cn e s t i n ga n dn u m e r i c a lc o n t r o l p r o g r a m m i n g ，a n d d o e sad e e pr e s e a r c ha b o u tt h e n e s t i n gp r o b l e m o ft h e t w o d i m e n s i o n a li r r e g u l a rp a r t s ，f i n i s h e st h ep a r to fa u t o m a t i cn e s t i n g f i r s t l y , a n a l y s i sa b o u tt h ec h a r a c t e r i s t i c so ft h ep a r t su s e di no f f s h o r ed r i l l i n g p l a t f o r mh a sb e e nd o n e t h e n ，t h i sp a p e ra c h i e v e st h ef u n c t i o no fg a i n i n ga n dm a n a g i n g g r a p h i c s d a t a ，a n da l s od e s i g n se f f i c i e n tm e t h o d so fo p e r a t i n gp a r t sw h i c hh a v eah i g h p r a c t i c a l i t y a n db a s e do nt h o s em e t h o d s ，t h i sp a p e rr a i s e da ne f f i c i e n ta r i t h m e t i ct o r e s o l et h en e s t i n gp r o b l e mo ft h et w o - d i m e n s i o n a li r r e g u l a rp a r t su s e di no f f s h o r e d r i l l i n gp l a t f o r m ，w h i c hc o m b i n e sh e u r i s t i cs e a r c ha n dg e n e t i ca l g o r i t h m s ( g a ) t op a c k t h ep a r t sb yt w op h a s e s t h ei n i t i a lr e s u l to ft h en e s t i n gh a sb e e nf o r m e db yt h eh e u r i s t i c s e a r c ha f t e rh e u r i s t i cr u l e sh a v eb e e nd e f i n e dd e p e n d i n go nt h e c h a r a c t e r i s t i c so ft h e s p e c i a li n d u s t r y t h eu n p e r f e c t e dr e s u l tp r o d u c e di nt h ef n s ts t e pi so p t i m i z e db yt h e g e n e t i ca l g o r i t h m s i nt h eg e n e t i ca l g o r i t h m s ，t h ep o l l e np a r e n ti st h er e s u l tp r o d u c e di n t h ef i r s ts t e p ，a n dt h i sp o l l e np a r e n tg i v e sb i r t ht ot h ei n i t i a lg r o u pb ya b e r r a n c e a ts a m e t i m e ，t h ec h r o m o s o m e sd o n tr e f l e c tt h er e s u l t so fl a y o u t a n dt h e r ei sap r o c e s st o d e c o d et h ec h r o m o s o m ei n t on e s t i n gr e s u l t ，d u r i n gw h i c ht h ec h r o m o s o m e sj u s tl i k e g r o w i n gu p d u r i n gt h ep r o c e s s ，f i r s t l y , t r a n s l a t et h ec h r o m o s o m ew h i c hc o n t a i n i n gt h e i n f o r m a t i o no ft h es o r t si n t oaa r r a yo ft h er e a lp a r t sw a i t i n gt ol a y o u t ；s e c o n d l y , p u t t h o s ep a r t si n t h a ta r r a yi n t ot h eb l o c kb o a r db yt h eh e u r i s t i cs e a r c hb yw h i c ht h e p r e d o m i n a n c eo ft h ec h r o m o s o m ec a nb ee x e r t e da tt h ec o m p l e t e l y t h r o u g ht h a t ，w e d o n to n l yu s et h eg e n e t i ca l g o r i t h m st oa c h i e v et h ef u l l s c a l es e a r c h ，b u ta l s og a i nah i g h e f f e c tb yt h eh e u r i s t i cs e a r c h b a s e do nt h es c i e n t i f i cm e t h o da n dt h ep r i n c i p l eo fm a n m a c h i n ec o n v e r s a t i o n ，t h i s p a p e re x p l o i t sah a n d yn e s t i n gs y s t e m ，w h i c hc a nb ec o m p a t i b l ew i t ha u t o c a d c o m p l e t e l y s u m m a r i z et h ea d v a n t a g ea n dd i s a d v a n t a g eo ft h ea r i t h m e t i ca n ds y s t e m ， f i n a l l yp u tf o r w a r ds u g g e s t i o n st op r o m o t e t h ea r i t h m e t i ca n ds y s t e m k e yw o r d s ：n e s t i n ga r i t h m e t i c ，f l a m ec u t t i n g ，h e u r i s t i cs e a r c h ，g e n e t i ca l g o r i t h m s ( g a ) ， o f f s h o r ed r i l l i n gp l a t f o r m 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得墨鲞盘堂或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：悫乍 签字目期： 弘妒年口6 月口弘日 学位论文版权使用授权书 本学位论文作者完全了解墨凄盘堂 有关保留、使用学位论文的规定。 特授权苤盗盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：丧 导师签名： 签字日期：p 哆年。j 月。佃 签字日期：) 歹年石月乎日 ， 第一章绪论 1 1 课题研究背景及意义 第一章绪论 排料又称套料，通常指在形状和尺寸给定的母材上尽可能多地排放零件。排料 问题一般有维排料，二维排料，三维排料。 排料技术应用范围十分广泛，如机械行业、服装行业、皮革行业、家具行业等。 排料结果是否优化直接影响到原材料的利用率，直接影响到企业的经济效益。 海洋钻井平台是应用于海洋钻探井的海上结构物，需要承载钻具、动力、 通讯、导航等设备，以及安全救生和人员生活设施。海洋钻井平台是以焊接为 主的大型结构，其中需要大量的二维不规则加强筋板，这就涉及n - 维不规则零 件的排料问题。企业普遍采用的做法是由人工放样、手动编码生成数控程序。这样 不仅费时费工，而且排样的结果很容易受到技术工人经验和情绪的影响。另一方面， 对于钢结构企业，钢材要占公司总成本的6 0 以上，而气体燃料也要占切割总成本 的6 0 以上，钢结构行业已经进入微利时代，2 0 0 8 年以来，钢材价格不断攀升，市 场竞争日益激烈，降低生产成本的要求愈加迫切，而降低成本的途径，最行之有效 的办法就是提高材料的利用率、提高切割效率【1 1 。 中国海洋石油工程股份有限公司对传统人工放样的生产方式进行改革，引进了 f a s tc a m 软件公司的f a s tc a m 系列切割软件，使用过程中发现软件的功能难以满 足生产需要，主要问题是，排料结果不够优化，切割轨迹路径不够优化，需要人工 调整，且调整工作非常繁琐，为此提出开发更加适应本企业生产的排料系统。 综上所述，具有行业针对性的解决二维不规则零件的排料问题具有重要的现实 意义。 1 2 课题国内外研究情况 1 2 1 国外研究状况 对于矩形零件排料问题1 2 ，自六十年代开始，人们就提出了大量的算法。h a i m s 第一章绪论 和f r e e m a n 给出的规划方法待排零件的数量不受限制，在每一步都将矩形部件或者 矩形组件放在板料的一角上【3 1 。c h i r s t o f i d e s 和w h i t l o c k ( 1 9 7 7 ) 提出了用动态规划的 树状搜索方法解决矩形剪切排料问题【4 1 。但是，由于该法耗费时间过长，不适合解 决实际应用过程中的大规模排料问题。 对于任意形状的排料问题，目前所采用的解决方法主要有一下几种： ( 1 ) 近似矩形法 该方法是由矩形零件排料优化问题引申出的，主导思想是将不规则排料问题转 化为矩形零件的排料问题，然后采用动态规划法对矩形进行排放【5 】。1 9 7 7 年 a a l b a n o 发表论文，论文提出“两步法”和“人机交互法，【引。首先通过启发式方 法和动态规划方法的组合，由计算机产生一个初始排料方案，然后再经过人工交互 对排料图进一步调整。1 9 9 1 年，c h e o k 和n e e 提出“三步自动排料方案，【7 1 。第一 步做形状处理，简化零件轮廓；第二步根据经验匹配分类零件，产生好的或者紧密 排列的矩形单元；第三步采用矩形排列方法排料。该类方法在一般情况下效率较高， 但是当零件种类繁多，且零件轮廓不规则程度较大时，排料结果往往不够优化。 ( 2 ) 启发式推理方法，该方法模仿人工排料，定义大量的启发规则，在定义 的规则下进行推理，由计算机决定排料方案。1 9 8 3 年，d a g l i 和t o t o g l u 通过零件 的面积、轮廓周长、复杂性等等决定零件排放的优先权f 8 】。从具有最高优先权的零 件开始，不加选择地判断边界匹配情况，选择具有最小包容矩形的位置放置零件。 按优先权顺序不断重复以上过程，直到所有的零件均己定位或将母材排满。这种方 法在待排零件不多的情况下还可以得到比较满意的解，但是随着零件数量的增加， 这种几乎不加选择的判断必然造成计算时间过长，最后因为计算机计算能力的局限 使问题无法得到解决。1 9 8 9 年，c h u n g 及合作者运用启发式搜索方法匹配零件凹凸 特征的方法，解决了不规则轮廓的排料问题【9 】。当第一个零件定位之后，它的下一 个最佳毗邻零件被测定。但是文章只考虑了四个基本位置( 9 0 度，1 8 0 度，2 7 0 度， 3 6 0 度) ，这样就使算法仅适用于规则度比较高的零件，对于形状奇异的零件排料问 题就会造成大量的材料浪费。1 9 9 4 年，p r a s a d 提出将一个零件先固定，将另一个零 件沿着它的多边形的轮廓移动。通过对正轮廓的最长边界，决定零件的相对位置， 在沿多边形移动的每一步过程中均构造一个最小包络矩形，然后选择其中最好的最 小包络矩形【1 0 】。这种算法同d a g l i 和t o t o g l u 提出的算法有同样的缺点，当零件数 量过大时，计算时间过长。 ( 3 ) 智能优化法，该方法首先定义一个目标函数，采用诸如人工神经网络、 遗传算法、模拟退火法等智能优化方法，在整个空间中进行搜索。k a t h r y n a 第一章绪论 d o w s l a n d ，s u b o d hr a i d 使用b l 算法实现了快速有效的不规则零件的嵌套布局【1 。 h o p f i e l d 利用h o p f i e l d 神经网络成功地求解了旅行商问题以后，人们对人工神经网 络方法在组合优化领域应用的研究越来越深入。m s r i r a ms m k a n g ( 1 9 9 0 ) 利用改进 的h o p f i e i d 人工神经网络解决y - 维模块的排料问趔1 2 l 。通过对神经网络改造，将 原来的二维排料问题分解成两个一维问题。同时采用了最d , 丰l l e 料布局的分层方法， 使得网络的大小与模块的数目呈线性关系。这种智能算法比单纯的启发式算法具有 很大的进步。 遗传算法是一种著名的全局优化算法，是采用概率搜索的组合优化技术1 1 引。 h i s m a i l 和k k b h o n ( 1 9 9 2 ) 用遗传算法完成了二维冲裁件排料的自动成组匹配 【l4 1 。但是一般遗传算法解决排料问题往往采用对零件进行编号，再把这些代号进行 排序得到染色体，还有的在每一个代号后面加一个旋转角度，用来控制零件需要旋 转的角度。染色体往往直接对应着排料结果，染色体中零件的顺序就是排料结果中 零件的排放关系。这样编码使搜索时间过长，又因为零件顺序与零件旋转角度有不 一样的特点，而要使他们进行统一的遗传操作，必然大大降低了算法的优化能力。 k a d o w n s l a n d ( 1 9 9 3 ) 用模拟退火算法解决了许多组合优化问题，证明模拟退 火算法是一种有效的全局搜索方法纠。 以上几篇文献单纯使用人工神经网络等智能算法，理论上可以得到最优解，但 是实际上由于计算机计算能力的限制，往往在待排零件数目过多时，算法失效。 从实际的应用看，上个世纪七八十年代排料算法在国外就已经进入实用阶段。 现在市场上比较实用的国外软件有韩国的c a d w i n ；美国s i g m a t e k 公司的 s i g m a n e s t ；m t cs o f t w a r e 开发的m t cp r o n e s t 软件；以及国内市场普遍使用的 澳大利亚f a s t c a m 公司开发的f a s t c a m 数控切割套料软件。国外的软件技术相对 成熟，在一定程度上已经能够达到很高的板材利用率，但是国外的排料系统价格昂 贵，有的需要几十万一套；另一个缺点就是通用性较强，针对特定行业的零件排料 板材面积利用率不够理想，并且有时运行速度比较慢。 1 2 2 国内研究状况 国内对优化排料技术的研究起步晚，但也取得了一定的成果。根据工程的实际 背景，很多人采用启发式搜索算法，根据人工排样的经验定义大量的规则，得到了 较大的认同，但是难度较大。华北电力大学的段巍等人提出基于启发式二维搜索算 法，其基本思想是：对待排零件进行预处理，确定合理的零件选择规则和定位规则， 对预处理后的零件在板材上直接排放1 6 】。近年来，国内掀起了智能算法研究的热潮， 第一章绪论 2 0 0 6 年刘瑞杰等人发表了题为( a c s 算法在矩形件优化排料中的应用的论文，该 文提出了用蚁群算法求解矩形件优化排料问题。把矩形件优化排料问题转化成寻找 一棵面积比率最大的下二叉树，用蚁群算法实现树搜索，把一定数量的蚂蚁分布在 与或树的根结点，蚂蚁间通过使用信息素互相交流，最后得到排料问题的优化解【l7 1 。 华中科技大学的刘心雄等提出了一种基于人工智能的自动排料算法【1 8 】。该算法运用 问题的规约理论，将自动排料的过程简化为基本块的生成与搜索，运用规则判断与 启发式搜索的方法生成基本块，并把该算法应用于服装衣片的裁剪，加快了运算速 度。东北大学的滕健在其硕士论文计算机辅助二维排料方法的研究中提出了一 种新颖而且实用的算法，运用人工神经网络的自组织特征映射算法( s o m ) 以及模 拟退火算法( s a ) ，分两个阶段解决排料问题【l9 1 。上海交通大学的宋嘉仁提出一 种基于混合遗传算法的零件图形滑移算法【2 0 1 。 在实际应用方面，国内也开发了自己的排料系统，发展也很迅速。目前市场上 出现了大量的排料软件，如北京天良科技发展有限公司开发的天良板材套料优化软 件，北京文泰铭雕软件有限公司的v 8 套料软件等。国内的软件相对便宜，但是板 材的利用率不高，而且耗费计算机资源，目前尚没有得到市场普遍认可的排料软件。 1 3 本文的主要内容 本论文在对前人关于不规n - 维排料问题研究成果总结借鉴的基础上，提出了 以海洋钻井平台工程为实际工程背景，对该工程中使用的二维不规则零件的计算机 自动排料技术进行研究。研究内容包括以下几个方面： 1 读取零件图，本系统是在a u t o c a d 平台上进行的二次开发，最直接的问题就 是做到系统与a u t o c a d 数据兼容。 2 数据管理，程序的编制必须有一个好的数据管理方法，根据工程的特点，建 立适合的工程数据库。 3 用启发式搜索填充空白区域的办法产生初始排料方案，并利用改进的遗传算 法，对初始排料方案进行优化。 4 排料过程中，处理零件之间的间隙，针对海洋钻井平台二维不规则零件的切 割工艺需要，一般零件与零件之间设定间隙，要求是6 m m ，但是对于相邻零件存在 相等直线段的零件作为两个零件的公共边，可以去除间隙。 第二章排料系统的总体设计 2 1 概述 第二章排料系统的总体设计 本章对海洋钻井平台上使用的二维不规则零件的排料问题和切割问题要点进 行分析。根据问题的要点和企业的要求选择a u t o c a d 作为开发平台，选择v b a 作 为开发语言，设计了自动排料及数控编程系统框架。 系统的总体功能如图2 1 所示。系统主要包括两大功能：自动优化排料和切割 轨迹的自动优化。为了便于系统设计和管理，根据两大功能把系统划分为五个模块： 图形加载、自动排料、轨迹优化、轨迹模拟、数控自动编程。图中自动优化排料部 分将在后续的章节中深入展开研究，图中虚线内部分为切割轨迹的自动优化部分， 在本文不做深入研究。 自动优一比排料l l 轨迹自动优化 上 上上 上 1 l l 零件图形加载卜叫自动排料h| 轨迹优化h 轨迹模拟制数控自动编程j i 排料图加载h 。一一 图2 1 系统功能模块 系统工作流程如图2 - 2 所示。图中，系统加载零件图以后，由图形加载模块完 成“信息提取”和“添加扩展数据”，然后，数据流入自动排料模块。自动排料图 和手动排料图都可以读入轨迹优化模块，进行切割轨迹的自动优化。最后切割轨迹 的优化方案传入轨迹模拟模块，在确认无误后，由数控编程模块转化为数控程序文 件输出。 第二章排料系统的总体设计 圃 工 2 2 排料问题要点分析 图2 - 2 系统实现总体功能的流程图 本文是针对海洋钻井平台工程中使用的二维不规则零件进行的优化排料技术 研究并开发相应的软件系统。海洋钻井平台工程中使用的二维不规则零件具有不同 于其它工程的特点，为搭建一个合理的自动排料及数控编程系统并能有效的解决实 际问题，有必要把海洋钻井平台二维不规则零件的排料问题要点作如下分析。 1 排料约束条件：在一次排料中，板材的长度和宽度限定，不规则二维零件的 数量和规格限定。 2 海洋钻井平台所用的零件形状和规格大小一般没有规律性，重复率低，所以 没有必要对零件和输出的排料图数据进行复杂的数据管理，工程没有大量的数据管 理，不需要建立专门的数据库。 第二章排料系统的总体设计 3 海洋钻井平台的体积很庞大，零件最小包络圆的直径一般都会在l o o m m 以 上；工程本身的精度要求不是很高，所以对零件尺寸的精度要求不高。 4 原材料一般为厚度大于1 0 m m 的钢板，下料一般采用火焰切割，火焰切割要 求相邻零件之间留有间隙，根据生产厂家要求设置间隙为6 m m 。 5 根据工程需要，在同一批次的排料中，会有大量统一规格的零件，这样就引 出公共边。公共边的利用不仅可以提高板材的利用率，而且也可以大大节省切割燃 料，提高切割效率。 6 海洋钻井平台工程中的二维零件有大量含有镂空的零件，所以有必要充分利 用零件的镂空区域。 2 3 开发环境及开发语言 a u t o c a d 是a u t od e s k 公司推出的精确绘图软件，广泛应用于机械、电子、纺 织、汽车、建筑设计等众多领域，受到世界各地用户的青睐，也是国内海洋钻井平 台工程公司应用最为广泛的软件之一 2 h 。为了充分利用企业现有图样资源，与企业 现行技术有效接轨，本文选择a u t o c a d 作为开发平台。传统计算机辅助制造系统 采用高级语言进行设计计算，与a u t o c a d 之间利用标准结构的数据文件( 如术d x f ) 进行数据交换，其编程过程复杂而且效率低下。使软件与a u t o c a d 自由兼容使用， 方便用户，而且可以利用a u t o c a d 现有的图形处理技术，为编程带来的极大地便 利。 a u t od e s k 公司相继推出了三代二次开发工具。第一代开发工具a u t o l i s e 第二 代开发工具a d s ( a u t o c a dd e v e l o p m e n ts y s t e m ) ，第三代开发工具包括v i s u a ll i s p , a r x ( a u t oc a dr u n t i m ee x t e n s i o n ) ，以及基于a c t i v e xa u t o m a t i o n 技术的 v b a ( m i c r o s o f to f f i c e 中的v i s u a lb a s i cf o ra p p l i c a t i o n ) 、v i s u a lj a v a 、v b n e t 等2 2 1 。 本文采用的开发工具是v b a 。v b a 是完全面向对象的程序语言，集成了v b 语言 简单、功能强大、易于掌握的特点。v b a 和a u t o c a d 中强大的a c t i v e x 自动化对 象模型的结合，代表了一种新型的定制a u t oc a d 的模式构架。和l i s p 结合起来， v b a 首先是一个开发公司内部使用的程序的利器。在所有的开发工具中，这是一种 开发速度最快的工具，特别是在开发需要图形界面( 对话框) 的程序时【2 3 1 。 第二章排料系统的总体设计 2 4 排料系统功能模块设计 2 4 1 图形加载模块 为了充分利用企业现有的图样资源，本文在系统中设置了图形加载模块，主要 功能是系统与a u t o c a d 的数据传递，把图形处理成为自动排料模块和轨迹优化模 块可以辨识的数据信息。图形加载模块有两部分，一部分是排料部分零件图加载， 另一部分是轨迹规划部分排料图加载。排料部分零件图形加载，在软件界面下浏览 计算机存储的幸d w g 文件，选择需要的文件读入内存，图形加载模块获取零件图信 息，组织成排料模块可以识别的数据形式。轨迹规划部分排料图加载，直接应用 a u t o c a d 的打开命令打开需要规划轨迹的排料图，经过该模块运算提取出轨迹自动 优化部分需要的数据信息。 2 4 2 自动排料模块 自动排料模块的功能是把加载的零件按照用户指定的个数自动排放，输出排料 方案，并达到较高的板材利用率。程序允许用户对方案中不满意的地方进行手动调 整。模块还提供了交互式的排料信息输入界面，用户可以根据生产需要输入待排零 件的个数，零件间隙和移动步长。 2 5 本章小结 本章分析了海洋钻井平台二维不规则零件排料问题的特点。并根据这些特点和 用户的要求选择a u t o c a d 作为系统开发的平台，v b a 作为开发语言。根据系统要 实现的功能进行模块的划分，并分析了各个模块之间的联系。 第三章基于a u t o c a d 图形处理的排料算法 3 1 概述 第三章基于图形处理的排料算法 要实现计算机自动排料，首先要使计算机获得零件信息，再实现计算机上对零 件图形的操作，模拟排料过程。本章主要解决图形获取和图形操作的基本问题。 随着排料零件个数的增加，海量的零件数据信息使得人们对数据的分析和处理 变得越来越难，从而影响了系统开发的速度和准确性。a u t o c a d 在图形处理方面已 经相当成熟，本文直接借用a u t o c a d 的图形处理功能，或者对其加以改造，实现 图形信息的获取和操作。 3 2 零件图形数据处理 3 2 1 零件的读取 目前的海洋钻井平台的标准化程度很低，零件的重用率低，规则度低，因此本 文没有采用标准零件库的方式组织管理零件，而是直接使用a u t o c a d 的绘图功能， 绘制零件图并存档。如图3 1 所示，排料时把这些存储的零件图形调入排料系统。 调入的零件图形是直线、圆、圆弧和二维样条曲线等信息组成，这些信息对于排料 是没有直接意义的，必须把它们组织成便于图形操作的数据。为了使零件实体的数 据得到有效的管理，降低运算难度，提高系统开发效率，本文借用a u t o c a d 提供 的面域来组织零件。面域是a u t o c a d 提供的对象类型，在v b a 中对应a c a d r e g i o n 类，是用户由闭合形状创建的二维闭合区域。零件图形的读取是通过直接加载球d w g 文件实现的。 同时，系统提供了交互式界面，供用户输入待排零件的个数，用户输入的零件 个数信息和零件号( 零件存储时所用的名称) 一并存储到内存中。当用户单击“取 消”输入时，系统退出加载。 第三章基于a u t o c a d 图形处理的排料算法 打开零件文件 复制零件图形到 当前排料文件 转化面域l = 工二 输入待排零件 个数 二 存储零件个 数，零件号 关闭零件文件 3 2 2 零件的数据管理 在排料过程中，不仅需要知道零件的图形信息，而且还需要零件的属性信息， 比如零件号，该零件待排的个数，零件是否已经排好等。这些信息在加载零件的过 程中已经获取，存储在内存中。一般的排料系统都是采用数据库的方式对这些数据 加以管理，但是考虑到信息管理的完整性【2 4 1 ，本文采用a u t o c a d 二次开发工具提 供的扩展数据表( x d a t a ) 对图形属性信息进行统一管理。属性信息定义如下所示： x d a t a ( 0 ) _ l a y ”工程名 x d a t a ( 1 ) = a d d o b j t y p e 零件号 x d a t a ( 2 ) _ s t r f i l e n a m e 零件的路径 x d a t a ( 3 ) = n零件的个数 x d a t a ( 4 ) = 0 0 代表待排，1 代表已经排好 x d a t a ( 5 ) = ”奉幸 零件的排放类型 使用o b j e c t s e t x d a t ax d a t a t y p e ，x d a t a 方法把上面定义的信息附着在面域实体 蹴 多南一 菩一 第三章基于a u t o c a d 图形处理的排料算法 上，这样整个零件的图形信息和属性信息都统一在这个面域实体中，需要使用这些 信息的时候，再使用o b j e c t g e t x d a t aa p p n a m e ，x d a t a t y p e ，x d a t a v a l u e 方法得到。 3 3 排料关键算法 要实现计算机自动排料，适当的算法是必不可少的，算法是否科学，直接影响 到排料结果和运算效率。为此本节开发了零件移动，碰撞检测，求取零件间隙及公 共边的算法。 3 3 1 零件移动算法 排料工作的关键在于各待排零件最终是否能排放到板材上恰当的位置，本文采 用移动算法进行零件排放，零件图形通过移动到达板材上一个合适的位置。移动算 法直接影响到自动排料的精度和速度。但是精度和速度是相互矛盾的两个方面，以 往的算法通常在满足精度要求的时候，要耗费大量运算时间，或者是提高了运算速 度，又不能满足精度要求。为此本文提出了大步长和微移相结合的办法。大步长通 过用户输入的办法确定。用户根据待排零件的大小确定大步长，首先使零件按照大 步长进行移动，每移动一个步长都进行一次检测，如果该零件与其他零件相交，则 采用微移的办法行进后退，微移的距离是系统提前确定的，每微移一次都进行一次 检测，如果该零件与所有的零件都不想交，则停止后退微移，具体流程如图3 2 所 示。大步长移动使移动效率大大提高，微移保证了排料的精度。 第三章基于a u t o c a d 图形处理的排料算法 甲 图3 - 2 零件移动算法流程图 3 3 2 零件碰撞算法 排料的基本要求之一是零件不发生重叠。为了防止重叠，碰撞检测不失为一种 有效方法【2 5 1 。碰撞检测是本文开发的自动排料算法之一，它关系到自动排料的精度 和计算速度【2 们。 本文在处理碰撞的时候，充分利用了a u t o c a d 中的求交方法r e t v a l = o b j e c t i n t e r s e c t w i t h ( i n t e r s e c t o b j e c t ，e x t e n d o p t i o n ) ，r e t v a l 是一个存放交点的数组， 如果两个面域完全不相交则r e t v a l 为空的。这种算法简单易行，不易产生误判，编 程的难度低，运算效率高。用u b o u n d ( r e t v a l ) 返回数组的大小，如果值为1 ，则两 个被测零件之间没有相交，否则相交。零件碰撞检测算法流程如图3 - 3 所示。 第三章基于a u t o c a d 图形处理的排料算法 图3 3 零件碰撞检测算法流程 3 3 3 零件间隙和公共边求取算法 在火焰切割生产中，为了满足零件的尺寸要求，排料时往往在需要切割的相邻 零件之间留有一定的间隙。这个间隙一般是割缝宽度，或者根据防止变形的工艺需 要，规定一个大于割缝宽度的距离，本文采用“等距放大法 产生零件之间的间隙， 即用于排料运算的不是零件的原始图形，而是边界扩大半个间隙后的等距放大图， 如图3 - 4 所示为“等距放大法”的示意图，图中d 为排料所需的零件之间的间隙。具 体操作流程如图3 - 5 ，真正调用排料函数之前先进行等距处理，在排料运算结束后， 再把图形还原，其中n 是待排零件的个数。 第三章基于a u t o c a d 图形处理的排料算法 i 图3 4 等距放大法产生间隙 1 4 第三章基于a u t o c a d 图形处理的排料算法 团 图3 5 零件间隙的处理 相邻零件如果存在长度相等的直线，通过移动可以使这两条直线重合，该重合 边即是公共边。对于每一个待排零件，首先提取面域的边界，分析其中含有的线段， 当这个线段符合以下条件时，则该线段为疑似公共边。疑似公共边的检测示意图见 图3 - 6 。 l 、线段大于一定的长度。长度根据用户要求设定。 第三章基于a u t o c a d 图形处理的排料算法 2 、线段分布在面域的左侧。把零件分为左侧和右侧两部分的目的是避免重复 判断，提高判断效率。判断方法为：离开直线a b 中点微小距离向左做一 条足够小的短划，若短划与面域没有交点，则符合条件。 检测短划 a b 图3 - 6 疑似公共边的检测 c 利用检测线段检测疑似公共边是否为公共边，在零件要检测的边上取中点作一 条检测线段，直线段的长度略长于间隙长度，若与检测直线相交的面域的边界，也 是段直线，并且直线段的长度与疑似公共边长度相等，则疑似公共边与这条直线 被定义为一对公共边。并把公共边的信息，起点和终点作为扩展数据x d a t a 附着在 面域实体中。具体操作如图3 7 所示。 图3 7 公共边检测示意 3 3 4 零件镂空区求取算法 海洋钻井平台工程中存在大量的镂空零件，如果对这些镂空不加以处理和填 充，将会造成大量的材料浪费，如果完全采用自动排料后人工填充镂空的方式，则 效率低下，而且由于调整人员的经验不足也可能造成材料利用率难以提高。为此本 文提出了排料过程中自动填充零件镂空区域的算法。 根据对海洋钻井平台零件的分析，本文定义了两种镂空区，一种情况是在零件 第三章基于a u t o c a d 图形处理的排料算法 中封闭有一个空白区域，如图3 8 所示。其中p a r t l 和p a r t 2 的内部都有封闭的空白 区域。在排放p a r t l 后，p a r t l 内部的空白区域就产生了一个镂空。在这个镂空中填 充p a a 2 ， 图3 - 8 镂空区域 p a r t l v p a r t 2 p a r t 3 再次产生镂空，在该镂空中可以继续填充p 矾3 。 另一种情况是由非矩形零件在排料过程中自然产生，如图3 8 所示。其中p a r t1 是内凹零件，和p a r t 2 的外凸部分结合，就出现了中间的镂空部分。 镂空区域的求取主要应用面域实体的布尔运算b o o l e a na c s u b t r a c t i o n 实现。对 于第一种情况，是直接求取镂空的情况，板材与面域零件进行差集运算，得到的比 板材面积小的多的小差集面域就是镂空部分。 对于第二种情况，有两种方法求取，第一种方法是，每排一个有凹陷的零件， 就运算一次，采用填补零件凹陷求取镂空的方法，过程如图3 8 中a 所示，p a n l 与 使用g e t b o u n d i n g b o x 方法得到的p a a l 的最大矩形包络面域求差集，得到四个小的 差集面域。由于只有差集面域可以放下某个零件时，对排料才有意义，所以差集面 域必须符合以下条件时才是镂空。 条件1 表示镂空的面积必须大于某个零件的面积； 条件2 表示镂空的长度必须大于所有零件的最小长度，同时，镂空的宽度必须 大于所有零件的最小宽度。 条件1 ：b l a n k h o l l o w a r e a mi n ( p a r t ；a r e a ) 条件2 - b l a n k h o l l o w l m i n ( p a r t i l ) a n db l a n k h o l l o w w m i n ( p a r t i w ) 其中，1 ，一一长度，w 一宽度，a r e a 面积 b l a n k h o l l o w 是表达镂空的数据结构，b l a n k h o l l o w a r e a 是表达镂 空区域面积的数据结构，p a r t ；代表第i 个零件。 第三章基于a u t o c a d 图形处理的排料算法 这中方法求取的结果会使镂空产生分割细化，错过一些可能填充某个零件的镂空区 域，而且，计算机对填充的计算过于复杂，大大降低了运算速度，所以对这种算法 加以改进得到了第二种算法。 第二种方法是，一种零件排到不能再排之后，再进行方法一中的运算，这样做 的好处就是使相邻两个零件的空白区域得到合并，产生更有利于填充的空白区域。 这种算法的优势在图3 8 可以得到很好的说明。如果按照第一种求法，求得的镂空 面积如图3 - 9 中a 中空白区域所示，第二种求法得到的镂空如图b 中的空白区域，图c 为最终的排料结果。 p a r t ： 矮，砸i 域 p a n l - - 一 - - c 、按第一种方法计算得到的排料方案 图3 - 9 镂空区域的求解与利用 第三章基于a u t o c a d 图形处理的排料算法 3 4 本章小结 本章根据工程特点和图形操作基本原理，提出了适合本工程的数据管理方案， 对排料中关键问题进行了研究，提出了以a u t o c a d 图形操作为基础的移动和碰撞 操作算法，提出了求解公共边和零件镂空的算法，提出了解决相邻零件间隙问题的 方法。 第四章初始排料方案的形成 4 1 概述 第四章初始排料方案的形成 排料问题难于解决的一个重要原因是随着待排零件数目的增长，获得最优解所 需要的计算时间将成指数增长，即计算时间随k n 中的n 指数( 其中k 为大于l 的 常数，n 为零件数) 增加而急剧加长。因此排料问题属于n p 难度问趔z ”。另外在 解决实际问题时会遇到许多约束条件，将这些约束条件用数学方法全部组合在一起 非常困难，有时甚至不可能。由于这些原因，许多排料问题的研究者并不是直接利 用最优化技术，而是通过启发式搜素的方法，借鉴人工排料的经验，并采用近似最 优技术解决排料问题 2 8 1 。本文引入启发式算法，并深入研究了沉积现象与人工排料 结果的相似之处，定义启发式规则，采用启发式搜索填充空白区域的办法进行初始 排料。 4 2 启发式搜索与沉积现象 4 2 1 启发式算法 启发式搜索要用到问题自身的某些特性信息，以指导搜索朝着最优解的方向前 进。由于这种搜索针对性较强，因而原则上只搜索问题的部分状态空间，效率较高 1 2 9 1 。 在搜索空间进行搜索时，为了更有效地搜索一个给定的空间，可设计一系列的 启发规则来决定每一次扩展时，哪个节点最有希望到达目标节点，然后搜索就可能 沿着某个被认为最有希望的节点向外扩展。如果能够给出合适的启发规则，将会大 大减少搜索工作量【3 0 l 。 4 2 2 沉积现象 水流中所夹带的岩石、沙砾、泥土等在河床和海湾等低洼地带沉淀、淤积的现 第四章初始排料方案的形成 象称为沉积现象。沉积过程遵循最小位能原理，即所有沉积物的势能总和最小，并 且最终的沉积物可以达到一个最稳定的状态。 沉积物在搬运和沉积过程中会