第31卷第6期 2003年 6月
华 中 科 技 大 学 学 报(自然科学版) Vol.31 No.6 J.HuazhongUniv.ofSci.&Tech.(NatureScienceEdition)
Jun. 2003
一种矩形件优化排样综合算法
王华昌 陶献伟 李志刚
(华中科技大学塑性成形模拟及模具技术国家重点实验室)
摘要:提出了应用于矩形件优化排样中的关键算法:条料生成算法与填充算法.把二者融合在一起,提出了一种适用于矩形件优化排样的最小残料算法.该算法依据残料大小决定条料,并对空白矩形进行有效填充,可快速得到排样结果.将其与模拟退火算法相结合,能够跳出局部搜索,最终可获得近似总体最优的排样结果.关 键 词:矩形件优化排样;条料生成算法;填充算法;最小残料算法;模拟退火算法中图分类号:TG316 文献标识码:A 文章编号:1671-4512(2003)06-0009-04
矩形件优化排样是指有多种不同矩形件,每种矩形件需要若干个,尽可能多地排放,使给定的矩形板材利用率最高.矩形件优化排样问题实质是一个组合优化的二维布局问题,具有工件种类多、数量大等特点,是计算复杂性最高的一类NP完全问题,至今还无法找到解决该问题的有效多项式时间算法.
国内外已经有不少专家学者在这个领域做了很多研究工作,并且取得了一些成果,例如背包算法[1]、组块技术[2]等,都能够得到较好的排样效果.但是,前者是近似优化算法,后者是局部搜索方法,达不到排样的总体最优.而不经任何处理的模拟退火排样算法虽然可达到近似最优解,却不适合/一刀切0的下料工艺,只适合/正交切割0.
为获得总体最优解,作者提出了最小残料算法.该算法是一种接近最优解的局部搜索算法,适用于矩形件毛坯的优化排样.将其与模拟退火算法思想相结合,能随机地接受某些劣化解,跳出局部极小点,因而有较强的全局搜索能力.同时,可满足排样速度快、板材利用率高的要求和/一刀切0高效率下料工艺,从而较好地解决了现行排样算法中存在的上述问题.
{
intw;M工件宽度 intl;M工件长度
intn;M工件数目}Rect,*pRect;
矩形工件输出坐标如下:typedefstructtagPoint
{
intx1;M当前输出工件左下角点横坐标 inty1;M当前输出工件左下角点纵坐标 intx2;M当前输出工件右上角点横坐标 inty2;M当前输出工件右上角点纵坐标}XPoint,*pXPoint;1.2 约束条件和目标函数
排样的基本目标是使得排样所用的板材数尽可能少,以提高材料的利用率;排样的基本约束条件是矩形件之间不能有相互重叠区域,并且矩形件不能有排出板材的部分.排样规则为每一个矩形件可以被横向排放或者纵排.排样方式为从板材的最左下角开始排到板材的右上角结束一块板材的排样.设板材左下角的坐标为(0,0),(x1i,y1i)和(x2i,y2i)为第i块矩形工件在板材上左下角和右上角坐标,那么他们的关系为
x2i=x1i+Rect[i].l;
y2i=y1i+Rect[i].w,
或者
x2i=x1i+Rect[i].w;y2i=y1i+Rect[i].l,
其中前者为横排时同一矩形件坐标关系,后者为
1 最小残料算法
1.1 数据结构
设板材的长度为l,宽度为w,工件种类数为n,则矩形工件基本信息存储如下:
typedefstructtagRect
收稿日期:2002-11-20.
,(.
10 华 中 科 技 大 学 学 报(自然科学版) 第31卷
纵排时同一矩形件坐标关系,则排样的过程就是根据一定的寻优规则,确定每个矩形工件在板材上的左下角和右上角坐标.
设任意两个参加排样的矩形工件的左下角和右上角坐标分别是(x1s,y1s),(x2s,y2s)和(x1t,y1t),(x2t,y2t),则满足下面任何一种情况,工件不会相互重叠:a.x2s[x1t;b.x1s\x2t;c.y1t\x2s;d.y2t[x1s.
对于任意第i种工件,必须满足下面的约束,否则工件必然越出板材之外:a.x1i\0;b.y1i\0;c.x2i[nl;d.y2i[w;
在满足以上初始约束条件的前提下,使得板材利用率尽可能地高,因此,优化排样的目标函数可表达为
max
i=1
件的首次条料生成过程如图1~4所示.
表1 4种工件的参数
序号1234
n12379
l/mm[1**********]0
w/mm[1**********]
图1 条料生成方案1 图2 条料生成方案2
E(Rect[i].lRect[i].w#
n
Leftwidth[1]=100mm Leftwidth[2]=30mm
Rect[i].n)/([Point[last].x2-w]w),式中,Point[last].x2为最后一个排样工件右上角横坐标;w为板材之间间隔.1.3 条料生成算法
排样问题是二维布局的问题,化二维布局为一维布局,即沿板材的宽度方向不断产生条料.生成条料的方式很多,作者所提出的基于最小残料的条料生成算法能够使板材利用率在宽度方向达到最高,算法描述如下:
a.把所有的工件按照长度从大到小排序;
b.令i=n,k=1;
c.从第i种工件沿着板材宽度方向试探排样;
d.令h=i,若当前第h种工件排样完毕,则令h=h-1,若Rect[h].n不为0,则紧邻以上工件继续试探排样;若为0,则续排下一种工件.同时,每排一个工件,须判定板材宽度是否排完;
e.若板材宽度仍可排,则转d,继续排样,直到不可排.否则,返回剩余宽度Leftwidth[k].若Leftwidth[k]为0,则中止循环,转g,否则,顺序执行;
f.令i=i-1,k=k+1,转c,继续第k种方案排样,直到i=0,中止循环;
g.确认Leftwidth[k]为最优条料生成途径;h.输出此次沿宽度方向的排样结果.
为更加清楚地说明条料生成过程,下面给出一个典型例子.表1所示为排样数据,共有4种工件,板材宽度为1000mm,长度不定.
图3 条料生成方案3 图4 条料生成方案4Leftwidth[3]=70mm Leftwidth[4]=40mm
由图中可知,条料生成方案2的剩余宽度最小.根据算法判断准则,该方案为首次条料最终生成方案.在条料产生的同时,会出现如图中阴影表示的空白矩形,如何对这些空白矩形进行填充,则是算法的关键.
1.4 空白矩形的填充算法
每个空白矩形都可看作一块一定尺寸的板材.由于其尺寸相对较小,针对这种情况,作者开发了专门用于空白矩形排样的填充算法.对未排工件分别进行横向排列和纵向排列的试探,判断是否能够对其进行填充.如果能够填充,则选择横向填充或者纵向填充,并进而得到排样的条料.在完成上述填充过程的同时,在原空白矩形上会产生更多的更小的空白矩形,调用填充算法对其进一步填充,直到任何待排工件都不能再填充为止.算法描述如下:
a.设由条料生成算法得到空白矩形长度和宽度分别为l和w;
b.令i=n-1,若i\0,Rect[i].n>0,判断工件长度是否大于板材宽度,如果是,采用连续横排,转e;否则,顺序执行;
第6期 王华昌等:一种矩形件优化排样综合算法 11
min-l=min{Rect[i].l};
d.分别计算局部利用率,
LocalRatio1=(Rect[i].nRect[i].l#Rect[i].w)/(l1w),
LocalRatio2=(Rect[i].nRect[i].l#Rect[i].w)/(l2w),
并取Max{LocalRatio1,LocalRatio2},由此判定选用连续横排或者连续纵排;
e.对于所产生的空白矩形进行填充,令k=n-1,若k\0,则Rect[k].n>0;对工件k进行试探填充,若满足约束条件,则调用相应空白矩形填充算法,对其填充.对于所产生的新的空白矩形,继续调用填充算法,直到不能填充任何工件为止.填充完毕后,令k=k-1,更新工件数目;
f.判断剩余板材长度l是否大于min-l,如果大于,转b;否则,调用结尾空白矩形填充算法对其填充,更新工件信息.若工件的总数目大于0,产生下一张板材,转c.否则,顺序执行;
g.输出排样结果,包括用于输出图形的坐标文件和每块板材的排样信息.
1.5 最小残料算法
综合条料生成算法与填充算法,导出适合于矩形件排样的最小残料算法,可描述如图5所示
.
模拟退火算法[3]应用的一般形式是:从选定的初始解开始,利用一个新解产生装置和接受准则,重复执行包括/产生新解)))计算目标函数差)))判断是否接受新解)))接受(或者舍弃)新解0这四个任务的试验,不断对当前解迭代,从而达到使目标函数最优的执行过程.
当满足以下条件时,算法中止[4]:
a.算法获得的当前最优解达到预定值;b.算法对所有可能点搜索完毕.
综合最小残料算法和模拟退火算法的最优毛坯排样算法可用图6表示.
图6 模拟退火求解算法流程图
3 排样实例
基于上述算法,给出了两个典型算例.
算例1 表2所示为7种工件的参数,该组工件中,每种工件的数量较多,而且工件尺寸与板材尺寸相对差异较大,工件之间尺寸差异不大,属于中等规模排样.板材的尺寸为4000mm@2900mm,获得的排样结果如图7所示.
表2 7种工件的参数
序号1234567
n[**************]45
l/mm[***********]450
w/mm[***********]0
图5 最小残料算法流程图
2 模拟退火算法的应用
利用最小残料算法的排样存在一个缺陷,那就是在产生条料时,只能按照对工件的长度排序依次产生,虽然能够保证得到当前最小残料的条料,却不能保证第i个工件在该位置是最合适的.
为解决上述问题,作者将模拟退火算法思想应用于最小残料算法中,增加解的空间,一定程度接受劣质解,提高全局搜索能力,可得到近似最优
解图7 排样图(板料利用率为97.75%)
算例2 表3所示为26种工件的参数,该组,
12 华 中 科 技 大 学 学 报(自然科学版) 第31卷
表3 26种工件的参数
序号12
[***********][***********]42526
n[***********]12411122
l/mm[***********][***********][***********][***********][**************]0
w/mm[***********][***********][***********][***********]90
图8 排样图(板料利用率为90.38%)
参
考
文
献
[1]曹 炬,周 济,余 俊.矩形件排样的背包算法.中
国机械工程,1994,5(2):11~12
[2]崔耀东.矩形毛坯下料排样的一种优化算法.机械工
艺师,1998(6):32~33
[3]康立山,谢 云,尤矢勇等.非数值并行算法(第一
册))))模拟退火算法.北京:科学出版社,1994.[4]贾志欣,殷国富,罗 阳等.矩形件排样的模拟退火算
法求解.四川大学学报(工程科学版),2001,33(5):35~38
材尺寸相对差异较为接近,工件之间尺寸差异不大,属于难度较高的排样问题,适用于非批量生产.板材的尺寸为1850mm@1240mm,获得的排样结果如图8所示
.
Asyntheticalalgorithmfortheoptimallayoutofrectangularpart
WangHuachang TaoXianwei LiZhigang
Abstract:Aminimalareaalgorithmfortheoptimallayoutforrectangularpartswasproposedbasedonstripcreationalgorithmandrectangle-fillingalgorithm.Thisalgorithmmeansthechoiceofthecreatedstripde-terminedbytheremainedareaandfillingtherectanglecreatedbythestripefficiently.Tofindglobalopt-imallayoutsolution,thesimulatedannealingalgorithmwasintegratedwiththeminimalarea.Itovercomesthedefectoftheminimalareaalgorithmandjumpsoutofthepoorqualifiedresultpoint.Keywords:rectangularpartsoptimallayout;stripcreationalgorithm;rectangle-fillingalgorithm;minimal
areaalgorithm;simulatedannealingalgorithm
WangHuachang Lect.;StateKeyLab.ofPlasticFormingSimulationandDie&MouldTech.,
HuazhongUniv.ofSci.&Tech.,Wuhan430074,China.
第31卷第6期 2003年 6月
华 中 科 技 大 学 学 报(自然科学版) Vol.31 No.6 J.HuazhongUniv.ofSci.&Tech.(NatureScienceEdition)
Jun. 2003
一种矩形件优化排样综合算法
王华昌 陶献伟 李志刚
(华中科技大学塑性成形模拟及模具技术国家重点实验室)
摘要:提出了应用于矩形件优化排样中的关键算法:条料生成算法与填充算法.把二者融合在一起,提出了一种适用于矩形件优化排样的最小残料算法.该算法依据残料大小决定条料,并对空白矩形进行有效填充,可快速得到排样结果.将其与模拟退火算法相结合,能够跳出局部搜索,最终可获得近似总体最优的排样结果.关 键 词:矩形件优化排样;条料生成算法;填充算法;最小残料算法;模拟退火算法中图分类号:TG316 文献标识码:A 文章编号:1671-4512(2003)06-0009-04
矩形件优化排样是指有多种不同矩形件,每种矩形件需要若干个,尽可能多地排放,使给定的矩形板材利用率最高.矩形件优化排样问题实质是一个组合优化的二维布局问题,具有工件种类多、数量大等特点,是计算复杂性最高的一类NP完全问题,至今还无法找到解决该问题的有效多项式时间算法.
国内外已经有不少专家学者在这个领域做了很多研究工作,并且取得了一些成果,例如背包算法[1]、组块技术[2]等,都能够得到较好的排样效果.但是,前者是近似优化算法,后者是局部搜索方法,达不到排样的总体最优.而不经任何处理的模拟退火排样算法虽然可达到近似最优解,却不适合/一刀切0的下料工艺,只适合/正交切割0.
为获得总体最优解,作者提出了最小残料算法.该算法是一种接近最优解的局部搜索算法,适用于矩形件毛坯的优化排样.将其与模拟退火算法思想相结合,能随机地接受某些劣化解,跳出局部极小点,因而有较强的全局搜索能力.同时,可满足排样速度快、板材利用率高的要求和/一刀切0高效率下料工艺,从而较好地解决了现行排样算法中存在的上述问题.
{
intw;M工件宽度 intl;M工件长度
intn;M工件数目}Rect,*pRect;
矩形工件输出坐标如下:typedefstructtagPoint
{
intx1;M当前输出工件左下角点横坐标 inty1;M当前输出工件左下角点纵坐标 intx2;M当前输出工件右上角点横坐标 inty2;M当前输出工件右上角点纵坐标}XPoint,*pXPoint;1.2 约束条件和目标函数
排样的基本目标是使得排样所用的板材数尽可能少,以提高材料的利用率;排样的基本约束条件是矩形件之间不能有相互重叠区域,并且矩形件不能有排出板材的部分.排样规则为每一个矩形件可以被横向排放或者纵排.排样方式为从板材的最左下角开始排到板材的右上角结束一块板材的排样.设板材左下角的坐标为(0,0),(x1i,y1i)和(x2i,y2i)为第i块矩形工件在板材上左下角和右上角坐标,那么他们的关系为
x2i=x1i+Rect[i].l;
y2i=y1i+Rect[i].w,
或者
x2i=x1i+Rect[i].w;y2i=y1i+Rect[i].l,
其中前者为横排时同一矩形件坐标关系,后者为
1 最小残料算法
1.1 数据结构
设板材的长度为l,宽度为w,工件种类数为n,则矩形工件基本信息存储如下:
typedefstructtagRect
收稿日期:2002-11-20.
,(.
10 华 中 科 技 大 学 学 报(自然科学版) 第31卷
纵排时同一矩形件坐标关系,则排样的过程就是根据一定的寻优规则,确定每个矩形工件在板材上的左下角和右上角坐标.
设任意两个参加排样的矩形工件的左下角和右上角坐标分别是(x1s,y1s),(x2s,y2s)和(x1t,y1t),(x2t,y2t),则满足下面任何一种情况,工件不会相互重叠:a.x2s[x1t;b.x1s\x2t;c.y1t\x2s;d.y2t[x1s.
对于任意第i种工件,必须满足下面的约束,否则工件必然越出板材之外:a.x1i\0;b.y1i\0;c.x2i[nl;d.y2i[w;
在满足以上初始约束条件的前提下,使得板材利用率尽可能地高,因此,优化排样的目标函数可表达为
max
i=1
件的首次条料生成过程如图1~4所示.
表1 4种工件的参数
序号1234
n12379
l/mm[1**********]0
w/mm[1**********]
图1 条料生成方案1 图2 条料生成方案2
E(Rect[i].lRect[i].w#
n
Leftwidth[1]=100mm Leftwidth[2]=30mm
Rect[i].n)/([Point[last].x2-w]w),式中,Point[last].x2为最后一个排样工件右上角横坐标;w为板材之间间隔.1.3 条料生成算法
排样问题是二维布局的问题,化二维布局为一维布局,即沿板材的宽度方向不断产生条料.生成条料的方式很多,作者所提出的基于最小残料的条料生成算法能够使板材利用率在宽度方向达到最高,算法描述如下:
a.把所有的工件按照长度从大到小排序;
b.令i=n,k=1;
c.从第i种工件沿着板材宽度方向试探排样;
d.令h=i,若当前第h种工件排样完毕,则令h=h-1,若Rect[h].n不为0,则紧邻以上工件继续试探排样;若为0,则续排下一种工件.同时,每排一个工件,须判定板材宽度是否排完;
e.若板材宽度仍可排,则转d,继续排样,直到不可排.否则,返回剩余宽度Leftwidth[k].若Leftwidth[k]为0,则中止循环,转g,否则,顺序执行;
f.令i=i-1,k=k+1,转c,继续第k种方案排样,直到i=0,中止循环;
g.确认Leftwidth[k]为最优条料生成途径;h.输出此次沿宽度方向的排样结果.
为更加清楚地说明条料生成过程,下面给出一个典型例子.表1所示为排样数据,共有4种工件,板材宽度为1000mm,长度不定.
图3 条料生成方案3 图4 条料生成方案4Leftwidth[3]=70mm Leftwidth[4]=40mm
由图中可知,条料生成方案2的剩余宽度最小.根据算法判断准则,该方案为首次条料最终生成方案.在条料产生的同时,会出现如图中阴影表示的空白矩形,如何对这些空白矩形进行填充,则是算法的关键.
1.4 空白矩形的填充算法
每个空白矩形都可看作一块一定尺寸的板材.由于其尺寸相对较小,针对这种情况,作者开发了专门用于空白矩形排样的填充算法.对未排工件分别进行横向排列和纵向排列的试探,判断是否能够对其进行填充.如果能够填充,则选择横向填充或者纵向填充,并进而得到排样的条料.在完成上述填充过程的同时,在原空白矩形上会产生更多的更小的空白矩形,调用填充算法对其进一步填充,直到任何待排工件都不能再填充为止.算法描述如下:
a.设由条料生成算法得到空白矩形长度和宽度分别为l和w;
b.令i=n-1,若i\0,Rect[i].n>0,判断工件长度是否大于板材宽度,如果是,采用连续横排,转e;否则,顺序执行;
第6期 王华昌等:一种矩形件优化排样综合算法 11
min-l=min{Rect[i].l};
d.分别计算局部利用率,
LocalRatio1=(Rect[i].nRect[i].l#Rect[i].w)/(l1w),
LocalRatio2=(Rect[i].nRect[i].l#Rect[i].w)/(l2w),
并取Max{LocalRatio1,LocalRatio2},由此判定选用连续横排或者连续纵排;
e.对于所产生的空白矩形进行填充,令k=n-1,若k\0,则Rect[k].n>0;对工件k进行试探填充,若满足约束条件,则调用相应空白矩形填充算法,对其填充.对于所产生的新的空白矩形,继续调用填充算法,直到不能填充任何工件为止.填充完毕后,令k=k-1,更新工件数目;
f.判断剩余板材长度l是否大于min-l,如果大于,转b;否则,调用结尾空白矩形填充算法对其填充,更新工件信息.若工件的总数目大于0,产生下一张板材,转c.否则,顺序执行;
g.输出排样结果,包括用于输出图形的坐标文件和每块板材的排样信息.
1.5 最小残料算法
综合条料生成算法与填充算法,导出适合于矩形件排样的最小残料算法,可描述如图5所示
.
模拟退火算法[3]应用的一般形式是:从选定的初始解开始,利用一个新解产生装置和接受准则,重复执行包括/产生新解)))计算目标函数差)))判断是否接受新解)))接受(或者舍弃)新解0这四个任务的试验,不断对当前解迭代,从而达到使目标函数最优的执行过程.
当满足以下条件时,算法中止[4]:
a.算法获得的当前最优解达到预定值;b.算法对所有可能点搜索完毕.
综合最小残料算法和模拟退火算法的最优毛坯排样算法可用图6表示.
图6 模拟退火求解算法流程图
3 排样实例
基于上述算法,给出了两个典型算例.
算例1 表2所示为7种工件的参数,该组工件中,每种工件的数量较多,而且工件尺寸与板材尺寸相对差异较大,工件之间尺寸差异不大,属于中等规模排样.板材的尺寸为4000mm@2900mm,获得的排样结果如图7所示.
表2 7种工件的参数
序号1234567
n[**************]45
l/mm[***********]450
w/mm[***********]0
图5 最小残料算法流程图
2 模拟退火算法的应用
利用最小残料算法的排样存在一个缺陷,那就是在产生条料时,只能按照对工件的长度排序依次产生,虽然能够保证得到当前最小残料的条料,却不能保证第i个工件在该位置是最合适的.
为解决上述问题,作者将模拟退火算法思想应用于最小残料算法中,增加解的空间,一定程度接受劣质解,提高全局搜索能力,可得到近似最优
解图7 排样图(板料利用率为97.75%)
算例2 表3所示为26种工件的参数,该组,
12 华 中 科 技 大 学 学 报(自然科学版) 第31卷
表3 26种工件的参数
序号12
[***********][***********]42526
n[***********]12411122
l/mm[***********][***********][***********][***********][**************]0
w/mm[***********][***********][***********][***********]90
图8 排样图(板料利用率为90.38%)
参
考
文
献
[1]曹 炬,周 济,余 俊.矩形件排样的背包算法.中
国机械工程,1994,5(2):11~12
[2]崔耀东.矩形毛坯下料排样的一种优化算法.机械工
艺师,1998(6):32~33
[3]康立山,谢 云,尤矢勇等.非数值并行算法(第一
册))))模拟退火算法.北京:科学出版社,1994.[4]贾志欣,殷国富,罗 阳等.矩形件排样的模拟退火算
法求解.四川大学学报(工程科学版),2001,33(5):35~38
材尺寸相对差异较为接近,工件之间尺寸差异不大,属于难度较高的排样问题,适用于非批量生产.板材的尺寸为1850mm@1240mm,获得的排样结果如图8所示
.
Asyntheticalalgorithmfortheoptimallayoutofrectangularpart
WangHuachang TaoXianwei LiZhigang
Abstract:Aminimalareaalgorithmfortheoptimallayoutforrectangularpartswasproposedbasedonstripcreationalgorithmandrectangle-fillingalgorithm.Thisalgorithmmeansthechoiceofthecreatedstripde-terminedbytheremainedareaandfillingtherectanglecreatedbythestripefficiently.Tofindglobalopt-imallayoutsolution,thesimulatedannealingalgorithmwasintegratedwiththeminimalarea.Itovercomesthedefectoftheminimalareaalgorithmandjumpsoutofthepoorqualifiedresultpoint.Keywords:rectangularpartsoptimallayout;stripcreationalgorithm;rectangle-fillingalgorithm;minimal
areaalgorithm;simulatedannealingalgorithm
WangHuachang Lect.;StateKeyLab.ofPlasticFormingSimulationandDie&MouldTech.,
HuazhongUniv.ofSci.&Tech.,Wuhan430074,China.