（控制理论与控制工程专业论文）带残损原材料二维优化下料问题的研究.pdf

山东大学硕士学位论文 摘要 目前，随着可持续性发展战略的提出，全球对资源消耗问题日益重视， 优化利用资源是我国经济发展战略的重要内容之一，也是整个世界最重要的 研究课题之一。从平面原材料上切下各式各样的下料件，使材料的利用率最 高，这是二维优化下料问题。二维下料问题广泛存在于机械制造、服装、皮 革以及玻璃加工等行业中，它在理论属于具有最高复杂性的n p 完全 ( n o n d e t e r m i n i s t i cp o l y n o m i a lt n n ec o m p l e t e ) 问题，因此，开展对下料问题 的研究具有重要的理论意义和工程应用价值 本文主要讨论了不规则形状的下料件在带残损原材料上的下料方法。介 绍了下料件多边形、残损多边形的表示方法，多边形的平移、旋转、判交等 基本理论通过遗传模拟退火算法产生下料件的最优次序和角度，然后采用 基于左下角( b o s o m 1 e f t ) 策略的快速定位启发式算法进行布局。 本文的研究工作集中体现在以下几个方面： 1 自动下料系统分为信息输入、自动布局和结果输出三大部分，本文根 据课题的主要方向，设计了带残损原材的二维不规则下料系统的结构模型 2 系统的信息输入主要有a u m c a d 绘图软件输入和人机交互界面输入 两种，本文介绍了a u t o c a d 中d x f 文件的结构，为系统读取下料件图形数 据的程序编写打下了理论基础；同时，本文采用m a t l a b 语言，设计了友 好的人机交互界面，从而实现了原材料信息、初始条件等数据的输入以及结 果输出等功能。 3 将残损多边形视为已定位好的下料件，在排样过程中，将每一个待排 下料分别与已排下料件和所有的残损进行重叠检验，从理论上较易实现带残 损原材料的二维下料问题，但在实际运行时，必定会使系统的计算复杂度和 运行时间有所增加，因此，本文采用“最小最大测试”和逐边求交的二次判 交法，大大缩短了多边形的重叠判定时间，尤其在待排下料件和残损多边形 的判交过程中，效果突出 4 算法是系统是否真正实现优化的关键，本文从应用的角度对遗传算法 山东大学硕士学位论文 和模拟退火算法做了认真的分析和研究，然后将遗传模拟退火算法应用于二 维下料问题中，给出了遗传算法求解的编码方法、适应度函数的定义，遗传 山东大学硕士学位论文 a b s t r a c t a tp r e s e n t ，w i t ht h ep r o p o s a lo fs u s t a i n a b l ed e v e l o p m e n ts t r a t e g y , w ep a y m o r ea n dm o r ea t t e n t i o nt ot h eg l o b a lr e s o u r c e sc o n s u m p t i o ni s s u e i tt u r n so n eo f t h em o s ti m p o r t a n tc o n t e n t so fo u re c o n o m i cd e v e l o p m e n ts t r a t e g yt om a k et h e b e s to f r e s o u r c e sa n da l s ot h ee s s e n t i a lr e s e a r c hs u b j e c ti nt h ew o r l d w i d e c u t t i n g o f fav a r i e t yo fc u t t i n g - s t o c k sf r o m $ 1 l r f a c er a wm a t e r i a la n dm a x i m i z i n gi ti s t w o - d i m e n s i o n a lc u t t i n g - s t o c kp r o b l e m ，w h i c hi s w i d e l ye x i s t e di nm e c h a n i c a l m a n u f a c t u r e ，c l o t h i n g ，l e a t h e rm a k i n ga n dg l a s sc u t t i n g ，e t e i nt h e o r y , i tb e l o n g s t ot h em o s tc o m p l i c a t e dn p c o m p l e t ep r o b l e m ，t h e r e f o r e ，as t u d yo nc u t t i n g - s t o c k i so f g r e a tt h e o r e t i c a la n de n g i n e e r i n ga p p l i c a t i o ni m p o r t a n c e t h i sa r t i c l em a i n l yd i s c u s s e sh o wt oc u ts t o c kw i t hi r r e g u l a rp o l y g o n a l c u t t i n g - s t o c ko nd a m a g e dr a wm a t e r i a l i ti n t r o d u c e st h eb a s i ct h e o r yo f r e p r e s e n t i n gm e t h o do f c u t t i n g - s t o c kp o l y g o na n dp o l y g o n sh o r i z o n t a lm o v e m e n t , c i r c u m r o t a t i o na n ds oo n t h r o u g hg e n e t i cs i m u l a t e d a n n e a l i n ga l g o r i t h m , i t p r o d u c e so p t i m a lo r d e ra n da n g l eo fc u t t i n g - s t o c ka n dt h e na d o p t si m m e d i a t e l o c a t i o nh e u r i s t i ca l g o r i t h mt ol a y o u to nt h eb a s i so f b o t t o m - l e r ( b l ) s t r a t e g y t h i sp a p e rf o c u s e so nt h ef o l l o w i n ga s p e c t so f s t u d y ： 1 a u t o - c u t t i n g - s t o c ks y s t e mi sd i v i d e di n t ot h r e ep a r t s ：i n f o r m a t i o ni n p u t , a u t o l a y o u ta n dr e s u l to u t p u t i th a sd e s i g n e ds t r u c t r r a lm o d e lo f t w o d i m e n s i o n a l i r r e g u l a rc u t t i n g s t o c ks y s t e mo nd a m a g e dr a wm a t e r i a la c c o r d i n gt ot h e m a j o rd i r e c t i o no f t h et a s k 2 s y s t e mi n f oi n p u ti n c l u d e sa u t o c a ds o r w a r ei n p u ta n dp e r s o n - t o - m a c h i n e i n t e r f a c ei n p u t i ti n t r o d u c e sd x ff i l es t r u c t u r eo f a u t o c a d ，w h i c hm a k e st h e t h e o r e t i c a lb a s i sf o r s y s t e mr e a d i n go fc u t t i n g - s t o c k g r a p h i cd a t aa n d p r o g r a m m i n g a tt h es a m et i m e , i ta d o p t sm a t l a bl a n g u a g et od e s i g n f r i e n d l yp e r s o n t o - m a c h i n ei n t e r f a c et h e r e f o r ef u l f i l l i n gt h ef u n c t i o n so fr a w m a t e r i a li n f oa n di n i t i a lc o n d i t i o nd a t ai n p u ta n dr e s u l to u t p u t 3 c o n s i d e r i n gd a m a g e dp o l y g o na sl o c a t e dc u t t i n g s t o c k , i nt h ep r o c e s so f m 山东大学硕士学位论文 a r r a n g i n gs a m p l e s ，p u t t i n ge a c hs t a n d - t oa n da r r a n g e dc u t t i n g s t o c ki n t o o v e r l a p p i n ge x p e r i m e n t , i ti se a s yt oc o m p l e t et w o d i m e n s i o n a lc u t t i n g - s t o c k p r o b l e mo nd a m a g e dr a wm a t e r i a li nt h e o r y b u ti np r a c t i c e ，i tm u s ti n c r e a s e a l g o r i t h mc o m p l e x i t ya n dr u n n i n gt i m e i tg r e a t l ys h o r t e n st h ep o l y g o n a l o v e r l a p p i n g j u d g i n gt i m et h r o u g hm a x & m i nt e s t 4 a l g o r i t h mi sk e yt oo p t i m i z et h es y s t e m t h i sa r t i c l em a k e sc a r e f u la n a l y s i s a n dr e s e a r c ho ng e n e t i ca l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r i t h mf r o m a p p l i c a t i o nv i e w p o i n ta n dt h e na p p l i e si tt ot h et w o - d i m e n s i o n a lc u t t i n g s t o c k i s s u e t h ec o d i n gm e t h o d ，f i t n e s sf u n c t i o n d e f i n i t i o n , g e n e t i ca l g o r i t h m o p e r a t o r sa n ds o m ek e yp a r a m e t e r sa r eg i v e na n dt a k e ss i m u l a t e da n n e a l i n ga s i n d i v i d u a ls e l e c t i o ns t r a t e g yt op r o d u c eo p t i m a lc u t t i n g - s t o c ko r d e ra n de a c h c u t t i n g - s t o c ka n g l et h e nl o c a t ei tu s i n gh e u r i s t i ca l g o r i t h m 5 a u t o - l a y o u ti st h em o s ti m p o r t a n tp r o c e d u r ei nt h ep r o c e s so fc u t t i n gs t o c k o nt h eb a s i so fb ls t r a t e g y , t h i sp a p e ra d o p t si m m e d i a t el o c a t i o nh e u r i s t i c a l g o r i t h mt og i v ed e t a i l e dp r o c e d u r ef o rr e a l i z a t i o na n dt e s ti t sv a l i d i t y t h r o u g he x a m p l e k e y w o r d s ： g e n e t i ca l g o r i t h m ；s i m u l a t e da n n e a l i n g a l g o r i t h m ；o p t i m a lc u r i n g - s t o c k ；i r r e g u l a r p o l y g o n ；h e u r i s t i ca l g o r i t h m i v e 盘 、 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究所取得的成果。除文中已经注明引用的内容外，本 论文不包含任何其他个人或集体已经发表或撰写过的科研成果。 对本文的研究作出重要贡献的个人和集体，均已在文中以明确方 式标明。本声明的法律责任由本人承担。 论文作者签名：重 兰e 1 期： 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定， 同意学校保留或向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅；本人授权山东大学可以将本 学位论文的全部或部分内容编入有关数据库进行检索，可以采 影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：王f 兰导师签名： j v 聋 山东大学硕士学位论文 1 1 选题的意义 第1 章绪论 目前，随着可持续性发展战略的提出，全球对资源消耗问题日益重视， 我国是一个人口众多、人均资源相对贫乏的国家。从资源拥有量来看，虽然 我国资源总量不少，但人均资源相对贫乏，资源紧缺状况将长期存在。从新 中国成立以来资源的勘探、开发和利用来看，我们走的是依靠高消耗资源、 粗放式经营的经济发展之路，存在着高投入低产出和浪费严重的现象。2 0 0 5 年7 月6 日，国务院关于做好建设节约型社会近期重点工作通知中提出建 立节约型和谐社会。优化利用资源是我国经济发展战略的重要内容之一，也 是整个世界最重要的研究课题之一另一方面，对一个企业而言，提高原材 料的利用率，降低成本，是该企业在市场竞争中立于不败之地的必要条件。 因此在“下料”这一环节中使能源得以充分利用越来越受到人们的重视 优化下料就是在给定的原材料上按一定的要求切割下一些给定的下料 件，且使原材料的利用率最高或者产生的废弃料最少早期的下料主要是人 工下料法，就是在给定的原材料上先切割出最大的零件，再切割剩下的零件 中可能最大的零件，依次切割，直至最后无法切割出任何一种规格的零件为 止，剩下的边角余料就当废料处理这种人工下料方法除浪费十分惊人外， 排料计算复杂，耗费工程技术人员的大量精力，且容易出错。随着计算机技 术的发展，计算机辅助设计与辅助制造已经成为现代工业自动化中必不可缺 少的主要技术手段，人们利用计算机进行优化排样下料，不仅可以减轻工作 人员的劳动强度，而且可以提高原料的利用率和速度。因此研究优化下料问 题，是一项具有重大经济意义的重要课题 下料问题的理论研究涉及到线性规划、动态规划、启发式算法以及人工 智能等多种学术研究前沿理论【，6 0 年代至今国内外许多学者从不同的应用 领域用不同的方法在优化下料方面进行研究，经过几代人的努力，虽然取得 了初步的成果，但迄今尚无成熟的理论和有效的数值计算方法。研究优化下 料问题不仅具有一定经济效益和社会效益，还会对学术的深层发展和繁荣具 山东大学硕士学位论文 有一定的推动意义 近几年，国内外不少学者从事优化下料方面的理论和计算机算法的研究， 也形成了一些实用的软件产品，其中二维不规则形状下料的程序只有少数几 种，而带残损原材料的二维不规则优化下料的程序更是少见。而实际生活中， 原材料在生产、运输等环节中由于各种原因可能会造成残损，对于这种情况， 目前一般采用人工方法或人机交互式方法下料，工人操作困难、原材料的利 用率和工作效率都很低。因此，本文选择带残损原材料的优化下料问题进行 研究。 1 。2 下料问题的实质和分类 优化下料问题( 有些文献称为排料或布局问题) 就是在给定的原材料空间 ( 平面) 上找到被排零件的全局最优或近优布局，使得材料的利用率最高，或 者是耗材最少。许多行业或工业都存在优化下料问题，例如建筑业中的钢筋 的裁用、棒材的下料；布料皮革的裁剪，玻璃的裁制，家具板材的排样、冲 裁模设计中的工件下料等等。我们从不同的角度把下料问题进行分类： 1 按原材料和下料件的维数可将优化下料问题划分为一维优化下料问 题、二维优化下料问题和三维优化下料问题。 ( 1 ) 一维优化下料是指条型材、钢筋或棒料的优化下料它仅需考虑一 个方向的变化，相对来说比较容易，目前通过线性规则或智能算法，人们已 编制出较为满意的优化程序。 ( 2 ) 从平面原材料上切下各式各样的下料件，使材料的利用率最高，这 是二维优化下料问题。二维下料问题广泛存在于机械制造、服装、皮革以及 玻璃n t 等行业中。例如在机械制造业中从同一块钢板上切割出不同的零件， 在服装业中，从一定宽的布匹上裁剪出各种衣片等。由于该问题的复杂性以 及其重大的经济意义，目前已经引起国内外许多学者的研究兴趣。 目前二维优化下料问题被大多数研究人员分为两种情况：一种是下料件 为规则形状( 如矩形、规则多边形等) 的情况，研究的主要内容是如何采用 不同的技术手段使其达到最优设计；另一种是下料件为不规则形状，特别是 对象中含有凹多边形或者带有孔洞等情形，计算的复杂度会大大增加。现在 2 山东大学硕士学位论文 研究得比较多的是单一不规则件排样问题：如冲裁件的普通单排、普通双排、 对头单排和对头双排等排样问题。 ( 3 ) 三维优化下料问题是指原材料和下料件在坐标系的最只z - - 个方 向均有特定要求的情况。如集装箱内货物的排放、配电柜内设备、元件的布 置等等。三维下料问题是优化下料问题中较复杂的一类问题，很难用数学方 法得到最优解 2 按下料件的形状把优化下料分为规则形状的下料问题和不规则形状的 下料问题。 ( 1 ) 规则形状的下料指矩形、圆柱形等规则物体的下料问题。早期优化 下料问题的研究对象主要就是规则形状的物体。在二维规则物体的下料中， 矩形件的下料最为普遍，而直角切割( 矩形下料件的边必须和原材料的边平 行) 中的g u i l l o t i n e ( 闸刀式) 切割又是常见的切割方式，如玻璃切割、纸 张裁剪等，它要求矩形零件下料时的一系列切割路径都必须是边到边( e d g e t oe d g e ) 的切割。这类问题一般使用分枝界定法求解【2 l ，算法通过构造一棵 搜索树来遍历所有可能的切割形式。其中初始原材料矩形为树根，树上节点 表示切割原材料过程中产生的矩形块的集合。 ( 2 ) 不规则物体的下料问题在工业中大量存在，其主要问题就是确定不 规则物体的最佳组合，以使在互不干涉的情况下将其放入装载容器中。 另外，按原材料的情况来分，下料问题又可分为单一原材料的优化下料 问题、多规格原材料的优化下料问题和带残损原材料的优化下料问题等。文 献3 中还把下料问题分为材料的切割问题、排样问题和装箱问题。还有的学 者把下料问题分为人工经验下料、交互式下料、自动下料等等。 1 3 二维优化下料问题的研究和发展概况 1 3 1 二维下料问题的描述 从平面原材料上切下各式各样的下料件，使材料的利用率最高，这就是 二维优化下料问题。许多行业或工业都存在优化下料问题，例如布料皮革的 裁剪，玻璃的裁制，家具板材的排样、冲裁模设计中的工件下料等等在许 山东大学硕士学位论文 多行业中，如服装加工，下料件是不规则的形状，而且原材料上经常有挑线、 污渍、孔洞等残损，处理这样的下料问题不仅要考虑下料件的尺寸、形状、 纹理要求，还要考虑如何避开残损。 二维下料问题可以描述为：将一系列二维不规则形状的下料件p l ，尸2 ， p n 合理地排放在原材料p 中，使原材料的利用率( 下料件面积，原材料面积) 最高，并满足下列约束条件 4 1 ： ( 1 ) p i ，巧互不重叠；i ，j = l ，2 ，疗 ( 2 ) p i 必须放在，内；i = l ，2 ，玎 ( 3 ) 满足一定的工艺要求：( 比如西服面料的纹理要求) ( 4 ) 避开残损。 上述问题涉及到计算几何、计算机图形学、运筹学、逻辑推理等多学科、 多领域的知识，属于复杂的组合优化问题，其复杂性表现在：一是约束条件 很难用数学模型完全、准确地描述，需要用复合知识模型表达；另外，即使 下料问题能用数学模型来描述，求解该数学模型或复合知识模型的复杂度也 是n p 完全( n o n d e t e r m i n i s t i cp o l y n o m i a lt i m ec o m p l e t e ) 问题。目前，不少国内外 学者从不同的应用领域用不同的方法在进行这方面的研究。 1 3 2 国内外的研究状况 自2 0 世纪6 0 年代，随着计算机技术的发展，人们就开始二维优化下料 方面的理论和计算机算法的研究。1 9 6 5 年，g i l m o r e 和g o m o r y l 5 发表文章， 用线性动态规划方法解决下料问题；其后，h a i m s 和f r e e m a n ( 6 1 的规则方法用 于矩形下料，其待下料件数量不受限制，每一步都将矩形下料件放在原材料 的一个角上，然后依次规划求出最优解；a d a m o w i c z 和a l b a n o ( ? 1 采用了矩形 包络法，把不规则形状物体的布局转化为矩形布局问题。这些方法比起人工 排料是行之有效的，但解决有特殊限制的下料问题，存在着种种弊端。 2 0 世纪9 0 年代以来，人们开始把遗传算法、模拟退火算法、人工神经 网络、禁忌搜索等智能优化算法引入异形件的下料中h e c k m 锄【8 9 l 等人采 用模拟退火算法求解，其中考虑了下料件的任意角度旋转，主要针对纺织品 加工行业，在排样时考虑了花色、条纹的约束，设置的目标函数由两部分组 4 山东大学硕士学位论文 成，一个是占用面积，另一个是面积的惩罚函数，通过变动参变量来获得领 域空间，这种算法的缺点是有时会限入局部最优。d a 班和s t a i c c y 【1 0 】根据下料 问题和调度问题的相似性，提出了一种集人工智能( a i ) 和运筹学( o r ) 的 方法来解决优化下料问题。j 和w a l k o w i a k 1 i 】于1 9 9 8 年提出了一种人机交互 的二维单原材异形材下料的禁忌表搜索算法。虽然每种算法较以前的经典算 法都有所改进，但随着问题的规模和复杂度越来越大，单一算法的性能就受 到局限，所以如何合理结合构造新的算法，在两个单一算法间取长补短是更 好解决二维下料问题的有效途径 在国内，对于下料问题的研究始于8 0 年代，浙江大学周泓一、金廷赞的 二维不规则形状的最优布局问题计算机辅助服装裁片自动排料系统 1 2 1 ，将计算机图形学和人工智能相结合，运用人工智能的启发式算法把裁片 的二维最优下料问题转化为在一个状态空间中寻找一条最优路径问题。华中 理工大学的曹炬，从拼图游戏中得到启发构造了一个异形零件优化排样下料 的拟合算法【1 3 1 。文献【4 】从下料件的数学性态出发，采用临界多边形算法进行 周边启发式的搜索。文献【1 4 】将二维下料问题建模成旅行商问题，并在原有 模型的基础上引入下料件的旋转，提出混合式算法。但因引入旋转变换和镜 像变换后，整个解的搜索空间将变得异常庞大，要想在有限的机器时间内找 到精确的最优解将是非常困难的 国内就下料问题研究与国外相比，无论是在深度和广度方面都有较大的 差距，近些年，关于不规则下料问题的研究和开发比较活跃，但研究带残损 原材料的二维优化下料问题尚不多见，本文选取带残损原材料的二维优化下 料这一贴近实际且具有重大经济意义的课题。 1 3 3 二维不规则物体下料的主要方法 迄今为止，已有许多算法用于解决不同的排样问题f ”】，总结国内外学者 的研究，对不规则物体下料的研究思路主要有； ( 1 ) 矩形下料法【6 7 1 5 ，1 日这是最原始的不规则物体下料的方法。首先将 下料件进行最小包络矩形转换，然后采用动态规划法对矩形进行最优排放， 等排定之后，再恢复其原形为使利用率更高，可进行空余块填充，空余块 ， 山东大学硕士学位论文 是指最小包络矩形与实际下料件之间的差余 ( 2 ) 对少数不规则图形进行靠接排样，然后再采用( 1 ) 中方法处理。 ( 3 ) 不进行包络，直接对原始图形采用填充方法排样，即在原材料上依 次放入下料件，对下料件多边形直接判交和碰撞来实现排样。 采用前两种方法的优点是：下料过程中判交和碰撞问题的复杂度与二维 规则物体的下料问题是一致的，只是增加了图形的预处理过程，即图形的矩 形包络和少数多边形的靠接拼图；还有就是对包络后的矩形排样过程中需要 描述的顶点信息大大减少，同时由于放置矩形时只需考虑水平和垂直两个方 向，减少了图形旋转带来的复杂度，使整个系统的计算时间和计算量都有所 减少【l7 1 采用前两种方法虽然能够保证较快的下料速度，但却导致了材料的利用 率降低，尤其下料件之间具有互补性时，其缺点更为突出如图卜1 所示 图1 - 1 具有互补性图形的包络矩形 采用第三种方法虽然图形的描述复杂，图形的判交、定位等问题也较难 解决，但可以克服前两种方法的不足，取得较为理想的利用率。对图形的判 交、定位过程目前主要有以下几种思路： ( 1 ) 判交分离算法：首先将两个图形放置成相交状态，再通过重叠检 验将两图形逐步分离，文献 1 4 1 就是采用的这种方法 ( 2 ) 判距一碰靠算法：对两分离的图形计算其间的平移间距，按一定的 精度要求将两图形逐步靠接在一起。如常见的b l ( b o t t o m l e f t ) 策略、下台 阶算法等1 ”1 1 。 ( 3 ) 临界多边形算法僻- 2 4 1 ：就是将待排下料件口不改变方向地靠接但 不重叠已排区域( 多边形) a 绕行一圈，b 的一个固定顶点所形成的轨迹叫 临界多边形，排放的最佳位置位于临界多边形上 上述的方法中，前两种方法相比较而言，判交一分离算法比判距一碰靠 6 l i f l e l l l ， 山东大学硕士学位论文 算法多了一个判交过程，但在填充孔洞时却具有优势而临界多边形法虽然 确立了求取4 、b 间最佳位置的基本原则，但彳、b 中只要有一个是凹多边形， 在绕行时就会出现重叠现象，因此，每移动一步都要作重叠检验，同时，在 移动中，步长的确定也是该方法的关键技术所在另外，在临界多边形算法 中口沿彳绕行过程中的靠接还需采用判距一碰靠算法。 综上所述，本文在实现带残损原材料的二维下料的过程中尝试将判交一 分离算法和判距一碰靠算法相结合，给出一种基于左下角策略的快速定位启 发式算法( 见本文4 2 2 ) ，并对算法中的多边形重叠检验和移动步长进行改 进，缩短了布局时间，取得了较为满意的结果。 1 4 本文的主要研究内容 本文研究的主要目的是用现代优化方法来求解带残损原材料的二维下料 问题，并设计一个实用的应用软件。主要内容包括以下部分： ( 1 ) 根据对下料问题的分析，构建自动优化下料系统结构。并对自动布 局过程中的平移、旋转、判交等关键技术进行研究。 ( 2 ) 总结国内外学者对下料问题求解的技术思想，选择合适的优化算法。 本文从应用的角度对遗传算法和模拟退火算法做了认真的分析和研究，然后 将遗传模拟退火算法应用于二维下料问题中，给出了遗传算法求解的编码方 法、适应度函数的定义、遗传算子及运行参数等，并将模拟退火作为个体的 选择策略，产生一最优下料顺序和每一下料件的角度，然后用启发式算法来 定位。 ( 3 ) 确定布局方案，设计自动下料系统多边形的判交和定位是算法实 现的关键，在布局方案中，本文的工作重点放在了当在带有残损的原材料上 放置下料件时，如何缩小被尝试的碰靠次数，提高每次的碰靠速度上给出 了“最小最大测试”和逐边求交的二次判交法、基于左下角策略的快速定位 启发式算法，并给出系统流程，该算法有效缩短了多边形的重叠判定时间， 减少了平移次数 ( 4 ) 系统的实现在w m d o w s 平台下，用m a t l a b 应用软件开发出自动 下料系统，验证本文提出的优化思想的可行性和理论上的正确性 7 、llt，j 山东大学硕士学位论文 本课题所解决的关键问题： ( 1 ) 对遗传算法进行改进，提高下料效率。 ( 2 ) 对底左下角布局方案进行简化，缩短了自动布局的时间 ( 3 ) 自动布局过程中，加入残损的识别及判交，从而实现了带残损原材 料的二维优化下料技术。 ( 4 ) 在w i n d o w s 2 0 0 0 平台下，用m a t l a b 应用软件实现了图形的读取和 显示以及基于遗传模拟退火算法的自动下料系统。 1 5 论文的内容组织 第2 章首先介绍自动布局系统结构，然后对下料件多边形和残损多边形 的图形表示、数据的读取进行描述，并对下料过程中图形的移动、判交等关 键技术进行分析。 第3 章介绍了遗传算法和模拟退火算法，指出各自在解决优化下料问题 中的优缺点，理论上证明遗传模拟退火算法用于二维不规则形状优化下料的 可行性。 第4 章对底左下角布局方案进行简化，基于遗传模拟退火算法，给出了 带残损原材料的二维不规则形状的下料方案，并用m a t l a b 应用软件实现之。 第5 章对本文的工作进行总结并分析存在的问题及下一步研究工作 8 ，ili 山东大学硕士学位论文 第2 章优化下料系统图像处理技术 2 1优化下料系统的构成 优化下料所需解决的问题是如何确定各下料件的排放位置及方向( 角度) 以获得最大的材料利用率。对问题进行深入的研究和分析后认为，要设计一 个优化下料系统，需解决以下一系列问题。 ( 1 ) 原材料形状的获取 在一般的下料系统中( 如玻璃、钢板、布料等) ，原材料的形状是矩形， 所要知道的只是原材料的长度厶宽度矿和数量 i 这些可以通过人机交互界 面获取信息。而在一些特殊行业( 如皮革加工) 中，原材料是不规则形状， 则需对每张原材料进行逐张拍摄形成数字信息，提取轮廓形状。 ( 2 ) 标注残损 在进行下料件的排样之前，应该首先在原材料表面标明残损位置残损 可分为线性残损、面形残损和聚集形残损，如图2 一l 所示。对于线形残损， 可以用最小包络矩形来标识；对于面形残损，其外轮廓要么是一整条曲线， 要么是若干直线和曲线首尾相连构成的封闭二维曲线，将曲线按一定的精度 离散成直线，构成残损多边形即可。聚集型残损是指在原材料的局部存在的 多个残损距离较近，这时若仍将每个残损单独标识，则会出现“出力不讨好” 的现象，可以将多个残损包含于一个多边型结构内。需注意的是标记残损应 力求准确，既不扩大又不缩小残损面积，以免影响产品质量或造成浪费。 线型残损 面型残损 图2 l 残损类型 聚集型残损 9 山东大学硕士学位论文 ( 3 ) 下料件信息的输入及读取 下料件信息的输入包括下料件特征量的输入和下料件几何图形的输入， 下料件的特征包括种类、个数、顶点数等通过人机交互界面输入，下料件图 形的输入通过绘图工具a u t o c a d 实现，并以d x f 格式的文件输出，系统 读取该d x f 格式文件获得图像数据，并进一步建立图像数据库。 ( 4 ) 自动布局 在获得原材料形状、数量，下料件的数据信息、标记残损之后就可进行 自动布局了，这一过程包括对图形信息的分析计算以及优化计算的各个过程。 也是优化下料问题中最重要的步骤。 ( 5 ) 结果输出 排样结果输出主要完成排样结果的图形输出以及排样结果的一些具体参 数的输出，以便对结果进行分析和指导生产 综上所述，带残损原材料的二维不规则多边形优化下料系统的构成如图 2 2 所示 f 可二蠹 标注残损 自动布局 结果输出 a u t o c a d 接口 交互式输入 自动布局 人工干涉 图形输出 参数输出 图2 - 2 优化下料系统结构图 2 2 图形数据处理的关键问题分析 本文采用一种基于遗传算法和模拟退火算法的混合启发式算法，通过改 进的遗传算法给出一最佳的排样次序和角度，并在遗传算法中运用模拟退火 算法作为个体的选择策略，进一步调整优化解 2 y l ，然后通过启发式底左顺序 1 0 ，fl，kr 山东大学硕士学位论文 将下料件一一放置到原材料上，实现自动布局。在自动布局过程中，多边形 的平移、旋转、判交等是基本操作，也是关键技术所在，下面就一些关键问 题进行剖析。 2 2 1 下料件及残损多边形的表示 不规则形状的下料件和残损处的形状均可用多边形来描述。在这里有两 个问题需说明一下：一是实际的下料件和残损的轮廓要么是一整条曲线，要 么是若干直线和曲线首尾相连构成的封闭二维曲线，我们将曲线按一定的精 度离散成直线；二是原材料上的残损可以视为已确定好位置和角度的特殊下 料件，并建立残损数据库( 见本论文4 3 节) 。 下料件轮廓的离散化：为了方便计算机处理，需要对下料件轮廓中的圆 和圆弧进行离散化处理，用多个小的直线段来拟合下料件轮廓，进而以多边 形来逼近下料件的实际外形。逼近多边形应该包含原下料件，还应该把下料 件外形上的一些小凹槽除去( 如图2 3 所示) ，使下料件外形尽量简化，有效 地减少系统的处理时间。 图2 - 3f 料件轮廓的离散化 多边形采用参照点法来表示 2 6 j ，方法是选定多边形上最左最下的一个顶 点为参照点，其坐标为( o ，o ) ，多边形上其余顶点取相对于参照点的坐标值， 然后从参照点出发，以逆时针方向顺序通过多边形上的每一个顶点，则获得 的顶点序列就表示了多边形。例如，图2 - 4 中多边形a 可以用顶点序列 a i ， a 2 ，a 3 ，a 4 ，a 5 ，a 6 ，a 7 ，a s 表示。 山东大学硕士学位论文 多边形a 的顶点序列坐标为： ( o ，o ) ( 勉，船) ( x 3 ，y 3 ) ( x s ，y s ) 2 2 2 坐标变换 t f 其中五、4 分别为图形在x 轴和y 轴方向的平移增量 点( 工，j ，) 在x 轴和y 轴方向的平移增量反、西后点的坐标为( 对喀，p 西) 。 卜1 | o l o | _ l 2 03 0i j y x i y i y 2 x ，y j x 4 y x ，矾。 x 6 y 6 x 7 。y 7 ) 【i y 图2 - 5 平移变换 点m缸舢舢舢缸肿舢 ，：=n=：=：=：= o 池池；=暑=乏；乏点m舡如舢舢舢舢舢 山东大学硕士学位论文 2 旋转 旋转是指每个下料件多边形以其参考点为中心旋转a 角，逆时针为正， 顺时针为负( 如图2 6 ) 。 产生旋转的变换矩阵阱1 是 t 俨r ic誓oscts i n a 锢 一 即：多边形上任一顶点( 工，y ) 绕其参考点旋转0 角后的点坐标变换为： 2 2 3 多边形的重叠性检验 多边形的判交是指在有残损多边形的原材料上，判断待排放下料件与残 损之间、以及待排放下料件与已定位好的下料件之间是否重叠的问题，是自 动布局中的关键技术，贯穿整个排样过程始终，直接影响着系统的运行速度。 国内外不少学者在这方面进行深入的研究，提出了一些有效的判别方法 1 逐边求交测试【2 6 】 逐边求交也就是对两多边形的各个边分别两两判交，是多边形判交中最 基本、最常用的方法。 设线段f i 、f 2 分别是多边形一和曰的两条边，f i 的两端点坐标为( 却，y 1 ) 和( x 2 ，此) ，1 2 的两端点坐标分别为( x 3 ， ) 和( x 4 ，y 4 ) ，如图2 7 ( a ) 所示。我们首先判线段f l 和f 2 的延长直线是否相交，若直线不相交，则两线 段必不相交，若直线相交，再进一步判断交点位置是在线段上还是在线段延 山东大学硕士学位论文 长线上。 ( a ) ( b ) 图2 7 ( a ) 两线段判交示意图( b ) 参数蜥，的含义示意图 设两参数阶v t 分别为两直线的参数，含义如图2 7 ( b ) 所示： l 、：工f = x l + ( x 2 一工i ) u l y i = y i + ( y2 一y i ) 嘶 k ：x i = x 3 + ( x 4 - x j ) v t y l = y3 + ( y4 - - y 3 ) v t 解方程组得 。产q ! = 丝2 垒二兰2 二垒! = 兰2 坐! = 丝2 ( y 2 一y 1 ) ( 而一x 4 ) 一( y 一y 3 ) ( x l x 2 ) ，栌q 2 二苎2 垒i 二兰2 二垒；：墨2 业i 二苎! 2 一y 。) ( 与一毛) 一o 一乃) ( 一j 2 ) 当幻- y 1 ) ( x 3 一x 4 ) 一( n y 3 ) ( x l x 2 ) o 时，直线f l 和f 2 有交点。 根据u i 和的含义，进一步判定： u l 和v f 均在开区间( o ，1 ) 时，交点在两线段上，两多边形重叠；u t 和 均至少有一个等于0 或等于1 时，交点处于线段的端点，不能证明两多边形 重叠；其余情况为线段l 。和f 2 不相交( 交点在线段的延长线上) 。 当劬- y 1 ) ( x 3 一x 4 ) 一触一y 3 ) 0 广x 2 ) = 0 时，直线f l 和, 3 z 行或重合。 此时用点包含性测试来判两多边形是否重叠。即分别测试点( x j ，如) ( x 2 ， 妮) 是否在多边形b 内以及点q 3 ，y 3 ) 和( 工4 ，y 4 ) 是否在多边形4 内。 采用射线交点数算法：先从该点引出一条射线，该射线与多边形相交， 若交点为偶数，则该点在多边形外，若交点为奇数，该点在多边形内需要 1 4 山东大学硕士学位论文 考虑的特殊情况是：如果多边形的一条边位于射线上或射线过多边形的顶点， 对于这种奇异情况，作如下处理：规定引出的射线与x 轴平行，当与射线有 交点的边( 线段) 在射线上方时，交点加1 ；当与射线有交点的边( 线段) 在射线下方时，交点数为o ；当边与射线重合时，交点也计为o 。 2 图像扫描 图像扫描就是以一定精度的水平( 或垂直) 扫描线顺序扫描多边形区域， 计算扫描线与多边形各边的交点并对交点个数进行分析，找到每条扫描线上 能代表图像区间的一对交点，这样每个扫描区间实际上是由一对x 坐标值构 成，通过比较工坐标值很容易判断两个扫描区间是否有重叠部分。这种方法 对原材料和下料件的形状没有任何要求，具有一般性，但扫描线与多边形交 点的分析与配对均较复杂，计算量大，对于较大规模的下料系统，影响下料 速度。 3 栅格检索 受a u t o c a d 和p r o t e l 等软件的启发，在图形重叠性检验时，还可以采用 栅格检索的方法。该方法的主要思想是：根据原材料实际使用的精度，用一 定间距的栅格来分别包围原材料和下料件图形，定义没有布局的原材料区域 的栅格元素为o ，而已定位好的下料件处的栅格元素为非o ，通过检索栅格中 是否有重复的图像元素( 非0 元素) 来判别图像是否重叠。该种方法中图像 信息可通过数字化仪器直接获取 以上介绍的几种方法各有所长，根据现有的实验设备，本文在实验中采 用了第1 种方法。同时，为了缩短判交时间，在判断多边形两两之间是否存 在重叠时，本文尝试采用了二次检验法：先用“最小最大测试法” 2 7 1 将多边 形进行极值包络矩形，利用矩形进行重叠性初判，如果两个多边形的包络矩 形不发生重叠，则两多边形肯定不重叠；当两个多边形的包络矩形发生重叠 时，再用多边形逐边求交的方法进行二次判断。 最小最大测试：也叫重叠测试或边界盒测试。这种测试提供了一个快速 方法来判别两个多边形不重叠，方法如下： 找到每个多边形的极值( 最大和最小的x ，y 值) 。然后分别用矩形去外 接每一个多边形( 如图2 8 所示) ，接着检查在工和y 方向两个矩形是否相交， 山东大学硕士学位论文 如果不相交，则相应的多边形不重叠( 见图2 - 9 a ) 。此时，必定有如下4 个不 等式中的一个得到满足，设两个多边形分别为和b ，即 x a m a z x b r a i n ；x a m o l x 触 蚴册群胁1 鲫；y