（通信与信息系统专业论文）面向玻璃切割机的排样优化算法设计与实现.pdf

武汉理工大学硕士学位论文 摘要 计算机自动排料技术的不断发展为很多排样优化领域带来了效益，面向玻 璃切割机的排样优化正是二维图形排样的一个应用分支。二维图形的排样是一 个n p 完全问题，它有较高的计算复杂度，这对面向玻璃切割机的排样优化带来 了一定的挑战算法必须具备可行性。针对排样领域的特定需求，本文从研 究几个核心算法着手，分别探索并设计了矩形件和非规则件的排样优化算法。 对于矩形件的排样，本文分别对贪心算法和最低水平线算法进行改进、设 计与m a t l a b 仿真，实现了改进的贪心算法和基于最低水平线的组合算法，经过性 能测试、比较与分析，得出改进的贪心算法可以获得很高的排样利用率，并且 它的耗时性能具有较大的改进空间：基于最低水平线的组合算法能有效改善最 低水平线算法的中心空白区域，可以作为进一步研究并改进最低水平线算法的 新渠道。结合面向玻璃切割机的排样需求，本文选择了贪心算法用于实际排样， 在此基础上，对改进的贪心算法进行策略性的两次改进与v c 实现。v c 实现的第 一个改进贪心算法即第二次改进的贪心算法，主要是对算法的外部控制进行改 进，通过测试数据的验证、比较与分析，证实改进后的贪心算法相对于第一次 仿真时的改进在排样时间上稍有改善，可以保证排样结果的紧密度，获得较高 的排样利用率，适用于种类较多、尺寸相对于板材不大的中等数量规模的矩形 玻璃件排样优化：v c 实现的第二个改进贪心算法即基于条料的贪心算法，是针 对第二次改进的贪心算法而做的进一步改进，它采用条料思想减少了占角对象， 从根本上有效改善排样时间，通过测试数据的验证、比较与分析，证实它在排 样时间上大为改善，适用于大规模的矩形玻璃件排样优化。 对于非规则图形的排样，本文从描述图形形状的数学理论着手，自设靠接 规则，将最低水平线算法运用于非规则图形排样领域，通过对算法数据结构、 主要模块以及总体流程的设计实现了基于最低水平线的靠接算法，通过测试数 据的排样显示证实该算法可以实现快速排样，且利用率也较满意，可以运用于 面向玻璃切割机的排样优化领域。 关键词：二维排样，玻璃切割机，可行性，矩形件，非规则件 武汉理工大学硕士学位论文 a b s t r a c t c o n t i n u o u sd e v e l o p m e n to ft h ea u t o m a t i cd i s c h a r g et e c h n o l o g yo fc o m p u t e rh a s m a d eal a r g en u m b e ro fb e n e f i t sf o rm a n ya r e a so f l a y o u t l a y o u to p t i m i z a t i o nb a s e d o ng l a s sc u t t i n gm a c h i n e si sj u s to n eo ft h e m t h el a y o u to ft w o - d i m e n s i o n a lg r a p h i c s i sa l ln pc o m p l e t ep r o b l e m ，i th a sah i g h e rc o m p u t a t i o n a lc o m p l e x i t ya n di tw i l lb e c e r t a i n l yb r i n gag r e a tc h a l l e n g et ot h el a y o u ta l g o r i t h m sb a s e do ng l a s sc u t t i n g m a c h i n e sw h i c hc a l lf o rp r a c t i c a b i l i t y f o rt h en e e d so fs p e c i f i ca r e a , t h i sp a p e rs t a r t 5 谢t l ls o m ec o r ea l g o r i t h m s a f t e rh a v i n gs t u d i e df u r t h e ro ft h e m ，id e s i g na l g o r i t h m s f o rr e c t a n g u l a rp a r t sa n di r r e g u l a rp a r t sr e s p e c t i v e l y f o rr e c t a n g u l a rp a n s ，t h i sp a p e r f i r s t l ym a k e ss o m ei m p r o v e m e n t sf o rt h eg r e e d y a l g o r i t h ma n dt h ea l g o r i t h mo nt h eb a s i so f t h el o w e s th o r i z o n t a ll i n e ，a n dt h e nm a k e s ad e s i g n a t i o no ft h e mr e s p e c t i v e l y , t h r o u g hm a t l a bs i m u l a t i o n sa n dc o m p a r i s o n sa s w e l la sa n a l y s i sif m dt h a tt h eg r e e d ya l g o r i t h mc a nm a k ea v e r yh i g hu t i l i z a t i o nr a t e a n di th a sag r e a tp o t e n t i a lt o i m p r o v ei t sp r o p e r t yo ft i m ec o m u m i n g ，t h e c o m b i n a t i o na l g o r i t h mo nt h e b a s i so ft h el o w e s th o r i z o n t a ll i n ec a ne f f e c t i v e l y i m p r o v et h eb l a n ka r e a sw h i c hh a v en o tb e e no c c u p i e da n di tc a nb ec h o s e na san e w i d e at oi m p r o v et h ea l g o r i t h mo nt h eb a s i so ft h el o w e s th o r i z o n t a ll i n e a c c o r d i n gt o t h er e q u i r e m e n t so ft h es p e c i f i ca r e a , ic h o o s et h ei m p r o v e dg r e e d ya l g o r i t h ma st h e o n et op u ti n t o p r a c t i c e a f t e rt h a t l c o n t i n u a l l ym a k i n gi m p r o v e m e n t sf o r t h e i m p r o v e dg r e e d ya l g o r i t h mt w i c ea n dm a k es o m ec o m p a r i s o n s t h el a y o u to fr e s u l t s f r o mt e s td a t a st h r o u g hv c p r o v et h a tt h ef i r s to n ei sb e t t e rt h a nt h eo n ed o n ei nt h e m a t l a bs i m u l a t i o n si n d e e d ，a n di tf i t sm e d i u ms c a l er e c t a n g u l a rp a r t sw h i c ha r ei n m a n yd i f f e r e n tk i n d sa n dt h ed i m e n s i o no f e a c ho n ei sn o tr e l a t i v e l yl a r g et ot h e s h e e t s ，w h i c hc a nm a k e 涨ab e t t e ru t i l i z a t i o n ；t h es e c o n do n em a k e saf u r t h e r i m p r o v e m e n tw h i c ht a k ea d v a n t a g e so ft h ei d e ao fs t r i p st h a tr e d u c e st h eo b j e c t st o o c c u p yc o m e r sa n dr e d u c e st h et i m ef o rl a y o u t ，w h i c hf i t sal a r g e rs c a l e a l lt h e r e s u l t sa b o v ec o n f i r mt h a tw ec a na p p l yb o t l lo ft h e mt ot h el a y o u tb a s e do ng l a s s c u t t i n gm a c h i n e s f o ri r r e g u l a rp a r t s ，is t a r tw i t ht h ed e s c r i p t i o no fi r r e g u l a rg r a p h i c s ，s e tc o l l i s i o n n 武汉理工大学硕士学位论文 r u l e sm y s e l f , a n da p p l yt h ei d e ao fl o w e s th o r i z o n t a ll i n et ot h ea r e ao fi r r e g u l a rp a r t s a f t e rt h ed e s i g n i n go fd a t as t r u c t u r e sa n dt h em a i nm o d u l e sa sw e l la st h eo v e r a l l f l o wc h a r to ft h ea l g o r i t h m ，if u l f i l lt h ec o l l i s i o na l g o r i t h mo nt h eb a s i so ft h el o w e s t h o r i z o n t a ll i n et h r o u g hv c ，t h er e s u l t ss h o wt h a tt h i sa l g o r i t h ms u i t sf o rr a p i d p a c k i n ga n dt h eu t i l i z a t i o ni ss a t i s f i e d ，w h i c hc a n b ep u ti n t op r a c t i c e k e y w o r d s ：t w o - d i m e n s i o n a ll a y o u t , g l a s sc u t t i n gm a c h i n e s ，p r a c t i c a b i l i t y ， r e c t a n g u l a rp a r t s ，i r r e g u l a rp a r t s 武汉理工大学硕士学位论文 第1 章绪论 1 1 课题来源、研究背景及意义 本文课题是与广东省某企业合作项目“玻璃切割机排样系统的研发 工作 的一部分。 玻璃排样是玻璃切割的一个重要分支，是一种经典的组合优化问题。玻璃 样件的排样算法属于二维零件的排样算法范畴，这种排样技术可以从其他领域 获得灵感，如：用于服装行业的不同形状布料的排布、制鞋行业加工所用的不 同形状鞋料样件的排布等，它们具有互通性，然而面向玻璃切割机的优化排样 也有其自身具备的特点，这主要体现在玻璃零件的形状上、数量规模上、排布 方式上。此外，本课题的研究具有一定的技术背景，在现有成熟的研究中，二 维图形排样技术主要还是体现在矩形样件的排放上，直到近些年，学者们才逐 渐将注意力转向到非规则图形的排样研究中来，然而一个个现实问题不断产生， 如：二维非规则图形排样时所需处理的数据量较为庞大，尽管计算机的计算和 处理能力随着硬盘和内存的容量不断加大而提高，但数据的处理能力始终不理 想，只有继续研究算法，在算法本身上来下大功夫；或是零件排样利用率始终 不理想，达不到技术指标；或是排样所耗时间太长，无法满足生产加工厂商的 需求，甚至还不及人工排样，若干问题的出现让我们不得不有针对性地进 行相应研究，力求将问题得到进一步改善，达到生产厂家的应用需求。 二维图形排样问题可以描述为在一定尺寸的板材上，让若干待排样件按照 一定的规则摆放在该板材上，使其满足： ( 1 ) 待排样件互不重合： ( 2 ) 待排样件摆放在板材范围内，即不超出板材尺寸。 为了满足工业上的成本需求，我们要尽可能地提高板材的利用率；为了使 那些对时间需求有一定限制的企业满意，我们需要尽可能地缩短排样所耗时间。 一般的，现在对二维图形样件排样的衡量标准有以下几种： ( 1 ) 在底边宽度一定，而高度不限的板材上，希望排样结果的高度越小越 好； ( 2 ) 在板材长、宽均限定的板材上，希望排样所需的板材数目越小越好； 武汉理工大学硕士学位论文 ( 3 ) 在板材长、宽均限定的板材上，希望排样结果显示的每块板材的利用 率越高越好，或平均利用率越高越好； ( 4 ) 在一定尺寸的板材上排样，在利用率较高的情况下，使得排样所耗时 间越少越好。 玻璃切割机的切割部分由切割平台与翻转平台两个部分构成。切割平台是 一个三轴联动系统，三轴是指x 轴方向的由电机来驱动的横梁、y 轴方向的由 电机来驱动的刀架以及z 轴方向由电机驱动的刀头。翻转平台主要完成自动取 料、送料的工作。切割刀头通常具有一定的长度，它通过x 轴和y 轴两方向运 动的配合形成所需要的轨迹进行切割。 玻璃切割的原料是矩形，长宽大约处于1 0 0 0 m m 到1 0 0 0 0 m m 的范围内，绝 大多数待切玻璃的边长处于l o o m m 到8 0 0 m m 之间。待切玻璃的种类往往各不 相同，每种数量不一且尺寸通常以毫米为单位。很多情况下，一块玻璃原料不 可能排下所有玻璃样件，因此往往最后所需的玻璃原件数量不定，对此，具体 需要多少块某种尺寸的原件，需要通过算法计算出来。此外，玻璃样件的切割 方法也不尽一样，但玻璃的切割尽量满足“一刀切 的条件。所谓“一刀切 ， 即在一块矩形板材区域中，切割出一条直线的轨迹，将玻璃分割成两块。“一刀 切一在玻璃切割生产中比较重要，这主要是由于在玻璃是一种脆性材料且切割 后有一道工序叫掰片，即最后所谓的“切开 ，这是在切割后用一种力量将玻璃 件掰成两片。因此待掰开的两个区域之间的分割线必须是一条直线，因为如果 出现拐角，那么在掰片的时候，拐角处可能因为力量的作用而断裂。 面向玻璃切割机的图形样件排样具有其自身的特点。其一，面向玻璃切割 机的排样图形具有定的规则性；其二，面向玻璃切割机的排样图形数量规模 较庞大；其三，面向玻璃切割机的图形排样，希望尽可能地减少排样所耗时间； 其四，面向玻璃切割机的图形排样算法，不同于大多数定宽不限高而力求最小 高度的算法，它需要给出每种尺寸的玻璃板材使用的数目；其五，面向玻璃切 割机的图形排样算法要求所有板材的平均利用率尽可能高。针对以上的需求， 本论文的算法需要符合适应大规模排样、利用率较高、耗时较少的的原则。 研究意义在于：首先，玻璃排样布局问题的思想可以推广到很多领域，如 机械制造、航空航天、道路交通运输、服装行业、建筑设计、城市规划、电子 工业及医疗器械等，它的扩展性很强，具有极广泛的应用性，因此研究价值不 可小觑。此外，生产排样作为工业生产的重要一环，在工程实践中往往依靠人 工进行，伴随着计算机自动排样技术的出现，各生产加工装配企业的生产效率 2 武汉理工大学硕士学位论文 得到了大幅度的提高，有效地推进了两型社会的建设，然而装配企业的生产加 工规模不断扩大，现有的排样技术亟需得到进一步发展，来满足其日益增长的 需求。因此，实现对任意样件的更高利用率的排放，可以帮助生产企业降低原 材料成本、节约排样所耗时间，进而提高生产厂家的生产效率，有助于形成一 条完善的高质量生产加工链。 1 2 相关领域国内外研究现状 1 2 1 二维矩形样件排样的国内外研究现状 矩形排样的研究较早就提出来了，而国外的起步也相对更早。这种优化排 样问题( o p t i m i z a t i o nl a y o u tp r o b l e m ) 属于一种经典的n p 完全( 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 lc o m p l e t e ，n p c ) 问题，即该问题无法找到一个多项式的解决办法。 对于这类问题，求解的计算量往往随着问题规模的递增而逐渐加大，进而导致 耗费的时间和费用不尽如人意，在没有标答的情况下，多种算法应运而生，各 有优劣，对算法的改进也均具有一定的广阔发展空间，这也正是研究优化排样 问题经久不衰的原因。 国外于上世纪8 0 年代( 1 9 8 8 年) ，在p a r i se u r o t i m s 国际会议上就专门 成立了下料问题兴趣小组e s i c u p ( e u r os p e c i a li n t e r e s tg r o u po nc u t t i n ga n d p a c k i n g ) ，定期举办对下料问题进行集中探讨和相互学习的会议。在早期，国外 对矩形件的排样主要采用的方法是启发式算法和数学规划法【l 】。数学规划法可分 为线性规划【2 1 、整数规划【3 1 、动态规划【4 】和整数线性规划5 1 这几类。但是这些方 法有一个重大局限：它不适合数量规模较大的矩形样件排样，因为随着矩形件 数目的逐渐变大，计算量将呈指数级增长。之后出现了启发式算法，它针对数 学规划法的缺点，不再寻求最优解，而是力求在可接受的时间范围内寻求问题 的近优解。a l b a n o 与o r s i n i 提出了基于树搜索的启发式搜索方法，适用于正交 切割形式的矩形排样问题，达到了近优的效果【6 】。y a n a s e e 与z i n o b e r 提出了一种 基于排样次序的启发式算法，其次序是依据排样矩形的某种特性的优先级规则， 如矩形长、宽或者面积等，确定次序后再依次序排样【7 l 。启发式算法具有一定的 灵活性，可以为不同的场合量身制定其约束条件，故在优化排样领域起着重要 作用。随着研究的不断深入，上世纪末随着智能算法如：模拟退火算法、遗传 算法、蚁群算法、禁忌搜索算法、神经网络算法等的出现和不断成熟，这些智 3 武汉理工大学硕士学位论文 能算法也逐渐应用于矩形件的优化排样中来，这主要是以与经典启发式算法相 融合的形式出现。s e g e n r i e c h 和b r a g a 对遗传算法的使用让矩形件的优化排样得 到了较好的解决，这种遗传算法将待排列的若干矩形件依次编号，将排样问题 转变为数字串的选择、交叉、变异操作，进而完成对矩形件的排放瞵j 。j a c k o b s 提出将遗传算法与经典的b l ( b o t t o m l e f t c o n d i t i o n ) 算法相结合，是启发式算 法的创新，但产生了较多的空白区域【9 】。针对b l 算法的中心空白区域，h o p p e r 和t u r t o n 提出b l f ( b l f i l l i n g ) 算法，可以对空白区域进行有效填充，较b l 算法在利用率上改善了很多【l o j 。f a i n a 将模拟退火算法引入解决了适于一刀切与 非一刀切的矩形下料排样问题i l l l 。l e u n g 和y u n g 将遗传算法、模拟退火算法与 d p ( d i f f e r e n c ep r o c e s s ) 、b l 算法相结合求解非一刀切的排样问题，并将结果进 行了细致对比【1 2 】。s o k e 和b i n g u l 用遗传算法与模拟退火算法定序并结合改进的 b l 算法摆放规则求解矩形样件的排样下料问题1 1 3 1 。e d m u n dk b u r k e 和m a t t h e w h y d e 等提出了一种新算法电p ( g e n e t i cp r o g r a m m i n g ) 算法，他们将遗传算 法用于具体的定位判断与处理，并与原遗传算法进行对比，显示出新算法具有 绝对的优势1 1 4 j 。 我国对计算机辅助排样的研究起步较晚，对c u t t i n ga n dp a c k i n g 问题的研究 机构主要有华中科技大学c a d 中心、上海交大、浙江大学、四川大学等，对矩形 件的排样多用人工交互的形式实现，算法主要表现为启发式算法、数学规划法 和启发式算法与智能算法相结合的算法。周杰、李军等将深度优先搜索策略引 入到矩形套裁件排样中【”】。刘德全和滕弘飞的改进遗传算法解决了矩形样件的 正交排样问题，该文献提出了下台阶算法( 另一改进的b l 算法) ，将它与遗传 算法相结合起到了很好的效果【1 6 1 。贾志欣、殷国富等率先提出了“最低水平线 算法 ，并将其与模拟退火算法相结合进行零件排放，取得了较好的结果l l7 1 。曹 炬、周济和余俊提出了矩形样件优化排样的背包算法，将二维矩形件排样问题 转化为一维优化问题，构造了一个利用背包问题解决矩形件排样问题的近优模 型【1 3 】。李勇、曹炬等提出了一种满足矩形“一刀切 工艺要求的十字线法，较 有效地兼顾了生产和效率【1 9 】。为了进一步提高生产率，他们又提出了一种将板 材分块的近似算法，减料方便。方仍存、曹炬和陈学松运用求余算法解决了二 维矩形的排样，他们根据板材的长或宽来对各个矩形件的长或宽求余数，根据 余数结果来作为排布依据【2 们。宋连超、朱建良等分析了近似算法的主要缺陷， 提出了最小余料删除法，在同等数据条件下提高了板材利用率【2 1 1 。谢淼和田社 平提出了一个基于二叉树结构的排样方法，二叉树的生长方向由板材利用率决 4 武汉理工大学硕士学位论文 定，通过调整关键因素的权值调节二叉树生长方向，结果显示这种算法的速度 较快、效率较高f 2 2 1 。郭文兰和张彤提出了一种矩形件优化排样的双向双原算法， 首先采取局部最优原则，将板材分为两块，再将分割点设为两待排区域的原点， 最后运用改进的近似算法完成排样，获得了较好的排样结果【2 3 1 。总体说来，国 内现在的主题算法仍以混合式启发算法为主，算法的改进也在不断的发展。 1 2 2 二维非规则样件排样的国内外研究现状 二维非规则图形的排样亦属于n p 完全问题，较之矩形件的排样，它难度更 大。二维非规则图形的排样问题在国外较早提出。首先是a d a m o w i t z 和a l b a n o z 提出的最小包络矩形法，但是采用最小包络矩形来代替异形件的排样，将会对 利用率造成很大的负面影响，因此这种方法比较适用于外形近似矩形的玻璃原 料f 2 4 1 。除了可采用矩形包络以外，d o r i 与b e n b a s s a t 希望能通过其他方式来提 高性能，在1 9 8 4 年他们就尝试了三角形包络、五边形包络和六边形的包络，因 为这些图形在形状上具有一定的相似性，可以实现形状互补、减小未利用区域 从而提高利用率【2 5 1 。1 9 9 1 年，k a r o u p i 与l o f t u s 在对凸多边形的研究中试图尝 试这种包络方法，但效果不大理想【2 6 】。因此包络方法往往不易实现理想排样。 之后有学者在零件的旋转角上进行研究，希望能得到理想的靠接，如l i n 与 h s u 2 7 1 、n e e 2 8 l 等，在此类方法当中，样件按照某一角度逐渐旋转，然后他们计算 出该样件旋转过程中的步长及带宽。待整个过程结束以后，选择排样利用率最 高的那个转角为样件的最终定位转角。但此算法仍具有一定的局限性，因为零 件每次均以固定的角度值作为增量将零件旋转，故求得的最佳利用率可能顶多 是局部近优。因为最佳定位的角度很可能在角度增加时丢失，故此方法不具有 稳定性，很可能在大规模的生产中造成很大的材料损失。之后出现了 n f p ( n o f i t p 0 1 y g o n ，n f p ) 即临界多边形算法，该算法复杂度很高，很多学者 为此进行大量的改进。g o m e sa m 和o l i v e i r aj f 2 9 删、l i uh y 和h ey j 【3 l 】的算法 均基于临界多边形，该方法将两多边形的位置关系转变为求点和图形边线的位 置关系，虽然求解精度较高，但运行时间极长，对有些领域不适用。 我国对二维非规则图形排样的研究可以分为以下几类： ( 1 ) 单一图形的包络近似法：这类近似法通常与一些智能算法或启发式算 法相结合进行处理，首先将图形进行矩形包络，再按照矩形排样法进行排样。 有时在进行包络后，会采取一定的靠接措施，主要方法有判交一分离法、逐点扫 武汉理工大学硕士学位论文 描偏移法和判距一靠接法。如：曹新明、蒋瑞斌将不规则图形的外轮廓曲线离散 化处理，通过离散点求解最小包络矩形，将不规则件转化为矩形件进行排样【3 2 l 。 宋亚男、杨宜民等提出了一种基于位图排样的计算方法，将外包圆、外包矩形 集应用于待排样件的编码来提高匹配速度，对排样图形进行预处理，再进行图 形排样【3 3 1 。曾窕俊和孙英将遗传算法运用进来，提高了板材利用率，但是时间 花费太大【蚓。 ( 2 ) 直接定位排样法：这类方法通常是基于n f p 的启发式算法与智能算法 相结合的算法，或者是n f p 的启发式衍进算法。这种算法思想直接、操作时间 较长、难度也较大，主要体现在n f p 的自适应操作上。n f p 的处理主要有以下三 种方法：移动碰撞法、明可夫斯基矢量和法和多边形凸化分割法。现在的跟多 算法都是对n f p 的改进。如：刘嘉敏、佟德刚和黄有群通过对斜率思想的引进 提出了一种改进的n f p 算法p 5 1 。刘胡瑶和何援军提出了基于轨迹计算的临界多 边形法，降低了临界多边形的时间复杂度【3 引，之后他们又提出了基于重心n f p 的二维不规则排样算法，通过选择重心n f p 中的最低重心位置来给样件定位， 减少了空间的浪判罗n 。李阳、赵华东和杨威将经典b l 算法和遗传算法相结合运 用n f p 的自适应操作对非规则图形直接排样1 3 砌。张德福、陈竞驰等提出了一种 离散临界多边形模型，改进了b u r k e 的单项离散化模型，通过数据证实了新方 法在求解质量和排样时间上的优势【3 9 1 。n f p 思想的衍进算法如：徐彦欣的产生式 规则的非规则图形排样算法，这种算法将非规则图形的排样边界用点序列逆时 针方向表示，结合靠接思想完成排样【4 0 】。胡华的多边形旋转靠接算法通过提取 多边形关于点的单调线族将多边形排样时的旋转靠接转化为部分线族的旋转靠 接，提高了处理速度1 4 。 ( 3 ) 组合图形的矩形包络近似法：这类方法首先将非规则图形直接靠接排 样，让它们的组合尽量接近于矩形，然后运用矩形件的排样方法进行排样。这 种方法可以用到n f p 策略，是( 1 ) 与( 2 ) 的混合方法。与( 2 ) 方法相比，( 3 ) 方法的操作范围明显减小。如：梁利东和叶家伟提出将剩余矩形匹配算法与遗 传算法相结合，将非规则图形先靠接拼凑为近似矩形的形状，再用矩形排样的 思想进行排样【4 2 l 。这种方法还可以将某些相似形状图形进行普通单排、对头双 排和对头单排处理，实现矩形包络。如：黄红兵、蒋望东的“二步法 算法， 他们将其与人机交互处理结合实现二维不规则样件的排样【4 3 1 。贾志欣、李红林 和张美琴的综合优化算法也采取预处理、自动排样、人工交互的方式运用包络 法结合模拟退火思想实现了排样j 。 6 武汉理工大学硕士学位论文 ( 4 ) 基于最小势能原理的不规则零件排样法：该算法是最近由刘城、叶家 玮和胡金鹏提出的，其原理是零件总是会试图通过平移运动与旋转运动来尽量 降低其重心高度，从而排列更加紧凑【4 5 】。此算法不需要计算n f p ，也不需要考虑 “尽量向左 原则，计算时间上有一定的优势。 1 3 论文主要工作和组织结构 现有成熟的排样算法不少，本文在研究若干算法后，针对玻璃切割机的排 样需求，选择了几种算法加以实现，并针对结果与期待的目标对其加以改进， 实现了对矩形样件和非规则样件的优化排样。 首先针对矩形排样选择了贪心算法和最低水平线算法，对贪心算法的“占 角 等思想进行改进，并设计了一种基于最低水平线的组合算法，分别对其进 行m a t l a b 仿真，证实了算法的有效性、分析各自的优缺点；然后针对玻璃切割 机的排样需求选择贪心算法，并对其进行针对性地第二次改进，用v c 6 0 实现， 用算例分析了其可行性和局限性；之后依照其局限提出了优化对策，再次改进 贪心算法，用v c 6 0 实现了基于条料的贪心算法，验证了其可行性和有效性； 最后针对玻璃切割机排样图形的特点设计了非规则图形排样算法，即基于最低 水平线的靠接算法，并用v c 6 0 加以实现，证实了算法的可行性。 本文研究工作，从理论上对贪心算法的思想进行改进，减少了矩形样件排 样所需时间，使之适合大中等规模的排样生产，同时也保证了利用率的要求： 提出了一个研究并改进最低水平线算法的新方向；并针对绝大多数非规则图形 排样算法时间过长的问题，运用最低水平线算法，自设靠接规则，在利用率较 为理想的情况下，减少了数量庞大的非规则图形排样所需时间，且此方法对凹 凸图形均可适用。 本论文的各章节内容安排如下： 第1 章首先主要介绍课题的来源、研究背景及意义；然后简述矩形和非规 则图形样件排样的国内外研究现状；再对面向玻璃切割机的样件排样进行了需 求分析；之后对论文的主要工作和创新点进行了总结；最后给出了论文各章节 的安排； 第2 章首先具体描述二维矩形排样的几种典型算法，并着重描述贪心算法 和最低水平线算法：然后分别对贪心算法和最低水平线算法加以改进，并分别 进行m a t l a b 仿真，通过对算例结果的比较，分析各自优缺点以及它们在面向玻 7 武汉理工大学硕士学位论文 璃切割机的排样应用领域的可行性；再针对仿真时的改进贪心算法在大规模应 用方面的实用性及弊病，对该算法又进行策略性的两次改进，分别加以设计并 用c + + 编程实现；之后通过对算例的结果分析来说明贪心算法的两个改进算法的 可行性范围，结果显示两个改进的算法各适用于不同的场合，基本均可以用于 面向玻璃切割机的大规模生产；最后对本章内容进行归纳总结； 第3 章首先简单描述了二维非规则图形排样问题中的几种常用算法并分析 其在面向玻璃切割机的排样领域的可行性；然后描述计算机应用领域中的非规 则图形若干特点，并对这些特点进行相应的数学理论说明或推导，为后面的算 法实现作准备；再针对面向玻璃切割机的排样这个具体背景，选择了基于最低 水平线的靠接算法进行设计与实现，此过程中对最低水平线算法在非规则图形 排样领域中的应用进行了针对性的改进，并设定了靠接规则；之后通过对算例 结果的比较与分析，验证了算法的可行性；最后对本章内容进行总结； 第4 章先对本文所做的工作进行总结，同时指出算法研究中遇到的问题以 及改进的空间，最后对后续的研究工作进行展望。 8 武汉理工大学硕士学位论文 第2 章改进的二维矩形零件排样的贪心算法 二维矩形零件排样的算法随着近些年研究的深入，可谓是越来越成熟，但 有几个核心的典型算法是开启排样优化算法这扇大门的金钥匙，它们从排样思 想的本质入手，提供了解决这类问题的办法，并留下了广阔的改进发展空间。 本章将会从这些典型算法入手，深入探索面向玻璃切割机的矩形样件排样优化 算法。 2 1 二维矩形排样的相关典型算法 核心的启发式二维矩形排样算法有以下几种：b l t 9 1 ( b o t t o m l e f tc o n d i t i o n ) 算法、下台阶算法( b l 的改进算法) 【1 6 1 、b l f ( b l - f i l l i n g ) 算、法1 1 0 l 、d p ( d i f f e r e n c e p r o c e s s ) 算法【蛔、背包算法【1 8 1 、求余算法 2 0 1 、贪心算法【4 7 】和最低水平线算法f i 刀 等。本节将重点对贪心算法和最低水平线算法进行描述。 2 1 1 贪心算法 贪心算法是一个经典的排样算法，该算法来自中国古时候的一句谚语“金 角银边草肚皮”【4 刀，该算法运用到“占角动作 、矩形块间的距离【4 7 l 、“占穴动 作一、“穴度一、贴边数的思想【4 7 1 。现分别用图2 1 、图2 2 说明这些思想概念的 意义，1 - 4 号为已排矩形件，5 号为待排矩形件。 图2 1 占角动作描述 9 武汉理工大学硕士学位论文 ( a ) d ( b 图2 - 2 矩形块间的距离 ( 1 ) 占角动作：在图2 1 显示了5 号矩形块的7 种定位操作，其中l 、2 、 3 、4 、5 均为占角动作，而6 、7 位置不为占角操作。可以发现，占角动作需要 紧贴两个以上的矩形块的不同方向的边( 包括构成容器的四块矩形块的边) 。因 为位置6 矩形件悬空了，没有紧贴任何一个矩形件，而在位置7 矩形件只贴了 一个矩形边。除了占角，我们还需要合理占角，即需保证在占角的前提下，满 足矩形块件互不重叠且不会超出矩形板材的区间范围，称之为“合理占角动作 。 位置l 、2 、3 、4 、5 均为合理占角动作。 ( 2 ) 矩形件间的距离：即矩形件间的x 、y 方向的无重叠区域的距离之和。 如图2 - 2 ( a ) 距离为0 ，图2 - 2 ( b ) 距离为d ( x 方向为d ，y 方向为0 ，y 方向有重叠 区域) ，图2 - 2 ( c ) 距离为d ，+ d ：( x 、y 方向均无重叠区域) 。 ( 3 ) 占穴动作：占穴动作是在占角的动作的基础上提出来的。即如果某一 矩形件占角，并且还与形成这个角的其他矩形贴边，那么这种占角动作称之为 占穴。在贪心算法中每个矩形件排样时尽可能占穴。仍如图2 1 所示，当5 号矩 形件位于位置2 时，就是一个占穴动作。5 号矩形件除了与形成角的l 号、3 号 矩形件贴边，还与4 号矩形件贴边，所以5 号矩形块在位置2 为占穴动作。 ( 4 ) 穴度：矩形件相互紧密程度的度量。设矩形块a 占角，且a 与形成该 角的矩形件外的其他矩形件间的距离最小值为d 血，则穴度c 。定义为： c 刮- d 炳 q 1 ) 在( 2 1 ) 式中，w 。、l 。分别为矩形件a 的宽和长。 ( 5 ) 贴边数：矩形块的四个边中与其他矩形紧贴的数目。如图2 1 中将矩 形块5 放到位置2 时的贴边数为3 ，如果放到位置5 贴边数则为2 。 贪心算法对某一个矩形件进行占角的选择优先级步骤为： l o 口一 武汉理工大学硕士学位论文 优选穴度最大的合理占角动作，如果这样的占角动作不止一个，转步骤 ； 优选选择贴边数最大的合理占角动作，如果这样的占角动作不止一个， 转步骤； 任选一个合理占角动作。 贪心算法的排样利用率较高，但时间复杂度较大。 2 1 2 最低水平线算法 “最低水平线算法 本世纪初我国学者提出的一个经典算法，它运用每次 排放矩形后得到的最高轮廓线的取值来决定下一个矩形件排放的走向，其思想 是取若干最高水平线轮廓中可以放下该待排矩形的最小( 最低) 水平线来排放， 突破了以往排放的要么左侧偏高要么右侧偏高的弊病，该算法使得排放比较紧 密，且排放速度较快。 该算法的排样思想步骤是： ( d 初始排放时设置最低水平线为板材的下边缘线； 在最低水平线段的最左处放入第一块矩形件，抬高水平线并更新最低水 平线轮廓集，准备下一个矩形块的排放； ( d 若矩形块排放完毕，则排放结束，否则在最低水平线轮廓集中找到高度 最低的那条水平线，若最低水平线有几段，则选择最左边的那条水平线，然后 准备放入待排矩形块，进行下一步骤( a ) ； ( a ) 如果该最低水平线处可以放下该矩形块，则放入矩形块，抬高水平 线并更最低水平线轮廓集，准备排下一个矩形块，转步骤，否则转步骤( b ) ； ( b ) 如果该最低水平线不可以放下该矩形块，则将该水平线抬高，使 其与它左右两边水平线较低的那个高度相等，更新最低水平线集，转步骤。 图2 3 是最低水平线算法的一个简单实例，1 6 号为已排矩形件，7 、8 号为 未排矩形件。 武汉理工大学硕士学位论文 图2 3 最低水平线算法操作实例图 田7 由图2 3 所示，排样顺序为l 、2 、3 、4 、5 、6 、7 、8 ，其中7 由于底边长 度大于a ，无法放在a 处，故a 处的水平线抬高至6 号矩形块的高度，形成如图 灰色所示空白区域( 再无法放于此) ，此时6 号上方轮廓即为最低水平线且可以 放下7 号，所以7 号放于此，当排8 号时，也只有在此时的最低水平线处，即 仍为6 号上方放8 号。其实8 号完全可以放在a 处。 最低水平线算法的排样速度较快，但是有三个缺陷：其一，容易形成中心 空白区域，譬如，如果某一最低水平线，不能排下此矩形块，就会抬高该水平 线，无形中形成一个空白未排区域，而可能该水平线可以放下其他的某些矩形 块，或者将该矩形转动9 0 度也可能可以放下去，所以这是一个弊病；其二，矩 形件间的某些组合也可能无误差或者以较小误差放入该水平线内；其三，由于 最低水平线会随着排样的进行高度越来越大，那么未排区域面积会越积越多， 后面排放的矩形也只能在更高高度的最低水平线内寻求排放空间，无法达到一 个理想的最低高度解。 2 2 贪心算法和最低水平线算法的改进 上一节对相关算法进行了分析，面向玻璃切割机的排样优化，现选择贪心 算法和最低水平线算法，针对贪心算法和最低水平线算法的缺陷，分别对贪心 算法和最低水平线算法从算法本身进行一定的改进。 2 2 1 贪心算法的改进 武汉理工大学硕士学位论文 贪心算法的利用率较高，但是时间复杂度太大，可以从两方面着手改进贪 心算法。其一，从算法需要的计算量上改进算法，即改进算法思想；其二，从 数据结构、外部控制上入手改进算法。 如上节对贪心算法的描述与分析，贪心算法能使得排样结果较为紧密的关 键是在“占角 策略上，现就经典贪心算法的思想步骤做进一步的说明。设有n 个矩形件进行排样，足表示第i 个矩形件，i 初值为1 ，且l isn ，ub c s t 表示 板材的未被利用率，设初值ub c s l = 1 ，用j 表示初始排放方式，j = l 表示初始横排， j = 2 表示初始竖排，初始设置j = l ，经典贪心算法步骤为： 如果j _ 1 ，初始化格局为未排状态，在板材左下角横放第i 个矩形件置， 转步骤q ) ； ( d 如果j = 2 ，初始化格局为未排状态，在板材左下角竖放第i 个矩形件足， 转步骤( d ； ( d 放入后得到新的格局，准备排放下一个矩形件，若矩形件均排放完毕， 则排放结束，转步骤( d ；否则枚举该矩形件在该格局下的所有合理占角，并计 算每一个合理占角的穴度和贴变数，转步骤( d ； ( d 若存在合理占角，则按照占角优先级选择唯一一个占角动作进行排样定 位，转步骤( d ；否则，若不存在合理占角，则不进行该样件的排样，并计算此 时板材的面积未被利用率，记为u ，如果u 2 ，则i = i + l ，j = 1 ，转步骤； ( d 排样结束，输出此时的格局和ub c s t 。 该算法取得了较高的排放利用率，但有三个方面值得我们关注：其一，算 法时间复杂度较大，尤其是当矩形件数量较为庞大时，该算法耗时太多；其二， 当矩形件以种类划分时，如果单纯用矩形件的次序来依次进行占角，则会进行 较多的重复动作，更增加了时间复杂度；其三，该算法设定的板材的高度均采 用最优解的容器高度，基本是一张板材就可以完成所有样件的排样，而在实际 工程中，板材尺寸不定，那么所需的板材数目不止一张，因此需要用算法来确 定需要几张板材，这也是面向玻璃切割机的排样优化应用所必须求得的。 针对以上问题，本节有针对性地从六个方面改进贪心算法。 ( 1 ) 排样控制的改进：经典贪心算法每当遇到一个矩形件不能排时，就停 止了排放，计算此格局下的板材未被利用率，如果该值小于最优未被利用率， 则更新该值为最优未被利用率，记录此时的最佳格局，进而再将格局初始化为 武汉理工大学硕士学位论文 最开始未排时的状态，重新改变左下角排放的对象或原对象的状态( 横放变竖 放) ，重新进行新的尝试，直到全部排完为止。对此可以进行改进，当一个矩形 件不能排时，将其放入链表存储，尝试后面的矩形件的排放，后面的矩形件很 可能存在合理占角，这样可为矩形件的排放增加更多的机会，进而减少搜索时 间。贪心思想改进之一示例图如下图2 _ 4 所示，1 5 号为已排矩形件，6 、7 号为 未排矩形件。 田 i 一 团 图2 - 4 贪心算法思想改进之一示例图 如图2 - 4 所示，按照排样顺序6 号无法放入板材即停止排放，记录最佳格局 并开始将2 号放入左下角的另一轮排放，而7 号在此次排放中完全可以放到图 中阴影部分，在可提供多块板材的情况下，让每一块板材的利用率尽可能的提 高是面向玻璃切割机排样优化的要求。 ( 2 ) “