钢构件的优化排料问题.docx

钢构件的优化排料问题
1、 问题的重述
1.1 背景
在当今激烈的市场竞争中, 降低生产成本、提高生产效率和增强对市场的应变能力, 是企业保持竞争力的主要实现手段。在钢构件制造产品的生产过程中，依照产品零件尺寸从板料中截取大小适当的零件过程称之为排料，也称之为下料。排料是钢构件制造的第一道工序。在这道工序中，不同的排料方案具有不同的材料利用率，而原材料的利用率直接影响产品的成本。材料费用是制造企业主要的生产成本, 一般占总成本的 60% ~ 80% , 在大批量生产中, 材料的利用率即使提高 1% , 所创造的经济效益也相当可观。据调查,优化下料后,制造企业材料利用率可平均提高 5%~ 10%。

另外由于切割工艺的要求，切割只能实行“一刀切”的工艺（在整料或余料中，从一边的某点到另外一边某点的连线一次切割，但可以在切割下来的板料中再次切割）。板材的利用率就是所有零件面积之和与在一刀切工艺后继续切割的那部分板材面积的比值。

1.2 问题
对于第一问，对1张板料和若干规则形状零件，求如何在板料中摆放零件使其板料的利用率最高。

规则形状零件即指矩形零件。其描述一般只需用矩形的长和宽。规则形状零件的排料问题的实质是研究如何组合零件摆放问题，使得在整个原料上摆放大量的不同长和宽的零件产生的废料最少、整料和余料的利用率最高。排放时，其零件间的搭接关系的处理相对容易，只需考虑长、宽两个因素（含预留的损耗量）。板材大小:2350*900【1张】。表1是九个规则形状零件的具体规格。

表1
零件
一
二
三
四
五
长（mm）
350
350
500
500
500
宽（mm）
300
200
240
210
350
个数
2
2
2
2
2
零件
六
七
八
九

长（mm）
300
250
500
500

宽（mm）
250
200
400
200

个数
2
2
2
2

对于第二问，对1张板料和若干不规则形状零件，如何在板料中摆放零件使其板料的利用率最高。

与第一问类似，但是此时需要切割出来的零件不具有矩形般对边平行的条件，切割较为麻烦，同时可能会造成更多边角料的产生，降低板料的利用率。图1和表2是题目要求的两种不规则零件的具体形状和规格。板材大小:2380*1630【1张】。
表2
零件
一
二
个数
14
14

图1

零件一 零件二

对于第三问，考虑到实际的切割过程中，一张板料并不能满足所有零件的生产需求，故而要求设计对2张板料和若干规则形状零件，如何在板料中摆放零件使其板料的利用率最高。还有一点与问题一不同，即各零件要求生产的个数有所改变。板材大小:4550*1630 【2张】。具体见下表3。

表3
零件
一
二
三
四
五
个数
4
0
5
6
6
零件
六
七
八
九

个数
4
2
2
4

2、符号规定与模型假设

2.1 符号规定
符号
表示意义
L
板材的长度
W
板材的宽度
hi
矩形件的长，i=1，2，3 …
w
矩形件的宽，i=1，2，3 …
ni
矩形件的数量，i=1，2，3 …
η
板材利用率
Ri
零件的种类，i=1，2，3 …

2.2 模型假设
1. 切割机垂直切割，不考虑料板的厚度，即将问题转化为二维平面问题；
2. 切割不会导致料板的长度或宽度减小，忽略切割损耗；
3. 切割方式为一刀切，即在整料或余料中，从一边的某点到另外一边某点的连线一次切割；
4. 忽略切割效率，本文着眼点在于料板利用率的提高；
5. 对于问题二中的六边形，可看作是矩形一角删去一个150×150的正方形，而这一步骤利用一刀切不可能实现，故而假设六边形ABCDEF当作五边形ABCDE对待（图2），该零件的后续加工后文不予考虑。

图2

3、问题分析

