矩形石板优化排样及切割路径规划研究

袁 哲，王永振，赵汉驰，安 冬

（1.沈阳建筑大学 机械工程学院，2.高档石材数控加工设备与技术国家地方联合工程实验室，沈阳 110168）

0 引言

国内石材加工现处于粗放型的加工阶段，多采用人工计算排样和切割加工，石材利用率低，浪费了大量珍贵的不可再生资源[1]。为了提高石材的利用效率，有必要研制一种可自动排样及切割加工的桥式切机，这需要对矩形石板的优化排样及对应的切割路径规划问题进行研究[2～4]。国内外学者对矩形排样进行了很多的研究，赵民[5]等利用VC++设计了矩形单一排样系统；M.Z.Arslanov等[6]人利用多项式算法得到了同高度或同宽度矩形的最优排样方式，并且得到了相应的最短路寻优路径；Andrea Cassioli等[7]利用启发式算法研究了同尺寸矩形在凸区域中的最优排样方式。上述学者对矩形排样有了深入的研究，并且给出了最短路寻优路径，但是并没有给出与排样方式对应的切割方式及切割坐标，不能满足桥式切机“一刀切”的特点。因此，针对石材“一刀切”的单一排样方式以及切割路径规划方面还有待研究。

本文利用动态规划算法建立单一排样的数学模型，通过寻求动态规划算法的全局最优路线，确定矩形石板的单一排样方式，并且按照单一排样的过程，寻找到矩形石板的切割路径，提高了矩形石板的加工效率。

1 基于动态规划的单一排样数学模型的建立及求解

动态规划是解决多阶段决策问题的一种数学方法。动态规划算法根据多阶段决策问题的特点，把多阶段的问题变换为一系列相互联系的单阶段问题，然后逐个加以解决的算法[8]。利用动态规划算法求解多阶段决策问题，必须先将问题的过程分为几个相互联系的阶段，恰当的选取状态变量和决策变量，并定义目标函数，把一个大问题化为一族同类型的子问题逐个求解，然后利用阶段之间的递推关系寻求全局最优路线。动态规划算法所针对的问题有一个显著的特征：它所对应的子问题树中的子问题呈现大量的重复性。动态规划算法的关键就在于对重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，以后再遇到时直接引用，不必重新求解。矩形毛坯单一排样就属于这样一类问题。

设矩形石板尺寸为L×W(L≥W)，工程板尺寸为a×b(a≥b)。对于上述尺寸的矩形石板和工程板，利用动态规划的思想，将整个决策过程分为L×W个阶段，第x×y个阶段的状态变量为(x,y)，决策变量为Q(x,y)，目标函数为F(x,y)，F(x,y)表示尺寸为x×y的矩形石板所包含工程板数量的最大值[9]。由动态规划算法可知，F(L,W)为整个问题的目标函数。通过初始条件，按不同阶段的递推关系逐阶段递推寻优，确定F(L,W)，并且通过逆推确定整个问题的最优路线，随之确定矩形石板的单一排样方式。矩形单一排样动态规划算法的数学模型为：

式中，

当F(x,y)=F(x,y-b)+int(x/a)，矩形石板横排，决策变量Q(x,y)=1 ；

当F(x,y)=F(x-b,y)+int(y/a)，矩形石板纵排，决策变量Q(x,y)=2 ；

当F(x,y)=0，矩形石板排样结束，决策变量Q(x,y)=0。

由于此问题的状态变量是二维数组，为了不混淆第x×y阶段与第y×x阶段的状态变量(x,y)与(y,x)，故约定：第1阶段状态变量为(1,1)，第2阶段的状态变量为(2,1)，…，第L阶段的状态变量为(L,1)，第(L+1)阶段的状态变量为(1,2)…，即先按x递增，再按y递增的方式来划分不同的阶段。

对于第x×y阶段的目标函数F(x,y)，若x＜b或y＜b，此时矩形石板不能容纳一个工程板，故可得F(x,y)=0。对于矩形单一排样，初始条件可以设为F(a,b)=1。由初始条件F(a,b)=1，根据F(x,y)的取值及与之对应的决策变量Q(x,y)，从第a×b阶段开始，利用动态规划算法，求解出每个阶段的目标函数及对应的决策变量。利用所求的目标函数数值与对应的决策变量，通过公式(1)逆推求解出包含最优解的最优路线。

