钢构件的排料问题

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2015/8/26,#,钢,构件的排料问题,目录,问题分析,模型假设,模型的建立与求解,模型评价与改进,一、问题,分析,题目,研究的是二维排料问题，排料问题的实质是研究如何组合零件摆放问题。对于二维排样优化问题，可以分为一下三个独立问题来考察,：,1.,将零件放入板材中，每块板材中的零件的面积之和不大于板材的面积；,2.,零件为矩形，板材为矩形，要求将零件互不重叠的放进板材，使材料利用率最高；,3.,零件具有任意复杂的平面形状，板材为矩形，要求将零件互不重叠的放入板材，使材料利用率最高，并满足一定的工艺要求,。,问题,1,为单一板材套裁下料问题，零件为矩形，要使得板材利用率最高同时又满足一刀切的约束条件。对于单一板材下料问题，一般使用,BL,算法，但常规的,BL,算法不满足一刀切的约束条件。故可在使用,BL,算法的排样过程中，每排一个矩形件则进行一次虚拟切割，从切割剩余的原料中进行下一次排样，直至所有零件排完或者所有符合要求的剩余矩形使用完。,问题,2,是多边形板材下料问题，在满足一刀切约束条件下将多边形化为矩形进行下料无疑是最简单的方法。但要保证最终的板材利用率最高则在多边形化为矩形的过程中要保证其所转化的矩形为最小的矩形，故可以引入最小包络矩形的概念。通过求解最小包络矩形，再通过问题,1,中建立的剩余矩形填充模型进行多边形的排料求解,。,问题,3,是多板材套裁下料问题，对于有多张板材的情况下，可以考虑将多张板材进行拼接，转换为单一板材下料问题。由于这种拼接在工艺要求下是不能实现的，故只能是虚拟拼接，即在其拼接线处，不能存在被排样矩形件。所以可以对排样过程利用某些约束使得拼接线处不会被排样。在此约束下利用问题,1,所建立的剩余矩形填充算法进行排料求解。,一、问题,分析,1.,假设不考虑切割时须预留的余量,宽度,2,.,假设算法排料中默认零件是无纤向约束,的,3,.,假设对各零件的需求度没有高低之分,二,、模型假设,在,BL,条件的约束下，设剩余矩形以左下角坐标及长宽表示，剩余矩形长为，宽为，设原料板左下角坐标为坐标轴的原点（,0,0,）则,第,n,个剩余矩形,设所有排样点都是从剩余矩形的左下角开始，待排矩形件同样以左下角坐标以及长宽表示，若待排矩形,i,的长为，宽为 则,第,i,个待排矩形,定义,1,：剩余矩形即第,n,次排样切割后余下的,n+1,个可再次排样切割的矩形，原始剩余矩形即初始原料矩形。,定义,2,：板材利用率 就是所有零件面积之和与在一刀切工艺后继续切割的那部分板材面积的比值,问题一,三、,模型的建立与求解,为了保证“一刀切”的工艺，每排一个矩形都要确定其切割方向，则矩形件,i,排样后的剩余矩形集如图,1-1,所示（图中虚线为其切割方向）,由,图可知第,i,次排样后剩余矩形集可表示为,三、,模型的建立与求解,问题一,按逆时针方向记录剩余矩形则有,在排样算法中应尽可能考虑大的矩形块，所以由图,1-1,可知，剩余矩形，必定有重合的部分,设任意两个矩形可用其左下角坐标和右上角坐标表示为,（,1-6,）,则重复部分,三、,模型的建立与求解,问题一,在进行一次排样后有两个剩余矩形，要进行下一次排样则需从中选定一块。当选定一块后，采用启发式重新分块，即利用公式（,1-2,）求出剩余矩阵的重叠部分，利用未选择的剩余矩形减去重叠部分。若未选择的剩余矩形为,，则重新分块得新的剩余矩阵如图,1-1,中,R2,所示。而被选中的剩余矩形则按公式,1-1,进行运算排样。,设所有第,n,次切割完成后所产生的剩余矩形集为结尾剩余矩形集,，则,第,n,次排样后产生新剩余矩阵的面积,结尾剩余矩形总面积,三、,模型的建立与求解,问题一,第,n,次排样零件的面积,生产零件总面积,（,1-10,）,综上有目标函数为,（,1-11,）,约束条件,：,(1-12,),三、,模型的建立与求解,问题一,图,1-2,剩余矩形填充算法流程图,三、,模型的建立与求解,问题一,定义,3,：最小包络矩形是指完全包含了图形上所有的点、线，且各边均与图形相接触的面积最小的矩形,定义,4,：零件总面积与包络矩形总面积的比值为包络矩形,利用率,2.1,模型的建立,数据预处理：,根据附件二所给数据运用,MATLAB,软件以零件一个顶点为原点绘制出零件,图形,三、,模型的建立与求解,问题二,2.1.1,最小包络矩形,模型,a,多边形的数据,保存,设,多边形信息用顶点动态数组,表示，点,的表示参考,MFC,的,CPoint,类，设计,CMYPoint,类,Class CMYPoint,float x,；,float y,；,b,多边形顶点排序的方向性判断,保存,的多边形顶点，有些是按顺时针顺序排序，有些是按逆时针顺序排序。为了便于程序上对数据点进行处理，我们对其排序顺序进行统一化。,首先判断多边形数据点的排序顺序。实际上多边形顶点的方向是与凸顶点及其相邻的两个顶点组成的三个顶点的方向是一致的，所以我们只需判断这三个顶点的方向即可。一般情况下，多边形的最上点，最下点，最左点和最右点必定是凸顶点，因此只要当多边形顶点中的,x,或,y,值有一个值是所有同类中的极值，就能确定该顶点是凸顶点。,顺序三个顶点的方向性判断还可以通过这三个顶点连线所得到的三角形,S,的面积 来,判断,三、,模型的建立与求解,(2-1),故有,：,c,多边形凹凸性的判断,任意多边形都具有凹凸性质。如果多边形上所有的顶点都是凸顶点，则为凸多边形；如果任有一个顶点是凹顶点，则这个多边形为凹多边形。,按逆时针方向对各顶点编号，将,m-1,，,m,，,m+1,三个点连接构成一个三角形,S,，根据公式,(2-1),求取面积 ，根据 的大小有：,三、,模型的建立与求解,问题二,d,凹多边形凸包的求解,凹多边形,的凸包算法思想：当多边形顶点是凹点时，去掉该顶点及与该顶点相邻的两条线段，把其前后两点相连。然后重新扫描多边形是否有凹点，直到去掉全部凹点为止。,e,凸多边形的最小包络矩形求解,对于,任意一个凸多边形，其最小包络矩形至少有一条边与该多边形的某一条边重合，具有,m,个顶点的凸多边形有,m,条边，故其有,m,个外接包络矩形。通过比较其各包络矩形面积，求出最小包络矩形。设任意一个凸多边形其中一个顶点为第,m,个顶点，按逆时针方向的下一个顶点为第,m+1,个顶点，两点连线所构成的多边形的一条边与,X,轴所成角度为，如图,2-3,所示,三、,模型的建立与求解,问题二,(2-2),(2-3),(2-4),将多变形以,m,点为圆心，顺时针旋转 角度，使点,m,与点,m+1,两点连线所构成的多边形的一条边与,X,轴平行。则旋转后各顶点可表示为,(2-5),设各顶点,X,坐标最大值为，最小值为；,Y,坐标最大值为，最小值为。则：,三、,模型的建立与求解,问题二,设对,m,点的包络矩形长为，宽为 则,其包络矩形可表示为,2.1.2,剩余矩形填充模型的建立,通过最小包络矩形求解模型，可以求出最小包络矩形表示式,(2-10),在,问题,1,中，建立了剩余矩形填充模型，对矩形零件进行排料。在问题,2,中建立了满足一刀切约束的最小包络矩形求解模型，求出最小包络矩形。通过剩余矩形填充模型对所的最小包络矩形进行排料，即可获得针对多边形零件的排料方案。,三、,模型的建立与求解,问题二,2.2,模型的求解,2.2.1,最小包络矩形的求解,由数据可知零件二为凹多边形，故利用凹多边形的凸包求解算法，编写,MATLAB,程序，求得零件二的凸包如图,2-5,所示,零件,一可以进行图形组合，可能会得出最优包络矩形,。零件,二所得包络矩形，在满足一刀切约束条件下已为最优包络矩形。,故针对零件一，在满足一刀切约束的条件下，我们利用坐标变换进行了零件组合，结果如图,2-8,所示,三、,模型的建立与求解,2.2.1,剩余矩形填充模型的求解,由最小包络矩形求解模型可得零件一、零件二各最优包络矩形的规格数量如表,2-3,所示,最优包络矩形编号,矩形表示式,数量,零件一,（,0,，,0,，,519,，,461,）,7,零件二,（,0,0,350,400,）,14,利用问题,1,所建立的剩余矩形填充模型，将零件一，零件二数据代入,MATLAB,程序中有结果如图,2-10,所示,三、,模型的建立与求解,5.3,问题,3,模型的建立与求解,3.1,模型的建立,a,原料板的拼接,为了方便计算，对原料板进行纵向虚拟拼接，化多板材套裁为单一板材套裁问题。设拼接线的纵坐标为，则有拼接线函数,b,矩形集的表示,参照问题,1,，对剩余矩形集定义一个,rect,类，用以保存所有剩余矩形。则有第,n,个剩余矩形可表示为,由问题,1,有，带排矩形集可表示为,三、,模型的建立与求解,问题三,c,临界平移函数的构建,由于工艺的限制，对原料板材进行的拼接为虚拟拼接，故在其拼接线处则不能排入矩形件，由此构建临界平移函数。当第,i,次排料时，若剩余矩形纵坐标与带排矩形的宽 之和大于拼接线纵坐标，则将剩余矩形纵坐标向上平移拼接线纵坐标与剩余矩形纵坐标之差个单位（即剩余矩形纵坐标变为拼接线纵坐标）更新剩余矩形集，重新进行排样。则有,剩余矩形,3.2,模型的求解,通过编写,MATLAB,程序实现对原料板材的虚拟拼接如图,3-1,所示,三、,模型的建立与求解,6.1,模型的优点,（,1,）本文引入,BL,算法并结合填充算法,得到剩余矩形填充算法,对板材下料问题进行规划,.,通过实际操作,发现这种排样算法具有准确度高,不受板材形状限制的优点,.,（,2,）针对不规则原件，对算法进行改进，提出了最小包络矩形的模型，这种算法对任意不规则图形都可以得到一个较好的排料解，能够很好的解决实际生产问题。,（,3,）针对多板材套裁问题，我们提出了“多化一”的思想，通过虚拟拼接，将多块板材问题转换为问题一的单板材问题，将问题简单化处理,。,6.2,模型的缺点,（,1,）在模型建立的过程中，我们并没有考虑到原件以及板材的纤向约束情况。,（,2,）第二问求解不规则零件的模型，只考虑了简单的拼接情况。,6.3,模型的改进,对所提出的剩余矩形填充算法，可利用现代优化算法，如遗传算法，模拟退火算法等进行优化，由此得出的解随板材利用率相同，但切割剩余板材的可利用度会更高，在此不做深入讨论。,四,、,模型的评价与改进,