文献综述
文 献 综 述一、研究背景优化排样应用范围非常广泛, 在工程应用领域中, 型材和棒材下料 、冲裁件排样、玻璃切割、报刊排 版、家具下料、服装裁剪、皮革裁剪 、造船 、车辆和发电设备生产中都存在大量的下料问题.从计算复杂 性理论上, 优化排样问题是具有最高复杂性的 NP 完全问题, 同时其具有几何特性, 对矩形件、异形件排样离不开图形运算, 排样问题至今尚无有效的求解方法.而现实中大量的实际问题又需要在较短的时间内给出可行解, 众多学者对此类问题的研究, 每年都有大量文章发表于管理学科、工程学科、信息和 计算机学科 、数学以及运筹学等不同学科的杂志和会议论文上。
二、国内外研究现状国外研究现状国外有关下料排样问题的研究起步比较早. Kantorovich[ 1] 于 1939 年就提出了一维下料问题;20 世纪 60 年代初, Gilmore 等[ 2-5] 发表了 4 篇著名的文 章, 提出了一维下料方案和二维排样优化问题;70 年 代至今, 众多学者针对排样问题的一个或几个方面提 出算法和解决方案.由于即使是矩形零件在一张板 材上的排放问题也是 NP 完全问题[ 6] , 加上实际的 限制条件问题会更加复杂, 因此排样问题具有多样 性特点, 至今没有通用的标准方法来解决.1988 年, 在 EU RO IX/TIMS XXVIII 国际会议上, 专门成立了下料问题兴趣小组 SICUP国内研究现状与工程应用国内对于排样问题的研究始于 20 世纪 80 年 代, 主要集中在高等院校和研究所. 对冲裁件排样从 20 世纪 80 年代开始研究, 以 华中科技大学、上海交通大学的工作最有代表性, 主要有人机交互法 、边界加密方法和不相交判别法 等[ 7] , 借助人机交互方式进行图形的旋转和平移以 达到优化排样的目的.围绕着冲裁件自动排样, 文 献[ 7-8] 采用将零件处理为多边形的方法或采用 碰撞算法直接对零件进行排样.文献[ 9-10] 对一维下料问题进行求解. 对矩形件 排样 的研 究始 于 20 世 纪 90 年 代[ 11-19] ,主要采用启发式算法, 动态规划、整数规划方法, GA, SA 算法进行求解.文献[ 20] 研究了单一尺寸矩形件的排布, 文献[ 21] 对特定设备下料排样 进行了分析. 近几年来, 国内学者开始对异形件排样问题进行研究[22-35].从算法看, 主要是采用一定规则将异 形件处理为矩形, 按矩形件排样方法进行排放;采用 基于图形运算的移动算法 、碰撞算法, 基于规则、样图的方法、神经网络方法、基于学习的遗传算法等进 行求解 ;文献[ 36] 采用模拟细胞长大自然生成布局 结构的膨胀算法求解矩形空间中等圆的布局问题. 国内学者对于三维排样问题主要采用启发式算 法及遗传算法进行求解.文献[ 37-38] 以八叉树为基础设计启发式算法;文献[ 39] 以相同尺寸的物体 布局为研究对象, 将约束处理加入启发式规则中, 提 出关于约束底盘装载问题的启发式方法;文献 [ 40-41] 采用遗传算法对装箱问题进行求解. 众多学者在研究排样算法的同时也开发了一些排样软件, 从早期的交互排样到自动排样, 排样系统 也在随着排样算法研究的深入而发展.华中科技大 学最早开发了冲裁件排样系统;曹炬推出了一维优化 、矩形件排样 、异形件排样的优化排样系统软件;滕弘飞等对航天器舱布局方案设计, 查建中等对集装箱装运问题进行研究和开发. 与国外相比, 国内关于排样问题的研究无论是在深度上和广度上都有差距, 好在很多学者已经意 识到该问题的研究价值, 目前排样问题已成为国内学者研究的一个热点.三、排样问题的研究趋势尽管人们对排样问题进行了大量研究, 并取得 892 计算机辅助设计与图形学学报 2004 年了一些成果, 但一直没有找到通用的、标准的解决方 法.随着计算机、优化技术的发展, 对排样问题的研 究也在不断深入.针对实际工作中下料排样问题具 有多样性的特点, 目前对排样算法的研究有如下 趋势 :( 1) 多种算法有效综合.随着智能优化算法的 不断发展, 不少学者采用计算机图形学处理方法与 智能优化算法相结合来解决优化排样问题.如何综 合多种算法以及哪些算法在哪一阶段综合, 是排样 问题研究的一个重要方向. ( 2) 多目标、多约束条件.不仅仅限于材料利用 率最高这个单一目标, 结合具体工艺和应用要求, 考虑多种约束条件. ( 3) 从多个角度对排样算法进行研究.在应用 领域对排样问题的研究是寻找合理时间内的最优解 法;在算法分析方面对算法的时间复杂性、空间复杂性进行分析;对算法性能表现方面进行一般情况下 、 最坏情况下解的质量以及适用的问题类型进行研 究;针对不同问题的特点, 如零件的情况( 零件的数 量、零件的长宽比、零件的差异变化比) , 测试和分析算法的性能。
资料编号：[579724]