例如，若第L×W阶段的决策变量Q(L,W)=1，则此阶段的目标函数F(L,W)=F(L,W-b)+int(L/a)，由式(1)，最优路线中的下一个阶段为第L×(W-b)阶段；查找第L×(W-b)阶段的决策变量Q(L,W-b)的值，若Q(L,Wb)=1，则此阶段的目标函数F(L,W-b)=F(L,W-2b)+int(L/a)，由式(1)，最优路线中的下一个阶段为第L×(W-2b)阶段；查找第L×(W-2b)阶段的决策变量Q(L,W-b)的值，…，按照此种方式，直至找到Q(x,y)=0的阶段，此阶段即为最优路线结束的阶段。至此，最优路线确定。

对于最优路线中决策变量，不妨设其值所组成的集合为数列{an}。显然，{an}中的元素仅为1或2（不考虑结束时的0）。通过最优路线来确定整个矩形石板的单一排样方式。例如，当{an}={1,1,2,2,2,1,1,2,2,1}时，则尺寸为L×W的矩形石板需要横排，条带长度为L，宽度为b，含工程板int(L/a)个；排完后的矩形石板尺寸为L×(W-b)，此矩形石板需要横排，所排条带长度为L，宽度为b，含工程板int(L/a)个；排完后的矩形石板尺寸为L×(W-2b)，此矩形石板需要纵排，所排条带长度为(W-2b)，宽度为b，含工程板int((W-2b)/a)个；排完余下的矩形石板尺寸为(L-b)×(W-2b)，此矩形石板需要纵排，…，根据{an}中的元素，按照上述方式进行排样，直至完成整个矩形石板的排样。

2 矩形石板切割路径的确定

矩形石板切割路径的确定是通过记录排样过程中各根条带的排样方式来实现的。根据规范多级方式[10]，整个矩形石板是由若干根条带组成的，方向相同且连在一起的条带组成级。为了尽可能的缩短切割路径，实现桥式切机的自动化切割，需要将方向相同的条带组成的级进行切割，然后再将级切割成条带，再将切好的条带切割成工程板，以此完成整个矩形石板的切割。

具体地说，矩形石板的切割分4步进行：

1）将矩形石板切割成级，如图1所示。按照动态规划算法中优化排样的顺序进行级的切割，将石材大板切割加工成几个大的区域。每次切割完成后，利用桥式切机横梁上的真空吸盘将级转移至辅助工作台，依次循环直至将最后两个级切开后，将倒数第二级移至辅助工作台。此时主切割工作台上剩余最后一个级，以便将其加工成工程板。

图1 将矩形石板切割成级

2）将级切割成带，如图2所示。对于主工作台上的级(此处以第一级为例)，按照排样方案进行条带的切割加工，将级中的所有条带切割加工出来。

3）将条带切割成工程板，如图2所示。步骤2完成后，将主切割工作台旋转90°，对主工作台上的条带（此处以第一级切割的条带示例）按照排样路径进行通切，完成工程板的切割。

图2 将第一级切割成条带和工程板

4）完成主工作台上的级的工程板切割加工后，通过真空吸盘将全部工程板移动至辅助工作台，然后将上一个级移动至主切割作台，并保持切割前的位置。对于主工作台上的级，利用步骤2与步骤3的方法，将其切割成条带与工程板。完成此级的切割加工后，通过真空吸盘将全部工程板移动至辅助工作台，然后将上一级移动至主切割工作台，并且保持切割前的位置，循环加工直至完成所有级的切割。

对于步骤1中级的尺寸，利用数列{an}来确定：考察{an}中连续子列的个数，连续子列的个数即为级的数目；每个连续子列中元素的个数代表相应级所包含条带的个数。例如，{an}={1 1 2 2 2 1 1 2 2 1}，此数列共有5个连续子列，对应的矩形石板有5个级：第一级为横向级，包含2根条带；第二级为纵向级，含有3根条带；第三级为横向级，含有2根条带…。不失一般性，不妨设{an}中连续子列的数目为k，即此矩形石板分为k个级，第i(1≤i≤k)级的条带数为ni根。

对于步骤1的切割，切割坐标与级的尺寸有密切关系。由图1所示，每个级的尺寸与级在矩形石板中存在的次序有关。其中，级的宽度与级所含的条带数有关，为ni×b。对于级的长度，第一级为横向级的矩形石板（如图1(a)所示），级的长度如下：奇数级第一级的长度为L，第三级的长度为(L-n2×b)，第五级的长度为(L-n2×b-n4×b)… ，偶数级第二级的长度为(W-n1×b)，第四级的长度为(W-n1×b-n3×b)…。对于第一级是纵向级的板材（对应于图1(b)所示的矩形石板），有类似的结论。利用各个级的尺寸得到步骤1（将矩形石板切割成级）切割的坐标点如表1、表2所示。