本题目三个问题所研究的是一刀切下料, 问题一和问题三属于二维规则图形的优化排料问题，问题二属于二维不规则图形的优化排料问题。排料问题是典型的优化组合问题，具有很高的计算复杂性，属于NP完全问题。“一刀切”的实际现象给了本问题一个最基础的约束，使得排样有了一个这样一个基础：每次切割都将板材一分为二。

图 3 给出了一刀切下料与非一刀切下料的比较。
图3

问题一和问题三要求制作的零件规格有9种, 因此属于多零件下料问题。多种零件, 需要解决如何选择将零件合理高效的布置在板材上。本文的研究目的是在这些约束条件下实现优化排样, 提高板材利用率。排样目标为: 尽可能提高一块板的利用率。

排料需要满足的基本约束条件有：①零件之间互不重叠；②零件的排布不得超出板材边缘；③满足一刀切条件。

4、模型建立
4.1 模型的准备
由于问题一和二要求在一张料板上规划，问题三要求在两张规格相同的料板上规划，故而在料板数量上简化模型，仅考虑在一张规格已知的料板进行排料规划。对于二维排料问题，排料方式要满足零件长，宽方向上的套裁。
将N个零件记为R1、R2、…Rn合理的排布在板材A中，其中满足：
Max（畏）=Max（j=0NSprA*100%） （1.1）
且满足：
（1）Rr∈A j=1,2…N…,
（2）Rj⋂Rk=∅ （j≠k ， j k=1,2…N…） (1.2)
其中畏为排料的材料利用率，应满足畏最大的原则。Spj为第j个板材Rj的零件面积，A为第一次一刀切后继续用于一刀切的原料板材的面积，也即布局板材所消耗的原料面积，一般有
A=A0+A1+A2 （其中A0=r=0NSpr，A1为工艺废料，A2为结构废料）。
从式（1.1）中可以看出，理论上若废料（包括工艺废料和结构废料）面积减至0，材料的利用率能够接近1，但该理论值在实际生产中无法达到。工艺废料由行业的工艺要求产生，如切割损耗和余料，本题在建模过程中暂不考虑实际生产中的切割损耗。结构废料由具体板材的结构形状所决定。在生产中结构废料无法控制，要提高材料的利用率只有从减少工艺废料入手，通过采用更合理的排料方案，减少余料（工艺废料）。

4.2 模型的建立

4.2.1问题一模型的建立

