（控制理论与控制工程专业论文）有瑕疵材料二维下料问题的研究和应用(1).pdf

原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：益么匿 日期： 、 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：缢 导师签名：日期： 山东大学硕士学位论文 中文摘要 下料问题，就是给定一个布局空间和若干待下物体，将待下物体合理地摆放 在布局生间中，满足必要的约束条件，并使材料利用率达到最高。自动下料问题 由来已久，对于自动最优下料问题在应用上可以提高生产效率，节约成本，理论 上它又是n p 完全问题，具有巨大的挑战性，可以认为它是人类到目前为止遇到的 最困难问题的典型代表之一，具有重要的研究价值。不规则图形的自动下料问题， 一直受到广泛的重视和研究，而对原材料的约束条件更是对此问题提出了挑战， 研究方法涉及了组合优化、人工智能、计算几何学等各种理论。 由于自动下料问题属于n p 完全问题，随着布局物体数量的增加，解空间里指 数倍数的扩大，出现组合爆炸现象，而动态规划、分支定界等基于穷举思想的算 法只能解决数量较少舻图形组合形式因而无法解决此类问题，采用启发式搜索的 方法，神经网络，遗传算法等求解自动布局问题得到了广泛的认同。 t ，t 本文所要解决的问题在此基础上更对原材料进行了约束，即带有瑕疵的原材 、 料的自动下料问题。针对此类下料问题，在原有算法的基础上提出了一种改进的 基于启发式搜索策略的自动下料算法，充分考虑人工下料时的经验信息，提出了 对原材料的瑕疵和待下料图形的初始化方法以及基于分组的定序规则算法，不但 提高了材料利用率，而且使自动下料图更易于进行交互式的修改；移动算法采用 了启发式搜索策略，可以很快确定待下料图形和瑕疵的位置；对于小块图形，进 行插空下，提高了材料利用率；靠接算法通过待移动区域确定可能发生碰撞的实 体，先大步长移动，然后微调，从而减少大量的盲目检测，提高了下料的精度。 本文主要采用的是改进的启发式搜索算法和碰撞检测算法对图形进行优化 排样，同时结合计算机图形处理软件a u t o c a d 2 0 0 0 与其二次开发软件o b j e c t a r x 进行编程。主要应用了矩形包络算法和旋转对排法来处理不规则图形和瑕疵处 理，然后调用初始化程序和定序规则算法对图形进行处理，最后采用改进的启发 式搜索算法和碰撞检测算法对处理后的图形进行优化排样。 实验结果证明，改进算法对瑕疵的处理具有可行性，与原算法相比，在面积 优先的前提下，对方正度趋近于l 或者经过变换后方正度趋近于1 的下料图形能够 取得较好的效果；并且在经过改进与没有经过改进的算法相比，大大减少了累积 误差，提高了材料利用率。 关键词：下料问题、启发式搜索算法、碰撞检测、瑕疵、方正度 a b s t r a c t p a c k i n gp r o b l e m sa r i s ef r o mav a r i e t yo fs i t u a t i o n si n c l u d i n gp a l l e tl o a d i n g , t e x t i l e c u t t i n g ，c o n t a i n e rs t u f f i n ga n dp l a c e m e n tp r o b l e m s s u c hp r o b l e m sa r eo p t i m i z a t i o n p r o b l e m s t h a ta r ec o n c e r n e d 、】v i t l l f i n d i n g ag o o d a r r a n g e m e n to fm u l t i p l e d i f f e r e n t - s i z e do b j e c t si nal a r g ec o n t a i n i n gr e g i o nw i t h o u to v e r l a p i no r d e rt os o l v e t h es u b j e c ta b o u tt i m ea n de n e r g y ，w h i c ha p p e a r si na l t e r n a t em a r k e r , t h ec l a s s i c p a c k i n ga l g o r i t h mi sb r o u g h tf o r w a r di nt h et h e s i s t h a ti st h ec l a s s i c a la l g o r i t h mi n t h ea r t i f i c i a li n t e l l i g e n c e c o n v e n t i o n a lg e n e t i ca l g o r i t h m s ( g a s ) a l o n ep e r f o r mn o b e t t e rt h a nt r a d i t i o n a la r t i f i c i a li n t e l l i g e n c ea p p r o a c h e ss u c ha sh e u r i s t i cs e a r c ho r o p e r a t i o n sr e s e a r c hm e t h o d ss u c ha sf i r s tf i t a tt h es a m et i m e ，s o l u t i o n st om a n y p a c k i n gp r o b l e m sd o e sn o tm a t c ht ob ea d j u s tb yh a n d h e u r i s t i cs e a r c hh a sb e e n p r o v e dt ob ea l le f f e c t i v ew a y t or e s o l v ep a c k i n gp r o b l e m s i nt h i sp a p e r , w ep r e s e n ta l lo p t i m i z e dh e u r i s t i cs e a r c hb a s e dp a c k i n ga l g o r i t h m 、。 w i t hm i n o rf a u l ti n t h em a t e r i a l s w ea l s op r e s e n tat w od i m e n s i o n a lc o l l i s i o n d e t e c t i o na l g o r i t h m ，t h ep r o b a b l ec o l l i s i o no b j e c t sa r eo b t a i n e da c c o r d i n gt ot h e r e g i o nw h e r et h em o b i l eo b j e aw i l lg ob yt oa v o i db l i n dd e t e c t i o n ；p u tf o r w a r dt ot h e m i n o rf a u l t so ft h eo r i g i n a lm a t e r i a l 、i t i lt r e a td e s c e n da n t i c i p a t es k e t c ho ft h e b e g i n n i n gs t a r tt ot u r nam e t h o d m o t i o ni sd o n ef i r s ti nl a r g es t e pt h e ni ns m a l ls t e p t o i m p r o v el a y o u te f f i c i e n c y m o r eo v e r , t h es o l u t i o n s t ot h i sh e u r i s t i cb a s e d a l g o r i t h mc a n b ee a s i l ya d j u s t e dt oi m p r o v et h eu t i l i z a t i o n t h ep a p e r sm a i n l ya d o p ti m p r o v e dh e u r i s t i cs e a r c ha r i t h m e t i ca n dc o l l i s i o n d e t e c t i o na r i t h m e t i ct oo p t i m i z ea n da r r a h g et h ef i g u r e s i nt h em e a n t i m e ，t h et e x t c o m b i n e d c o m p u t e rf i g u r e sp r o c e s s i n g s o f t w a r ea u t o c a d 2 0 0 0a n di t st w o d e v e l o p m e n ts o f t w a r eo b j e c t a r xt op r o g r a m i nt h et e x t , t h er e c t a n g l ee n c i r c l e d a r i t h m e t i ca n dr e v o l v i n gr e v e r s ea r i t h m e t i ca r ea d o p t c ( it oh a n d l et h ei r r e g u l a rf i g u r e s a n dn l i n o rf a u l t sp r o c e s s i n g ，t h e nt r a n s f e rt h ei n i t i a l i z a t i o np r o g r a m m e ra n dr e g u l a t i n g o r d e rp r o g r a m m e rt oh a n d l et h ef i g u r e s , a tl a s ta d o p ti m p r o v e dh e u r i s t i cs e a r c h a r i t h m e t i ca n dc o l l i s i o nd e t e c t i o na r i t h m e t i ct oo p t i m i z ea n da r r a n g et h ef i g u r e s t h er e s u l to ft e s tc e r t i f i c a t e ：t h ei m p r o v e da r i t h m e t i ci ss u c c e s s f u lt oh a n d l et h e 3 m i n o l d e f a u l t c o m p a r i n gt o t h ep r i m a r ya r i t h m e t i c ，g i v e nt h a ta r e ah a sp r i o r i t y ， s a t i s f i e dr e s u l tc a nb eo b t a i n e df o rt h ef i g u r e sa f t e rb e i n gt r a n s f o r m e do ro fw h i c h s q u a r ed e g r e et e n d st ob e1 a n dt h ei m p r o v e da r i t h m e t i cc a nr e d u c ea c c u m u l a t i o n e r r o rc o n s u m e d l ya n dr a i l sm a t e r i a lu t i l i z a t i o ng r e a t l y k e y w o r d s ：p a c k i n g p r o b l e mh e u r i s t i cs e a r c hc o l l i s i o nd e t e c t i o n m i n o rf a u l t s s q u a r ed e g r e e 4 第一章绪论 1 1 引言 下料问题，又称为布局问题( p a c k i n gp r o b l e m ) ，是给定一个布局空间和若 干待下物体，将待下物体合理地摆放在布局空间中，满足必要的约束条件，并使 布局利用率达到最高。下料问题是随着计算机技术的产生而出现的，大量出现在 机械制造、皮革服装加工、汽车、造船、玻璃、交通运输、航天航空、大规模集 成电路板的设计等领域。排样布局的优劣，直接与材料成本及经济效益有关，目 前存在的主要问题是材料利用率低，造成了巨大的浪费。对于规模比较大的生产 厂家来说，即使其材料利用率有很小的提高，也将会带来巨大的经济利益，同时 由于材料本身带有瑕疵而使整个材料报废的情况也不少见，所以对有瑕疵材料不 规则图形排样算法的研究具有十分重要的意义 本文主要采用启发式搜索方法解决不规则实体的自动下料问题，同时更多考 虑人工下料的经验信息，目的是不但要提高材料利用率，还要使下料图更容易进t 、 行手工修正，满足实际生产对利用率的要求。 1 2 背景与意义 对于自动最优下料问题在应用上可以提高生产效率，节约成本，理论上它又 是非确定多项( n o n d e t e r m i n i s t i cp o l y n o m i a l ，简记n p ) 完全问题，具有巨大的 挑战性，可以认为它是人类到目前为止遇到的最困难问题的典型代表之一，具有 重要的研究价值。对于此类问题的研究一直受到广泛的重视，研究方法涉及了组 合优化、人工智能、计算几何学等各种理论。 1 2 1 研究背景 在各种工业制造产品的生产过程中，为加工过程截取与产品零件尺寸相当的 原材料，称之为下料。下料是产品制造的第一道工序在这道工序中，不同的下 料方案具有不同的材料利用率，而原材料的利用率直接影响产品的成本。下料方 案不仅与零件的尺寸有关，而且与原料的种类、规格，零件的形状、数量、成套 率( 不同零件数量间的配比) ，加工工艺( 主要是加工余量的预留) 有关“3 。线材、 杆材的下料，属于一维的下料问题，其中杆材的一维料比线材复杂，这是因为杆 材的长度有限，不能连续截取而引起的单根杆材截取余料问题所造成的。但是由 5 山东大学硕士学位论文 于长度是唯一的控制因素，杆材下料问题可以归纳和表达为数学规划问题，这属 于运筹学的领域，并已得到较好的解决。 而本文主要研究的在二维平面材料，如钢板、木板、布匹、皮革上的下料问 题，称之为二维下料。二维下下料远比一维下料复杂这不仅在于由于维数的增 加、使得对利用率的衡量指标变为面积，而不是长度，更在于二维零件的形状种 类繁多，带来的问题首先是形状描述上的困难，这不是增加一个二维坐标就能简 单解决的；其次是形状的多样性引起的形状间的搭接关系的复杂，不像只考虑长 度关系的一维下料问题那样可以做到无缝衔接。搭接关系的描述和确定，比形状 描述更为复杂和困难。我们知道，数学处理的基础和前提，在于对问题的形式化 抽象化描述。而对形状和形状搭接关系的难以描述，使得二维下料问题迄今为止 未见有一般性的有效数学方法。传统的下料过程是由有经验的技术人员或工人采 取试排方式，依赖人的经验和智能。但是当前市场竞争加剧，产品更新换代加速， 产品复杂程度加大，交货周期缩短的情况下，人工下料在时间上的消耗及下料结 果的非最优性将逐渐变得不可接受。 、现在，计算机不仅在各行各业都大显身手，也广泛应用于制造业的设计、制 造、管理和销售多个环节。下料问题的形式描述的困难和规划问题结果的不确定 性给本质上是形式逻辑处理方式的计算机处理带来的不适应性。 1 2 2 研究意义 首先，下料问题在工业生产中应用十分广泛。如造船工业、汽车工业、钣金 加工工业、服装生产、皮革加工、纸张及木材加工工业等都需要处理下料问题。 二维下料问题按照其应用范围的不同经常应用于不同的生产行业中，例如应 用于造船或汽车制造等行业，零件的外形复杂、不规则，采用火焰切害、激光切 割，等离子切割或数控线切割分离零件的优化下料问题；应用于冲裁模具，加工 各种冲裁件的优化下料问题；应用于以加工矩形零件为主的板料柔性加工系统的 优化下料问题“1 。这类零件的加工设备主要是数控冲床、数控剪床，重点应用于 机箱、机柜类钣金产品的生产上。 其次，下料问题在工业生产中占有重要的地位并与经济效益有直接关系。众 所周知，材料费在产品的成本中占有较大的比例，因而如何提高材料利用率，减 少材料损失便成为降低产品成本，提高产品竞争力的主要手段之一。而下料的首 6 山东大学硕士学位论文 要任务正是：在满足一定的约束条件下合理、有效地布置零件，以求最大限度地 利用材料。所谓在满足一定的约束条件下合理且有效地布置零件，就是要符合将 零件从材料上分离下来所采用的设备和工具的加工工艺特点与要求。 例如，在冲压件的成本中材料费约占6 0 以上，特别是大量生产时，即使将 材料的利用率提高1 ，其经济效益也相当可观而冲压件的合理下料是冲压生产 中节约材料的主要方法“1 。 再次，下料是工业生产过程中的一个重要环节。例如，在冲裁零件的加工过 程中，毛坯下料是连续性工艺的主要前导，因此下料结果的好坏直接影响到后面 的加工过程。又如，服装生产的整个过程基本上可概括为：造型设计、制作样板、 下料、裁剪及制作等儿个生产环节，下料结果的好坏也直接影响后面的服装裁剪 及制作这两个工艺环节。 另外，随着现代科学技术的发展，数控下料铣、数控裁剪机、数控气割机、 激光切割机、高速冲床等设备相继问世，为现代化生产提供了高效率、高精度的_ 切割手段。所以，无论是从节约材料还是从充分发挥这些设备优越性的角度考虑， 、 配之以自动下料系统都是十分必要的。 当前计算机技术飞速发展，无论是软件还是硬件，都在快速地更新换代。应 用原来的软硬件环境所开发出的下料系统，在相关行业曾经发挥了很大的作用。 但是，随着工业生产要求的不断提高，这些系统有的已经不能胜任现在的要求， 也发挥不了高性能硬件的潜力。因此，对下料系统提出了新的要求。例如，受制 于计算机速度和存储空闻的限制，以往的一些下料系统在算法上常过多地使用近 似法，以至于影响了利用率的提高。还有的一些下料系统，采用了穷举法进行下 料，由于运行速度慢而极大地影响了效率和实用性。 所以致力于研究有效的算法，充分挖掘计算机的潜力，开发出“智能”型的 二维下料软件还是十分必要的。综上所述，解决下料问题具有深远的理论意义及 现实意义。 1 3 二维下料的分类以及研究现状 i 刍从本世纪六十年代起，由于下料问题在工业生产中及计算机辅助设计中的 重要作用并且由于计算机技术、优化技术、计算机图形学、数据存储与提取技术 的发展，人们对下料问题的研究逐渐深入下面介绍一下二维下料的分类以及国 7 山东大学硕士学位论文 内外对下料问题研究的历史及现状。 1 3 1 二维下料的分类 平面几何排样属于p a c k i n g c u t t i n gp r o b l e m s 研究中的二维问题。最先成 功解决此问题的是p c g i l m o r e 和r e g o m o r y “1 在6 0 年代初的创造性研究并激 发人们对p a c k i n g c u t t i n gp r o b l e m s 的研究兴趣，近三、四十年来已经发表了 几百篇甚至近千篇的研究论文，提出了各种各样针对不同类型问题的求解方法。 我们下面看看二维下料问题的分类： ( 1 ) 矩形件排样问题( r e c t a n g l ep a c k i n g ) 例如矩形件布局问题，装盘问题，玻璃下料、一刀切问题等。 此问题的相对简单性和可行性使许多研究人员将不规则图形排样问题转化 为矩形件排样问题来求解，p d e c a n i 于1 9 7 8 年对单一图形的排样问题提出基于树 的搜索精确解法，但其计算速度较慢，无法应用。由于排样问题的复杂性，求 精确解非常困难，为了提高计算速度，研究人员把目光更多地投向了启发式算法。 所谓启发式算法是指一组指导算法收索方向的、建议性质的规则集，通常按照这 个规则集，计算机可在解空间中寻找到一个较好的解。由于启发式算法的设计不 依赖于纯数学中的优化理论的突破和发展，其研究和应用取得了突飞猛进的发 展，也正是由于它缺乏严格的理论推导及数学证明，使得他的设计具有很强的随 意性与创造性。虽然其计算速度非常快，但解的质量与制定的准则密切相关，才 能保证每次都能找到较好的解，更不能保证找到最优解。 ( 2 ) 冲裁件排样问题( m e t a ls t a m p i n g ) 此问题由于工艺特殊，一般只允许单排、双排或对头双排方式排样，相对简 单。国内很多人对其进行了研究，如1 9 9 4 年曹炬的冲裁件排样的整体优化及冲裁 件排样中对头双排的优化算法及实现啷。 ( 3 ) 不规则件排样问题 例如服装自动下料、板材切割与装入问题等。 实际排样中的图形很少是矩形的，而更多的是任意形状的图形，这类问题是 更难解决的一类布局优化问题，此方面的文献不多。统观全世界从1 9 4 0 年至u 2 0 0 5 年5 0 0 多篇关于p a c k i n g c u t t i n gp r o b l e m s 篚j 文献，涉及不规则图形的仅有4 0 多 篇，可见数量之少m 由于长期以来，不规则件排样问题并没有得到很好的解决， 山东大学硕士学位论文 因此人们就在不断地寻找新的办法。现在人工智能中的启发式搜索算法、进化算 法、遗传算法、神经网络、基于学习的方法等等都用于求解此类问题。 1 3 2 国内外研究现状 l 、国外研究现状 ( 1 ) 矩形图形下料的研究情况 对于矩形图形的下料问题人们研究得比较早并且已做了大量工作。例如 p a u l l ( 1 9 5 6 ) 跚。e i s e m a n n ( 1 9 5 7 ) 1 4 v a j d a ( 1 9 5 8 ) 嘲利用线性规划解决纸张剪切 的矩形下料问题。1 9 6 1 年，g i l m o r e 和g o m o r y 嘲在所发表论文中利用线性规划和 动态规划，从运筹学中著名的“背包问题( k n a p s a c k ) ”出发，提出了带有约束条 件的剪切下料算法。h a i m s 和f r e e m a n ( 1 9 7 0 ) m 利用线性规划和二维动态规划把多 参数问题转化为多阶段问题。h e r z ( 1 9 7 2 ) 嘲利用递归搜索方法分阶段解决矩形下 料的下料问题。 另外，c h r i s t o f i d e s 和w h i t l o c k ( 1 9 7 7 ) 0 1 提出了用动态规划的树状搜索方法。 解决矩形剪切下料问题。可是，因为所耗费的计算时间也是下料问题的一个重要 考虑因素，此算法在解决实际应用过程中的大规模下料问题时效率不高。 ( 2 ) 不规则图形下料的研究情况 对于任意形状图形的下料问题，目前所采用的解决方法归纳起来主要有以下 三种n 0 1 ；。、。 近似矩形法，即把单个或几个不规则图形组合成矩形单元，然后对矩形单元 进行下料。 1 9 7 6 年纽约大学的瓶a d a m o w i c z 在所发表的博士论文中利用矩形模块分两 阶段对二维不规则图形进行下料。1 9 7 7 年a a l b a n “”发表论文，论文的基本思想 是“两步法”和“人机交互法”。1 9 9 1 年，c h e o k 和n e e “2 1 提出了用于造船业的不 步自动下料方法。c y u z u “”也曾于1 9 8 7 年提出了基于这种方法的用于服装裁剪的 专家系统。 启发式推理方法。此方法模仿人工下料，定义大量的规则，使用启发式推理 方法，由计算机决定下料方案，不需要人的参与。但组建这样的系统需要丰富的 经验。 f r e e m a n “”于1 9 6 4 年和后来的r a d a c k 与b a d l e “。于1 9 8 2 年提出一个与下料问 9 山东大学硕士学位论文 题十分类似且很有趣的问题一拼板玩具问题。1 9 8 0 年，a a l b a n o 和s a p u p p o o ” 提出了一种自动下料方法，在论文中他们使用了人工智能的典型启发式搜索策 略，将下料问题转换为寻找一条最优路径的问题。1 9 8 3 年，d a g l i 和t o t o g l u “” 通过决定图形的优先权算法，这种不加选择地判断边界匹配的各种可能性的方 法，耗费了大量的计算时间。1 9 8 9 年，c h u n g m l 及其合作者解决了复杂轮廓的钣 金下料问题。1 9 9 4 年，p r a s a d “”在文章中讨论了边界匹配的基本原理。 智能优化法。即以最小浪费率为目标函数，采用诸如人工神经网络、模拟退 火法、遗传算法等智能优化方法，在整个解空间中进行搜索。 近年来，国际上掀起了一股人工神经网络的研究热湖。神经网络的应用研究 取得了很大的成绩，涉及面非常广泛。一些学者已经将人工神经网络技术应用到 下料领域中，但在这方面所进行的研究还处于探索阶段。m s r i r a m 和s m k a n g ( 1 9 9 0 ) 。”利用改进的h o p f i e l d 人工神经网络解决t _ - 维模块的线路下料问 题。c x z h a n g 和d a m l y n s k i ( 1 9 9 0 ) o ”运用k o h o n e n ( 1 9 8 2 ) 和r i t e r ( 1 9 8 6 ) 提出的 人工神经网络模型的拓扑映射特征解决大规模集成电路的下料问题。s s k i m 和 c m k y u n g ( 1 9 9 2 ) 1 针对印刷电路板的下料问题，提出一种自组织辅助下料算法 ( s o a p ) 。这篇文章所解决的问题不是将任意形状的图形在规则的区域上进行下 料，而是在任意形状的区域上进行下料 目前，人们己经将模拟退火算法运用到二维下料问题中。模拟退火算法是一 种著名的全局优化算法嘲1 ，是采用概率搜索方法的组合优化技术。模拟退火算法 是基于m o n t ec a r l o 迭代求解的一种启发式随机搜索法，它非常适合解决具有大 范围搜索空间的问题。例如，s h a h o o k a r 和m a z u m b e r ( 1 9 9 1 ) 矧运用这种算法解决 了大规模集成电路中的布局问题。h e r a g u 和a l g a ( 1 9 9 2 ) 利用模拟退火算法解决 印刷中的下料问题。j a i n f e n y e s 以及r i c h t e r ( 1 9 9 2 ) 口力用此算法解决t r _ 维冲裁 图形下料问题。c h o ( 1 9 9 3 ) 也对钣金冲裁图形下料问题加以解决。 另外，h i s m a i l t 别和k k b h o n ( 1 9 9 2 ) 侧提出了用于解决二维冲裁件下料的 自动成组匹配算法。文章将整个下料过程分为两个阶段。首先，提取边界信息以 便形成边界数组，进而获得最佳边界匹配。然后运用遗传算法的非确定性理论， 产生下料结果。上述几个文献单纯采用了模拟退火算法或遗传算法，虽然在理论 上可以搜索到全局最优方案，但是单纯采用模拟退火算法或遗传算法具有一个致 1 0 山东大学硕士学位论文 命的缺点运算速度慢，效率低。 2 、国内研究现状 国内对优化下料的研究尽管起步较晚，但也做了大量工作。常用的方法主要 源于苏联学者a k h y p b a p a h j i o b 的板料冲压最佳排料图编制过程的自动化 针对下料问题的不同方面，最早提出的有加密点法、人机对话法，随后出现点阵 判交法、平行线分割一步平移法等哪儿蜘嘲。浙江大学、上海交大、西安交大、清 华大学及华中理工大学等院校均做了一定的研究。 1 9 9 2 年，李新军、熊火轮等发表点阵判交一一种计算机自动排样系统设 计的新方法嘲。文章介绍了一种新的非几何判交方法。指出判断两个几何元素 是否存在交点，即求交，是下料的基础性工作之一。其方法的优劣直接影响着下 料程序的可靠性和效率。判断两个几何元素是否相交，从图形上看是十分容易的， 但运用解析法在计算机上用程序实现却很费周折。文章论述了屏幕光栅点阵判交 的中心思想是判断某一直线所要经过的点是否已经被打亮。 n ， 对于冲裁件下料，国内所作的研究工作比较多，在算法上也已比较成熟。其 下料方式可分为：普通单排、普通双排、对头单排、对头双排。所需解决的主要 问题是冲裁步距和冲裁角度的计算问题。 o 例如，上海交通大学的夏尊辉、卞铭甲、李绍成发表了单双排冲裁件的最 佳排样法微机所确定的方案较人工方案，材料利用率提高了5 以上。文章中 将下料工件的几何图形信息化采用坐标点法( 即加密点法) 近似代表真实图形。为 使问题简化，只考虑了同一种图形在“无限长”条料下料的情况。 华中理工大学c a d 中心的曹炬、周济于1 9 9 3 年发表了冲裁件排样最优化的 数学模型及算法嘲。文章通过对数学模型的分析，解决了冲裁件下料问题。下 料后所得的最佳冲裁角度与冲裁步距的计算精度分别可达i 度和0 0 0 1 m m ，在3 8 6 型微机上平均计算时间为4 分钟。但是此优化模型没有对板材的大小加以限制， 即不能在有限长、宽的板料上下料，需进一步给出整体优化模型以及相应的算法。 1 9 9 8 年，华中理工大学的董长双、杨楚民、宾鸿赞发表了冲裁零件二维排 样优化。文章提出了在以往的冲裁件优化下料的计算机求解方案中，人们 一般将卷板当作无限长的条料或将有限长、宽的板料裁成若干条等宽度的条料， 所采用的优化模型也是建立在此基础上的。当将有限长宽的整体板料在冲压设各 山东大学硕士学位论文 上进行x ，y 轴双向送料冲裁时，上述建立的模型将不再适用。这篇文章给出了以 在有限长、宽的整体板料上能冲裁出的最大样件个数为目标的整体优化模型及算 法。 北京工业大学的杨洪旗，话安交通大学的储家佑发表了冲裁件的排样优化 与动画排样寻优法3 。可输出材料利用率特征曲线及最佳排样图并设计了动 画下料子程序。该方法形象直观，操作方便，但过多的依赖于人的参与。所得的 下料结果与操作者的经验直接相关。 浙江大学的周泓一、金廷赞的二维不规则形状的最优布局问题一计算机 辅助服装裁片自动排料系统d 町，将计算机图形学和人工智能相结合，运用人 工智能的启发式方法把裁片的二维最优布局问题转化为在一个状态空间中寻找 一条最优路径的问题。将从初始状态出发的所有可能达到的状态集合视为个有向 图，其中节点对应状态，边对应算子，将问题视为一个寻找从初始节点到目标节 点路径的搜索过程。 上海交大的杨世胜、吕荣发表了服装自动排料初探口”，提出了用服装 样板几何图形的数学模型来实现图形的输入，以及对图形进行各种判断、处理。 其最优下料方案的材料利用率达9 2 。判断板样是否相交，贯穿于整个下料过程。 另外，东北大学的聂瑞华，在其硕士论文中，对任意形状的图形进行下料。对以 往算法中将任意形状的轮廓用直线或圆弧代替的方法进行了改进。将任意形状的 曲线用参量样条逼近，也把二维最优下料问题转化为在一个状态空间寻找一条最 优路径的问题。 1 4 本文的研究内容 由于下料问题是n p 完全问题，并且要排放的图形形状不规则，数量又多，同 时下料材料多了许多不规则约束，解空间呈指数倍数地扩大，出现组合爆炸现象， 要达到最佳排样，非常困难。首先对一图形样件来说，它有无数个取向，对于所 有要排放的图形；先排哪一个后排哪一个，即下料的顺序数量极大，两者组合在 一起，计算量之巨大，即使用高速计算机耗时也很惊人。用动态规划、分支定界 等基于穷举思想的算法都不能顺利的得到好的结果。目前对于不规则图形直接下 料的求解方法比较认同的是采用启发式搜索方法。 1 2 山东大学硕士学位论文 本文所要解决的问题在此基础上更对原材料进行了约束，即带有瑕疵的原材 料的自动下料问题。本文针对此类下料问题，在原有算法的基础上提出了一种改 进的基于启发式搜索策略的自动下料算法，充分考虑人工下料时的经验信息，提 出了对原材料的瑕疵和待下料图形的初始化方法以及基于分组的定序规则算法， 不但提高了材料利用率，而且使自动下料图更易于进行交互式的修改；移动算法 采用了启发式搜索策略，可以很快确定待下料图形和瑕疵的位置：对于小块图形， 进行插空下，提高了利用率；靠接算法通过待移动区域确定可能发生碰撞的实体， 先大步长移动，然后微调，从而减少大量的盲目检测，提高了下料的精度。 本文主要采用的是启发式搜索算法和碰撞检测算法，同时结合计算机图形处 理软件a u t o c a d 2 0 0 0 与其二次开发软件o b j e c t a r x 进行编程。主要采用了矩形包 络算法和旋转对排法来处理不规则图形和瑕疵处理，然后调用初始化程序和定序 规则算法对图形进行处理，最后采用启发式搜索算法进行优化排样，在实验中取 得不错的效果。 1 5 主要内容和章节安排 第二章介绍了下料问题的实质和它的几种主要算法，主要介绍了搜索算法 的；第三章介绍了碰撞检测算法的原理和几种不同的检测算法；从第四章并始介 绍了本文所采用的下料算法和实现。第五章介绍了下料系统的设计思路。第六章 提出了现阶段存在的不足和以后的研究方向。 第二章二维下料算法 从前面我们知道二维下料问题属于非确定多项( n o n d e t e r m i n i s t i c p o l y n o m i a l ，简记n p ) 完全问题，要研究二维下料问题首先要了解什么是n p 完全 问题，面对n p 完全问题应该怎样去解决。下面让我们详细介绍一下n p 完全问题。 2 1 肿完全问题 2 1 1n p 完全问题的引出 构造算法的目的是能够解决问题的所有实例，而不单单是某一个实例。问题 ( p r o b l e m ) 是需要回答的一般性提问，通常含有若干个满足一定条件的参数。问 题通过下面的描述给定：( 1 ) 描述所有参数的特性，( 2 ) 描述答案所满足的条件。 问题中的参数被赋予了具体值的例子称为实例( i n s t a n c e ) 。衡量一个算法的 好坏通常用算法中的加、减、乘、除和比较等基本运算的总次数c ( i ) 同实例i 在 计算机计算时的二进制输入数据( 输入规模长度d ( i ) ) 的大小关系来度量。算法 的计算复杂度为： c ( d = ，( d ( 功、 ( 2 - 1 ) 假设问题和解决该问题的一个算法己经给定，若给定该问题的一个实例i ， 存在多项式函数g ( x ) ，使得计算时间： c ( o c r g ( ( d ) ( 2 - 2 ) 成立，我们称该算法对实例i 是多项式时间算法( p o l y n o m i a lt i m ea l g o r i t h m ) 3 。 若存在g ( x ) 为多项式函数，且对该问题任意的一个实例i ，都有( 2 2 ) 成立， 则称该算法为解决该问题的多项式时间算法。当不存在多项式函数g ( x ) 使得上式 成立时，称相应的算法是非多项式时间算法，或指数时间算法( e x p o n e n t i a lt i m e a l g o r i t h m ) “3 。 对于给定的一个优化问题，若存在一个求解该问题最优解的多项式时间算 法，则称给定的优化问题是多项式可解问题，或简称多项式问题，所有多项式问 题集记为( p o l y n o m i a l ) 。 评价一个算法的依据是该算法在最坏实例下的计算时间与实例输入规模的 关系“： 1 4 c ( d a g ( l ( o )或者c ( ，) ；d ( g ( d ( ，) ) ) ( 2 - 3 ) 存在多项式函数g ( x ) 满足上式时，算法为多项式算法。存在多项式算法的问题集 合为多项式问题类。 比多项式问题类可能更广泛的一个问题类是非确定多项( n o n d e t e r m i n i s t i c p o l y n o m i a l ，简记n p ) 问题类。n p 类是通过判定问题引入的。如果一个问题的每 一个实例只有“是”或“否”两种答案，则称这个问题为判定问题( d e c i s i o n r e c o g n i t i o n f e a s i b i l i t yp r o b l e m ) 。称有肯定答案的实例为“是”实例 ( y e s - i n s t a n c e ) 称答案为“否”的实例为“否”实例或非“是”实例 ( n o - i n s t a n c e ) 。考虑将求解判定问题的算法分为两个阶段： ( 1 ) 猜测阶段：求出或猜测该问题的一个解。 ( 2 ) 检查或验证阶段：一旦解己经选定，将猜测的解作为输入，验证此解是否为 该实例“是”的回答。我们称实例。是”回答的解为实例的可行解，否则称为不 可行解。 若存在一个多项式函数g ( x ) 和一个验证算法h ，对一类判定问题a 的任何一个 。是”实例i ，都存在一个字符串s 是i 的可行解，满足其输入长度d ( s ) 不超过 g ( d ( i ) ) ，其中d ( i ) 为i 的输入长度，且算法h 验证s 为实例i 的可行解的计算时间 f ( h ) 不超过g ( d ( i ) ) ，则称判定问题a 是非确定多项式的。构造字符串的过程及验 证算法h 一起构成一个算法，称为非确定多项式时间算法。所有非确定多项式问 题的集合用n p 表示。一般认为p n p 。 已知判定问题a l 和a 2 ，若存在多项式函数g ( x ) 和g 。( x ) ，使得对a l 的任何实 例i ，在多项式时间内构造a 2 的一个实例，其输入长度不超过g ( d ( 1 ) ) ，并对a 2 的 任何一个算法h 2 ，都存在问题a l 的一个算法h i ，使得h l 算法调用h 2 算法且使得计 算时间： 厶( j ( 功s 厶：凶( d ( 功) ( 2 4 ) 其中厶。p ( ，) ) 和厶：( ( x ) ) 分别表示算法h 1 和h 2 的计算时间与实例输入长 度x 之间的关系，则称问题a 1 多项式归约为问题a 2 。 对于判定问题a ，若a n p ，且n p 中的任何一个问题可在多项式时间内规约 为a ，则称a 为n p 完全问题p - c o m p l e t e 或n p 完全) 。可以表示为a n p c 。 山东大学硕士学位论文 2 1 2 解决n p 完全问题的思路 n p 完全问题是n p 类中最困难的问题。对于n p 完全问题，有证据表明，此类的 许多重要问题，至今无法找到多项式算法，因此不能被快速的解决。因而，求其 有效的近似解法是必由之路，关于n p 完全难题的近似解法还有待进一步发展。对 于这类问题，以目前已成熟的计算理论和算法，或者根本无法求解，或者其求解 的计算量是爆炸性的，即使用最快的计算机进行计算，所花费的机时和费用将不 是人们所能接受的。 解决n p 完全问题虽然是相当困难的，但是n p 完全问题又是人们常常碰到的问 题，所以人们还是千方百计采用各种方法来解决或者近似解决n p 完全问题。目前， 解决n p 完全问题一般有下面四种思路： 1 ) 采用启发式的( h e u r i s t i c ) 方法。采用问题的相关信息作为启发，在局部最 优的情况下来近似解决n p 完全问题，最后的结果往往不是最优的，但是却是足 够“好。 2 ) 近似地而不是精确地解决问题。一般的，可以找到一个比较快的算法，但是 它不能精确的解决n p 完全问题，而只能证明最后的结果很接近n p 完全问题的结 果。 3 ) 采用指数级时间的解决方法不管怎样，如果要精确地解决n p 完全问题的 话，可以编一个需要花指数级时间的算法程序来解决n p 完全问题，这样就不必 担心最后是否能够得到最优的结果了。 4 ) 提取问题的一个较好模型，然后进行解决。当在对具体n p 完全问题进行抽象 化时，往往忽略了看上去好像不重要的而在现实处理中又很复杂的部分或者因 素，从而简化了问题。不过看上去不重要的部分或者因素也许正是重要的部分 或者因素，很可能会把n p 完全问题变成了非n p 完全问题了，改变了问题的本质。 2 2 二维下料的常见几种算法介绍 了解t n p 完全问题，那么我们看看解决属于n p 完全问题的二维下料问题的几 种常见算法。 ( 1 ) 数学方法“ 现有的大部分布局问题的模型，一般都是将原问题进行简化( 包括几何形状 物体、约束和目标知识) ，建立单纯的数学模型，便于求解。但是当原问题涉及 1 6 山东大学硕士学位论文 一些不易用数学模型表达的约束条件时，采用近似方法得到的数学模型往往会与 原问题产生较大的偏差。并且当问题规模增大、解空间急剧增加时，它们的求解 复杂性变得很强、很难或无法得到有效解。 ( 2 ) 图论方法 图论方法经常用于求解下料问题，它是以图中的结点代表待布局物体，弧线 代表布局物体之间的关联关系，由此将下料问题转化为在一个已知的连接图中寻 找最大独立集或最大权平面子图问题：然后借助于分枝定界、整数规划及动态规 划等方法进行问题的求解。尽管作为组合数学的重要组成部分的