摘要：在材料加工领域，板料优化排样是实现薄板和厚板材料充分利用的一个常见问题。该问题是典型的NP完全问题，其求解过程复杂，求解耗时大，难以获得精确解。这不利于该问题的工程应用，为此，目前学术界提出了多种用于解决该问题的近似算法，求取在工程应用中可接受且耗时合理的优化排样方案。该文在对板料排样问题进行阐述的基础上，对近年来国内在板料优化排样问题方面所开展的研究进行了分析，对板料排样问题的发展前景进行了展望。
关键词：优化排样问题；板料优化；算法
中图分类号：TP39文献标识码：A文章编号：1009-3044(2011)20-4983-03
On Plate Nesting Optimization Problem
LI Wei1, LI Jian2
(1.Academic Administration of Guizhou Normal University, Guiyang 550001, China; 2.School of Materials Science and Engineering of Jiangsu University, Zhenjiang 212013, China)
Abstract: Plate nesting optimization problem is a Common problem for sheet and plate materials to achieve full use in the field of material processing. The problem is a typical NP-complete problem. The problem solving process is complex, time-consuming to solve large, difficult to obtain exact solutions. This is not conducive to the problem of engineering applications, for which, for the current academic made a variety of approximation algorithms to solve the problem of strike in the engineering applications and time-consuming reasonably acceptable optimal nesting program. This paper describes the sheet metal nesting problems, analysis of the recent domestic optimal nesting in sheet issues research carried out, and looked to the problem of sheet metal nesting prospects.
Key words: optimal nesting problems; sheet optimization; algorithm
在材料的加工制造中，原材料的规格和目标件规格之间具有复杂的组合关系。加工制造的方案确定首先就是确定出这种组合关系。在传统的情况下，往往通过决策者主观的判断来实现这种组合关系的确定，而其中最简单的方法就是按逐个目标件的需求从全材料上进行取材。由于这种决策过程没有从宏观上对材料的利用效率进行考虑，往往在很大程度上浪费了原材料。为此，需要采用一定的优化方案对原材料进行利用，即采用良好的排样方法，实现节约材料的目标。尤其在某些工艺过程中，材料的成本远高于加工成本，而其中的某些材料是不可重复处理的，因此，排样问题在原材料的剪裁过程中至关重要。
优化排样问题是确定原材料和目标件之间的组合关系得问题，由于原材料与目标件之间关系的复杂性，该问题属于非确定型的多项式算法(Nondeterministic Polynomial, NP)完全问题，计算复杂性高，很难通过精确算法在短时间内对问题进行求解[1]。尤其在问题规模较大时，一般的精确算法已不能满足工程应用的需要。为此，很对针对此问题的不确定算法发展起来了，采用这些算法能够实现较优的排样方案，实现求解时间与优化方案之间的调和。为进一步探索板料排样算法的发展，本文对近年来国内在板料排样问题方面所开展的工作综述，以期明确板料排样问题的发展方向。
1 问题描述
板料排样问题是确定原材料分解成多个目标件的方案，由于在某些情况下排样问题具有一定的约束条件，所以又常根据约束条件将板料排样问题分为一维问题、二维问题、三维问题以及1.5维问题。在工程应用领域，其中的二维板料排样问题应用广泛，其问题的直观描述如图1所示。问题表述为，在长为L宽为W的原材料上对目标件所需的区域进行划分，划分的目标是获取m类的bm个长为lm，宽为wm的目标件。即满足如下条件：
（1）
排样问题在工业领域具有广泛的应用，主要面向板料冲压领域和轻工业中的皮料分割领域。在冲压领域主要开展的工作是研究少无废料冲裁技术[2-6]，这些技术对汽车工业的发展起到一定的推动作用。另外，在其他领域如石料加工和皮料加工中也具有一定的应用，如赵民等人[7]将优化排样应用到石料的优化排样中。在皮料的排样问题中，所需要实现的目前与公式（1）的描述有所差别，其中的原材料是人工从自然界获取的二维形状复杂材料，在原材料上剪裁多边形，需要实现材料的最优利用与多边形边数之间的调和。
2 板料排样问题优化算法
板料排样问题的复杂性决定了求解过程的复杂性，一般情况下很难实现问题的精确求解。目前所采用的求解方案获取的解都是近似解。在不考虑具体算法的情况下，板料排样问题的优化一般包括问题的预处理、问题求解以及问题的后处理等几个步骤，目前的研究主要针对问题的求解算法来开展。
2.1 排样问题的预处理
为了方便问题的求解过程的实现，一般需要对排样问题进行预处理，将原材料和目标件之间的组合关系限制在较小的范围内，方便算法的实现。目前，国内部分学者在排样问题的预处理方面开展了一定的工作，其中包括对初始的零件的预处理、对板材的分割和对零件的拟合等处理过程的研究。对零件的预处理主要从多种零件的组合方式和板材的分割方面进行了考虑。这些工作主要在2000年左右开展，如崔耀东[8]采用组块优化排样法实现多种目标零件的预处理，使多种零件组合首先形成规则的矩形单元，这样有利于零件在原材料上的排布。在板材分割方面，崔耀东等人[9-10]考虑将板材分割为较小的板材，实现在子板材上进行单个目标零件的排样，使排样问题简化。
在排样问题预处理过程中，需要考虑到零件的特征、对待排样零件进行分类以及对零件排样方案进行权重分析等问题。多个课题组在这些方面开展了系列工作。李英华等人[11]对板料排样问题进行了分析，将各种二维几何零件及其排样问题进行了归类，并针对这些归类设计了一套分类码系统，为后续的板料排样问题的求解提供了借鉴。马建等人[12]也对零件的特征进行了考虑，在此基础上提出基于实例(样图)的推理优化方法，设计出了基于这种原理的排样系统结构。张玉萍等人[13-14]采用对皮料的样片进行进行了离散化预处理，减小排样优化过程与皮料和样片的几何信息之间的相关性对计算结果的影响和约束，提高了获取最优结果的可能性。
在工程问题中，由于所面临的板料排样问题可能遇到对复杂多样的零件的排样，这种情况难以采用对矩形件排样的理想方法进行统一处理。在这种情况下，需要对目标零件的轮廓进行拟合，以简化后续的优化过程。一般情况下，所进行的多边形拟合主要把不规则的平面几何图形拟合成平面多边形区域进行处理，最理想的情况是拟合成矩形形状。国内在这方面也开展了大量的工作，曹炬[15]将二维异型件拟合成多边形的基础上对多边形进行了排样优化；赵震等人[16]为了解决图形干涉问题，提出了采用毛坯图形等距放大的算法来对毛坯图形进行预处理。此后王亮申等人[17]、谢晓龙等人[18]、宋亚男等人[19]以及王华昌等人[20]所开展的工作都是基于这种等距放大原理的。
除了实现非规则零件的拟合，等距放大原理还用于考虑多个零件间的干涉。雷贺功等人[21]采用多边形顶点射线算法对零件进行处理，消除了零件在排样过程中的可能发生的相互干涉。宋亚男等人[22]考虑了不规则图形在板料排样过程中可能的干涉情况，专门研究了其中的判交和碰靠过程。这些关于多边形的干涉碰撞算法执行起来还很复杂，其复杂程度与目标多边形的性质相关，尤其在某些非凸多边形的情况，采用自动化的预处理存在一定程度的困难，这方面的工作有待延续。
2.2 排样问题的后处理
经过排样算法进行计算以后，所获取的排样方案只是一种近似的较优结果，所以排样方案可能存在理想的情况，这就需要对排样方案进行后续的人工干预，该过程通常称为排样问题的后处理过程。经过排样问题的后处理可使排样结果更加完善，过去也有少量学者强调了这方面的工作。贾志欣等人[23]运用计算机图形学处理技术结合现代智能算法的方法，按照图形预处理、自动排样、人工交互编辑3步解决了不规则零件的排样问题。黄星梅等人[24]通过交互寻优的手段对自动排样系统产生的排样图实现进一步的优化。
2.3 排样问题的近似求解算法
在板料优化排样问题中，最重要的步骤是采用一定的算法确定优化排样的方案。针对板料排样问题，目前的近似求解算法主要有确定性近似求解算法和启发式近似算法：
2.3.1 确定性近似求解算法
上世纪90年代前，国内外主要解决的板料排样问题主要是对矩形件的排样方案的确定，其中所采用的近似求解算法一般为确定性近似求解算法[25]如基于一维装箱的FFD算法、BFD算法和基于最左最下原则的算法(BottomLeft，BL)、双向背包算法、相近图形组合算法、动态规划算法等。在国内，文贵华等人[26]提出基于动态分割与合一的优化排样算法，将前一轮排样剩下的相邻余料动态地合并成较大的余料参与下一轮排样；崔耀东[27]等人提出连分数分支定界算法，用以实现对单一尺寸矩形毛坯的排样问题进行求解。这些排样算法的特点是具有确定性，求解结果仅决定于原材料和目标件以及求解策略，而与最优结果之间没有必然联系，不仅如此，通过这些方法求解的结果并不一定是较满意的解，而且对于较大的问题不是很适用。
2.3.2 启发式近似算法
启发式近似算法是研究人员受到自然界的启发所提出的一系列优化算法，在很多优化问题包括板料排样优化问题中具有较为理想的求解结果。在排样问题中，应用较多的启发式优化算法主要是模拟退火算法和遗传算法。贾志欣等人[28]针对传统的矩形件排样问题采用了模拟退火算法进行求解，建立了板料排样优化问题的模拟退火算法求解关键步骤。在此基础上，后续的研究人员采用模拟退火法解决了很多板料优化排样问题，涌现出很多新兴的工作。在排样问题求解中，遗传算法一种主要的算法，在遗传算法的应用方面开展了较多的工作[29-30]。杨威等人[29]采用遗传算法对大规模矩形零件在板材上的排样方案进行优化。贾志欣等人[30]则将这种算法应用到二维不规则零件排样优化问题中。龚志辉等人[31]提出了一种求解矩形件排样遗传算法的改进方法，实际上是在遗传算法中进行一定的预处理；陶献伟等人[32]将填充算法和遗传算法结合起来，应用填充算法对遗传算法作预处理，使矩形件更为方便；宋亚男等人[33] 采用改进免疫算法对排样问题进行求解，探讨了记忆效应的影响。2008年，赵新芳等人[34] 重新考虑了矩形件带排样问题的遗传算法，用带符号的有序整数串作为初始种群个体，改善了初始个体解的质量；吴斯等人[35] 更提出了小生境免疫遗传算法用以解决硅钢片优化排样问题。采用他们描述的方法保持抗体群的多样性，加快了优良个体的产生，提高了算法的收敛速度。
将多种启发式优化算法结合使用是实现板料排样优化的一种重要方式，到目前为止已经开展了大量工作。张玉萍等人[13]结合了模拟退火算法和遗传算法，提出了基于模拟退火技术的遗传算法，解决了皮料加工中的皮料优化排样问题。在她们所提出的算法中，采用能自适应地控制变异率的优化搜索方法，使得优化高效地逼近全局最优解。蒋兴波等人[36]提出自适应模拟退火遗传算法来对板料排样进行优化，其中通过环形交叉算子和环形变异算子来构造出自适应遗传算法，实现遗传算法的交叉和变异概率的自动调整，从而提高了算法的效率和效果。李明等人[37]结合了模拟退火算法和粒子群算法，在其中采用了交叉算子和柯西变异算子，提高了算法的收敛速度和计算精度，获取了较好的排样优化方案。陈勇等人[38]结合遗传算法和模拟退火算法设计了一种启发式排样算法，用以处理不规则多边形的排样问题。
2.3.3 简化算法
除了确定性近似算法和启发式近似算法之外，还有少数学者提出通过简化算法来实现对板料排样问题的求解。王峰等人[39]针对单一实体排样提出了水平线迭代切割排样算法。许超等人[40]针对数控直角剪排样的要求提出了一种正交阵列排样算法。洪灵等人[41] 设计了一种应用于不规则零件排样的快速解码算法，平行线化零件和板料，然后采用左下角(BL)策略驱动零件在板料上的排样。采用简化算法能够较快得到解，虽然在优化效果上没有精心设计的算法好，但仍然能够满足部分工程中的应用，得到工程解的认可。
3 结束语
板料排样优化问题在工程领域中具有广阔的应用潜力，在工程的节能节材方面扮演着重要的角色。经过多年的发展，学术界已在该问题的研究中取得了很大进展。目前，着计算机求解能力的增强，板料的优化排样问题已逐渐推向工程应用，在工程中的目标是采用稳定高效排样优化方法，实现板料排样方案的优化。由于排样优化问题是一个复杂的工程问题，包括了多个求解过程，因此需要对这些过程进行综合考虑，以提出更优的排样方案。同时，为实现板料优化排样的广泛应用，还需要继续开展板料排样技术与板料设计以及自动化加工技术的集成，实现工艺的配套，为节能节材提供保证。
参考文献：
[1] Xiaozhen Mi.Case Study on Optimization of Rectangular Object Layout by Genetic Algorithm[J].LNCS,2008,5236:608-619.
[2] 黄春峰.冲压工艺中的少无废料冲裁技术[J].航空制造技术,1999(4):54-56.
[3] 黄宜军,施德恒,许启富.钣金CAD中一个较优的排料算法[J].计算机辅助设计与图形学学报,2000,12(5):380-383.
[4] 袁国华.级进模工步排样中的组合优化问题研究[J].机械科学与技术,2000,19(6):947-949.
[5] 刘德福,罗意平,杨岳.面向铁路车辆制造业的矩形件优化排样系统[J].中国铁道科学,2003,24(4):34-39.
[6] Seiden S S,Woeginger G J.The two-dimensional cutting stock problem revisited[J].Mathematical Programming,2005,102(3):519-530.
[7] 赵民,袁哲,岳玉梅.缺陷石板的计算机优化排样[J].沈阳建筑大学学报:自然科学版,2007,23(6):21-24.
[8] 崔耀东,于洪方.钢板数控下料排样的一种优化算法[J].南京航空航天大学学报,1999,31(6):712-715.
[9] 崔耀东,周儒荣.单一尺寸矩形毛坯排样时长板的最优分割[J].计算机辅助设计与图形学学报,2001,13(5):434-437.
[10] 崔耀东.长板单一尺寸矩形毛坯定长分割优化排样[J].计算机工程,2004,30(7):178-180.
[11] 李英华.二维几何排样问题分类编码的研究[J].机械科学与技术,2000,19(3):441-444.
[12] 马建,滕弘飞,刘德全.基于样图的排样及其样图检索方法[J].软件学报,2000,11(12):1685-1691.
[13] 张玉萍,张春丽,蒋寿伟.皮料优化排样的有效方法[J].软件学报,2005,16(2):316-323.
[14] 张玉萍,宋健,蒋寿伟.基于离散化和遗传算法的皮革制造中的排样问题[J].计算机工程,2004,34(23):143-144.
[15] 曹炬.二维异形切割件优化排样的拟合算法[J].中国机械工程,2000,11(4):438-441.
[16] 赵震,彭颖红.实用型冲压毛坯优化排样系统的研究与开发[J].机械科学与技术,2002,21(2):312-314.
[17] 王亮申.基于顶点的冲裁零件排样系统[J].机械科学与技术,2002,21(2):334-336.
[18] 谢晓龙.冲压工艺数字化设计中的优化排样算法研究与系统实现[J].塑性工程学报,2005,12(1):15-19.
[19] 宋亚男.排样图形预处理中的几个实用算法[J].系统工程与电子技术,2005,21(6):1102-1104.
[20] 王华昌,李志刚.冲裁件优化排样算法的研究[J].中国机械工程,2001,12(2):199-202.
[21] 雷贺功,孙厚芳,刘汉雄.冲裁件优化排样的多边形顶点射线算法[J].北京理工大学学报,2004,24(9):770-773.
[22] 宋亚男.不规则图形排样系统中靠接算法比较研究[J].计算机工程,2004,30(19):8-10.
[23] 贾志欣.异型件排样系统的研究与开发[J].计算机工程,2002,28(12):218-220.
[24] 黄星梅,龚志辉,钟志华.矩形件优化排样系统中的交互寻优处理[J].湖南大学学报:自然科学版,2004,31(1):25-28.
[25] Dagli C H,Tatoglu M Y.An approach to two dimensional cutting stock problems[J].International Journal of Production Research,1987,25(2):175-190.
[26] 文贵华,丁月华.基于动态分割与合一的排样算法[J].计算机工程,1999,25(12):23-24.
[27] 崔耀东,张春玲,赵谊.同尺寸矩形毛坯排样的连分数分支定界算法[J].计算机辅助设计与图形学学报,2004,16(2):252-256.
[28] 贾志欣.矩形件排样的模拟退火算法求解[J].四川大学学报:工程科学版,2001,33(5):35-38.
[29] 杨威,罗阳,刘胜青.大规模矩形零件优化套排的遗传算法[J].四川大学学报:工程科学版,2001,33(5):59-62.
[30] 贾志欣,殷国富,罗阳.二维不规则零件排样问题的遗传算法求解[J].计算机辅助设计与图形学学报,2002,14(5):467-470.
[31] 龚志辉,黄星梅.二维矩形件优化排样算法的改进研究[J].湖南大学学报:自然科学版,2003,30(S1):47-49.
[32] 陶献伟,王华昌,李志刚.基于填充算法的矩形件排样优化求解[J].中国机械工程,2003,14(13):1104-1107.
[33] 宋亚男,邓飞其,叶家玮.基于改进免疫遗传算法的不规则图形排样[J].计算机工程,2005,31(9):170-172.
[34] 赵新芳.矩形件带排样的一种遗传算法[J].计算机辅助设计与图形学学报,2008,20(4):540-544.
[35] 吴斯,曹炬.基于小生境免疫遗传算法的硅钢片优化排样[J].计算机工程,2008,34(10):181-183.
[36] 蒋兴波,吕肖庆,刘成城.求解矩形件优化排样的自适应模拟退火遗传算法[J].计算机辅助设计与图形学学报,2008,20(11):1425.
[37] 李明,宋成芳,周泽魁. 一种二维不规则零件优化排样算法 [J]. 四川大学学报:工程科学版,2005,37(4):134-138.
[38] 陈勇.基于遗传模拟退火算法的不规则多边形排样[J].计算机辅助设计与图形学学报, 2003,15(05):598-604.
[39] 王峰,俞新陆.基于单一实体的轮廓表示及其水平线迭代切割的排样算法[J].机械科学与技术,2001,20(6):940-942.
[40] 许超,金霞.数控直角剪排样优化系统研究[J].中国机械工程,2001,12(10):1145-1147.
[41] 洪灵,王耘.一种不规则零件排样的快速解码算法[J].计算机辅助设计与图形学学报,2005,17(11):2465-2470.