设共有M张面积大小都为A的板材，N类目标零件板材。记板材的集合为：（X={Wi，H i i∈M}，零件集合为：Y={wj，hj j∈N} j类零件的数量为nj, 板材i上j 类零件的数量为nji，已知第k 个j 类零件在板材上的排列位置可以由其左下角坐标与右上角坐标唯一确定, 可记第k个j 类零件在下料板材i上的左下角坐标为(x0jki，y0jki), 右上角坐标记为(x1jki，y1jki)零件k 在
0 纵排
下料板材i上的排列方式记为pjki= ，目标是最大化板材的利用率。 1 横排
根据以上分析，将多板材下料问题用数学模型表示为：
Max（畏）=Max（j=0NSprA*100%） （1.3）
pr∈A j=1,2…2N…, (1.4）
pj⋂pk=∅ （j≠k j k=1,2…2N…）（1.5）
j，kmaxx1jki≤Wi， （1.6）
j，kmaxy1jki≤Hi，（1.7）
1Inji=nj （1.8）
式(1.3)为目标函数，表示最大板材利用效率；式(1.4)为零件规格约束；式(1.5)保证零件互不重叠；式(1.6)和式(1.7)为板材规格约束，式(8)为零件数量约束。

4.2.2 问题二模型的建立
该问属于二维不规则零件排样问题[2]，此类问题的求解主要有两种思路：一种是对这类问题直接在原材料上进行摆放；另一种则是将不规则零件转化为规则矩形件，然后按照矩形件进行优化排样。[4]

如果将不规则零件排放在矩形形状的板材上，其在板材上的位呈由三个参数决定，这三个参数是该零件的一个给定点在板材上的坐标（x,y）和该零件的排放角度θ，这三个参数确定后，该零件的其他各顶点参数均可通过这三个参数计算出来。[5]

首先定义以下参数：
——排样零件；
——排样零件图形；
——排样零件给定点的坐标。

零件在板材上的排样定位过程如下：
先将该零件的给定点在板材上平移至，然后再将该零件以为轴作角度为的旋转，这时零件在板材上的方向可表示为。则零件排样优化的模型为：

其中L为板材的长，W为板材的宽；N为排样零件的数目；为排样零件的面积；变量表示零件在板材上的排样状态，如果可以排放则取1，不能排放则取0。

排样的约束条件如下：

其中第一式约束了任意两个零件互不重叠；第二，三式约束了零件中任意点的坐标都必须在排样材料范围内，不能超出板材之外。

我们对于问题二的求解采用第二种方法，由于问题二给出的五边形和六边形并不是特别复杂的多边形，同时五边形具有直角。我们采用穷举法列出了6种较为常见排列方案，在这里对每种方案的利用率进行讨论，得出最佳矩形件优化方案。

矩形面积：277425

利用用率： 228189.5/277425*100%=82.25%

方案一（图4）
矩形面积：=399*617=246183

利用效率：=221583/246183*100%=90.01%

方案二（图5）
矩形面积：=411*558=229338

利用效率：=221100/229338*100%=96.41%

方案三（图6）
矩形面积：=411*664=272904

利用效率：=228050/272904*100%=83.56%

方案四（图7）
矩形面积：：=462*519=239778

利用效率：=221100/239778*100%=92.21%

方案五（图8）
矩形面积：：=400*350=140000

利用效率：=128750/140000*100%=91.96%

方案六（图9）

经过综合分析，我们拟采用方案三和方案六组合切割。至此，将不规则形状零件的排料问题简化为矩形零件的排料问题，可参照问题一模型来求解。

4.2.3 问题三模型的建立
与前两问有所不同的是，问题三要求在两张规格相同的料板上进行排料。经过计算得知，，故而我们在问题一模型的基础上，又可分两种方案进行比较：
（1）在一张板材上进行排板，看是否可以节省一整张料板；
（2）在两张板材上进行排版，排板顺序为两张同时进行，以求获得更大的剩余的料板整体面积。

4.3 算法模型
4.3.1算法结构框图图10
4.3.2 排样算法基本规则：
（1）插入规则
① 大边尺寸，指板材或者零件长度和宽度的较大边尺寸。
② 最大零件，指大边尺寸最大的待处理零件。
③ 最小空穴，指大边尺寸最小的待下料板材。

启发式算法[6]将待下料零件按大边尺寸降序排序，将原料板材按大边尺寸升序排序, 并规定新一轮的下料排样总是选取待下料零件中的最大零件，搜索空穴列表，从满足零件下料尺寸的空穴中选择最小空穴[1]作为下料板材。

(2) 放置规则－－靠左靠下
在求解初始排样方案中，对于给定空穴，规定从待排零件中选择高度最低、宽度最大的零件靠左靠下放置。

(3) 转向规则－－整除求余
设空穴小边为x ( x= min( W，L)，W和L分别为空穴的宽度和长度)，按插入规则和放置规则选定的零件宽度为w长度为l，则x与w，l之间满足以下线性关系: x= aw + l1 ，x= bh + d2。若d1 < d2 ,则按照w||x的方式放置零件，否则按照l||x的方式放置。

（4）切割线替换规则[1]
对于任意可行解, 若存在另一条切割线满足第一条切割线的切割条件, 则以这条切割线为第一条切割线所形成的排样方案与原解相同。

证明:

如图11所示, 已知区域 O 存在以 x 为第一条切割线的可行解 Ix, 则 O 中存在局部区域P, 使得P 中以 x 为第一条切割线的解 iox⊆I,现已经找到另外一条满足性质 1 的切割线 y, 需要证明 Iy= Ix 。

此时切割线 y 有两种情况: 一种为 y平行于 x, 另一种为 y 垂直于 x。下面分别就这两种情况进行证明。
（1） y平行于x。
x 将 O 划分为{ A C} 和 B 两部分, y将O 划分为 A 和{ B C} 两部分。易知iA∪C⊆I且iB⊆I, 同理iA⊆iA∪C 且 iC⊆iA∪C , 根据集合的传递性, 有iA⊆I且 iC⊆I 。所以以 y 为第一条切割线所形成的排样方案与原解相同。

（2） y垂直于x。
x 将 O 划分为{ A D} 和{ B C} 两部分, y 将 O 划分为{ C D}和{ A B} 两部分。易知：iA∪D⊆I 且 iB∪C⊆I, 同理iA⊆iA∪D 且 iD⊆iA∪D , iB⊆iB∪C且 iC⊆iB∪C , 根据集合的传递性, 有 iA⊆I, iB⊆I, iC⊆I, iD⊆I。所以以 y 为第一条切割线所形成的排样方案与原解相同。
切割线替换定理得证。

图11

4.3.3排样优化思想：

①采用二叉树的生成过程来描述板材的分割过程，则生成的二叉树就表示一个排样结果，即得到一个全局排样解。
②用I={N，G|N={nj},G={gj}，j=1，2，…} 表示一个全局排样解，其中N表示排样解中各类零件的个数集合；G表示排样解中零件的规格集合。∃i={Ni，Gi|Ni⊆N，Gi⊆G}是I的局部区域，则称i是I的一个局部解。
一刀切的切割特点决定了满足一刀切约束的排样解具有以下条件:

条件1 排样解中的第一条切割线必须满足：长度等于分割区域中与其平行的那条边的长度，且不影响任意零件的完整性。

条件2 设I为满足一刀切的全局解，对于I中的任意局部解i，i一定满足一刀切。

条件3 对于任意可行解，若存在另一条切割线满足第一条切割线的切割条件，则以这条切割线为第一条切割线所形成的排样方案与原解相同。

4.4下料优化问题的二叉树算法的构造
二叉树是一种常用的空间数据结构，因其结构简单，操作方便、快速而广泛应用于数据的排序和计算内部寻址等方面。本文主要基于VC++6. 0开发平台，对零件排料涉及到的二叉树算法进行了编写。

在排样过程中，由于一刀切的特性，1块矩形区域划分后，可得到2块小的矩形区域。在这2块矩形区域继续进行排样，就会得到4块矩形区域。不断进行下去，这个排样过程就是一种二叉树的结构。

本文将二叉树用于矩形物体布局空间状态的表达，具体应用如下:已知一个布局空间的矩形区域，按权值从可选布局物体中选择一个相对于该矩形区域来说是最优的布局物体A，并将其定位于该矩形区域的左下角。这样原布局空间变成了一个¬形区域。将这个¬形区域分成图12所示2个矩形A1和A2，分别用根结点的左、右2个子结点表示。这样，剩余的布局空间就变成了2个独立的布局空间，分别对这2个布局空间重复上述过程，直至没有可选布局物体满足要求时停止分解。

图12

其中，每个圆圈和数字代表二叉树的节点，代表在矩形中进行了一次子排样。根节点1为板材，进行一次子排样后，会生成2块空白矩形，相应产生2个节点:节点2和节点3。节点2的空白矩形进行一次子排样后，又会产生2个新的节点:节点4和节点5。节点之间的关系如图13所示：
图13

二叉树路径中的标号xi表示空白矩形分割方式。以节点1为例，定义X1=0时，对节点1的进行子排样后的空白区域进行横划分。X1=1时，对剩余空白区域的划分为竖划分。显然，当x1取值不同时，生成的节点2, 3中的原始空白矩形也不一样，更影响了后面的节点和排样结果。

具体步骤如下:

1.定义零件，二叉树节点的结构体，将板材和零件的长、宽与数量放置到数组中,并将零件按照长度从高到低，相同长度按照宽度从宽到窄进行排序。如下所示：
//定义待排零件
struct ORIGINAL_SQUARE
{
int length; //长
int width; //宽
int num; //数量};

//定义已排零件
struct SQUARE{
int length; //长
int width; //宽
int num; //数量};

//定义二叉树节点
struct NODE {
struct SQUARE blankSquare; //排布前的空白矩形
struct SQUARE *filledSquare; //空白矩形内排布的一列矩形
int fillesSquareNumber; //排布的矩形数目
int originalIndex; //排布的是哪个初始矩形
int remainLength; //顺着排布方向无法排布的矩形的长
int remainWidth; //顺着排布方向无法排布的矩形的宽
struct NODE *lastNode;//上个节点的地址};

//构建数组，存储数据，冒泡排序
#include<iostream>
using namespace std;
int main(int argc,char **argv)
{
//建立九行三列的二维数组
int row,col;
int i,n,k;
int** p; //p是一个二维int数组
row=9;
col=3;
p = new int*[row]; //创建行指针
for(i=1; i<=row;i++)
{
p[i] = new int[col]; //为每一行分配空间
}
cout<<"\n请按顺序依次输入零件的长,宽与数量,并用空格隔开:\n";
for(n=1;n<=row;n++)
{
for(k=1;k<=col;k++)
cin>>p[n][k];
}
cout<<"\n您输入的是:\n";
cout<<"\n长度\t宽度\t数量\n";
for(n=1;n<=row;n++)
{
for(k=1;k<=col;k++)
cout << p[n][k]<<"\t";
cout<< "\n";
}
cout<<"按照零件长度从高到低,相同长度下宽度从宽到窄排序得:\n";
for(n=1; n<=row; n++){ //for循环进行冒泡排序
for(int j = n+1;j <=row;j++){
if(p[n][1] < p[j][1])
{

int t = p[n][1];
p[n][1] = p[j][1];
p[j][1] = t;
int r = p[n][2];
p[n][2] = p[j][2];
p[j][2] = r;
int w = p[n][3];
p[n][3] = p[j][3];
p[j][3] = w;
}
if(p[n][1] == p[j][1]&&p[n][2] < p[j][2])
{

int t = p[n][2];
p[n][2] = p[j][2];
p[j][2] = t;
int w = p[n][3];
p[n][3] = p[j][3];
p[j][3] = w;
}
}
}
cout<<"\n长度\t宽度\t数量\n";
for(n=1;n<=row;n++)
{
for(k=1;k<=col;k++)
cout << p[n][k]<<"\t";
cout<< "\n";
}
cout << endl;
return 0;}

2.一张板材上的每次下料都优先选择长度最长，宽度最宽的零件靠左、靠下排列。此处选择权值法，引入权值公式计算板材的利用率：
Int w=λ1*u+λ2*t + λ3*r+ λ4*a

其中，u表示单个待排零件占空白区域比例; t表示一次子排样下的所有零件面积之和占空白区域比例; r表示剩余区域局部矩形的宽度；a表示剩余区域的面积; λ1，λ2，λ3，λ4分别代表u,t,r,a的加权系数。

以上的加权法直接影响的仅仅是一次排样，但由于全部零件的排样是由各个零件排样完成的，因此，通过调整加权系数，可以改变板材中排样的进程。多次调整权值并横向比较。选取总体排样率最高的权值，就可以得到较优的解。

3.在满足约束条件的情况下建立二叉树并实现遍历、搜索等操作：

#include<iostream>
#include<stack>
#include<queue>
using namespace std;

//二叉树链式存储结构的形式定义
//二叉树结点
typedef struct BiTNode{
char data;//数据
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;

//二叉树的创建
//按先序序列创建二叉树
int CreateBiTree(BiTree &T){
char data;
//按先序次序输入二叉树中结点的值（一个字符）,‘#’表示空树
cin>>data;
if(data == '#'){
T = NULL;
}
else{
T = (BiTree)malloc(sizeof(BiTNode));
//生成根结点
T->data = data;
//构造左子树
CreateBiTree(T->lchild);
//构造右子树
CreateBiTree(T->rchild);
}
return 0;
}
//输出

//二叉树的遍历
//递归算法
void Visit(BiTree T){
if(T->data != '#'){
cout<<T->data; }
}
//先序遍历
void PreOrder(BiTree T){
if(T != NULL){
//访问根节点
Visit(T);
//访问左子结点
PreOrder(T->lchild);
//访问右子结点
PreOrder(T->rchild);
}
}
//中序遍历
void InOrder(BiTree T){
if(T != NULL){
//访问左子结点
InOrder(T->lchild);
//访问根节点
Visit(T);
//访问右子结点
InOrder(T->rchild);
}
}
//后序遍历
void PostOrder(BiTree T){
if(T != NULL){
//访问左子结点
PostOrder(T->lchild);
//访问右子结点
PostOrder(T->rchild);
//访问根节点
Visit(T);
}
}
int main()
{
BiTree T;
CreateBiTree(T);
cout<<”先序遍历：\n”;

PreOrder2(T);
cout<<”\n”;
cout<<"中序遍历：\n";
InOrder2(T);
cout<<”\n”;
cout<<"后序遍历：\n";
LevelOrder(T);
cout<<”\n”;
return 0;
}

4.4.1问题一的输出结果

图14

4.4.2问题二的输出结果

图15

4.4.3问题三的输出结果

图16

5、模型求解

5.1 问题一的求解
参考问题一的方法，画出了近似最优切法图使得利用率较大，得到具体切法如图17：
图17

剩料为400×300的矩形，故

η=1nSiS-S余=1nSi2500×900-300×400=99.94%

5.2 问题二的求解
类似问题一，我们画出了近似最优切法图使得利用率较大，得到具体切法如图18。

根据附件二和假设的条件易求得五边形和六边形的面积分别为：110689.5和128570。而余料为411×311的矩形。可求得：

η=1nSiS-S余=1nSi2380×1630-411×311=89.3%

图18
5.3问题三的求解
类似问题一，我们画出了近似最优切法图使得利用率较大，得到具体切法如图19。

问题三条件里给了两块钢材（4550*1630），但在实际分析过程中发现，只需一块钢材便可够用。经切割后，余料位3950*820的矩形。
图19

6、模型评价
排料是钢构件制造的第一道工序。在这道工序中，不同的排料方案具有不同的材料利用率，而原材料的利用率直接影响产品的成本。对于一个年消耗大量钢材的生产单位，若能够提高原料利用率的1%，那么其节约的钢材成本是可观的。因此，降低废料率提高原材料利用率是钢构件生产企业追求的目标。根据实际情况，板材排料又可分为两种：一是规则形状的零件排料，一是不规则形状的零件排料。
另外由于切割工艺的要求，切割只能实行“一刀切”的工艺（在整料或余料中，从一边的某点到另外一边某点的连线一次切割，但可以在切割下来的板料中再次切割）。
在解决上述规则零件排料和不规则零件排料的问题上，我们采用的是二叉树构造矩阵、启发式算法，优化模型的方法。二叉树在C语言里是个重要的结构，而对于矩形零件的排料，也类似于二叉树的分布方式，故可用二叉树构造模型算法。而启发式算法则是在排料问题中最常用的一种算法，目前研究及使用的都很成熟。优化模型则是运筹学的一个重要分支，运用运筹学的思想，来确定最优模型。
应用二叉树结构、启发式算法来解决钢材排料的实际问题，能一定程度上帮助人们解决问题，但它也有以下的优缺点。
优点：运用矩形包络法将不规则多边形排料问题转化为矩形排料问题，简化的问题。二叉树结构能很好的减少启发式算法计算过程中的迭代次数。
缺点：对于稍复杂点的钢材排料问题，此模型不能高效地解决；矩形包络法里钢材的利用效率不高。

7、参考文献

[1] 戈鹏等,一刀切问题的优化二叉树排样，计算机集成制造系统，第2期：329-337页，2011。
[2] 陈露，实用下料的数学模型，数学的实践与认识，第七期：58-63页，2005。
[3] 姜启源，谢金星，叶俊 ，《数学模型》，北京：高等教育出版社，2011.1
[4] 王爱虎,查建中,王金敏.一种基于二叉树结构表达的矩形物体布局的启发式方法[J].软件学报,1996,4(7):252-257.]
[5] 李兵 ，二维不规则零件排样问题优化研究_，吉林大学，TH140.8：15-17页，2012。
[6]陆敏,多约束条件下的矩形件优化排样研究[D].杭州:浙江大学, 2006.]