表1 第一级为横向级的矩形石板步骤1的切割坐标点

表2 第一级为纵向级的矩形石板步骤1的切割坐标点

对切好的级进行步骤2与步骤3的切割。对于要进行切割的级，若此级是横级，则步骤2的切割全都是横切，步骤3的切割全都是纵切；纵向级与横向级恰好相反。

对于第一级是横向级的板材，第一级步骤2切割需要切的刀数是(n1-1)刀，每一刀都是横切。第1刀切点坐标为(L,W-b)；第2刀切点坐标为(L,W-2b),…,第(n1-1)刀切点坐标为(L,W-(n1-1)×b)。按照此种方式切割，对第一级完成步骤2的切割。然后进行第一级步骤3的切割，此步骤的切割刀数与a和L之间的关系有关。若a能整除L，需要切割的刀数为(int(L/a)-1) ，产生int(L/a)块工程板；若a不能整除L，需要切的刀数为int(L/a)，产生的工程板数目为int(L/a)+1（其中最后一块板材不是需要的工程板）。不失一般性，设第一级中步骤3的切割需要的刀数为m1，第i级中步骤3需要切割的刀数为mi（对于纵向级，有同样的假设，但是切割的刀数需要考察a和W之间的关系），则第1刀切点的坐标为(L-a,W)，第2刀的切点坐标为(L-2a,W)，第3刀…第m1刀的切点为(L-m1×a,W)。按照上述方式切割，直至第一级切割完成。

对于其他的级，有上述的类似的结论。对其进行总结，结果如表3、表4所示。

表3 第一级是横向级时，各级步骤2与步骤3的切割坐标点

表4 第一级是纵向级时，各级步骤2与步骤3的切割坐标点

3 实验研究

设矩形石板尺寸为1500×1500，工程板尺寸为400×300，单位：mm。利用动态规划得到的矩形单一排样数学模型进行编程，得到矩形石板的切割路径如图3与图4所示，切割坐标如表5与表6所示。

图3 矩形石板步骤1的切割坐标

图4 矩形石板步骤2与步骤3的切割坐标

表5 步骤1的切割坐标

表6 步骤2与步骤3的切割坐标

4 结论

1）通过动态规划算法，建立了矩形单一排样的数学模型，利用数学模型进行逆推得到了矩形工程板的最优排样方案。

2）按照单一排样各根条带排样的顺序，得到了级的排样，确定了桥式切机的切割路径，实现了桥式切机的自动化切割，解决了石材企业人工下料慢，错误率高的问题，极大的提高了石材企业的加工效率，提高了石材企业的核心竞争力。

[1] 赵民,那丽红,闵莉,等.基于图像处理技术的石材大板表面轮廓提取算法[J].沈阳建筑大学学报(自然科学版),2010,26(5)：981-985.

[2] 侯媛彬,高阳东,郑茂全.基于贪心-遗传算法的混合轨迹加工走刀空行程路径优化[J].机械工程学报,2013,49(21)：153-159.

[3] 刘恒.数控曲面切割路径生成算法研究[J].制造业自动化,2010, 32(11)：65-67.

[4] 胡鹏,胡春燕,蒋念平.二维激光连续切割移动材料路径算法及约束[J].中国激光,2014,41(10).

[5] 赵民,王若男,李洪飞,等.基于VC++矩形纹理石材排样系统[J].沈阳建筑大学学报(自然科学版),2011,27(3)：578-582.

[6] M.Z.Arslanov,D.U.Ashigaliev,E.E.Ismail.Polynomial algorithms for guillotine cutting of a rectangle into small rectangles of two kinds[J].European Journal of Operational Research, 2008(185)：105-121.

[7] Andrea Cassioli,Marco Locatelli.A heuristic approach for packing identical rectangles in convex regions[J].Computers & Operations Research, 2011(38)：1342-1350.

[8] 曹卫华,郭正.最优化技术方法及MATLAB的实现[M].化学工业出版社,2005：112-115.

[9] 胡祥培,王旭茵,刘伟国,等.动态规划问题的知识化数学模型生成器研究[J].管理工程学报,2004,18(2)：64-70.

[10] 崔耀东,张春玲,赵谊.同尺寸矩形毛坯排样的连分数分支定界算法[J].计算机辅助设计与图形学学报,2004,16(2)：252-256.