二维矩形件装箱(two-dimensional rectangular bin packing, 简称2RBP)问题是切割排样问题的一个重要研究分支^[1], 在众多工程应用领域中, 例如钣金件加工、玻璃深加工、家具制造、服装剪裁和集成电路排布等行业都存在大量此类下料排样问题及一些成熟的应用软件, 如玻璃排样优化软件Optima和PrefectCut.

单一尺寸二维矩形件装箱(two-dimensional rectangular single bin-size bin packing, 简称2RSBSBP)问题, 描述为给定单规格固定尺寸且数量无限制的大矩形板材, 其X轴方向宽度为W, Y轴方向高度为L, 需要下料的小矩形工件为n种, 每种工件X轴方向宽度为w_i, Y轴方向高度为l_i, 数量为m_i, i∈[1, n], 要求在板材上进行合理布局, 使得下料耗费板材数量最少, 即最大化板材利用率.实际排样过程常常受限于原材料本身属性和切割工艺约束, 而产生不同的2RBP问题分类.Lodi等人^[2]将2RBP问题定义为4种不同类型, 即2BP|O|G、2BP|R|G、2BP|O|F和2BP|R|F, 这里, R代表工件可以旋转90°, O代表工件固定不能旋转, F代表工件可以自由排布, G代表排样满足“一刀切”, 即切割线平行于矩形板材的两边, 并一刀将板材分割为两个独立的矩形工件.本文研究的2RSBSBP问题属于2BP|R|G这个问题分类^[3], 要求使用同一规格矩形板材, 工艺满足工件可旋转和一刀切约束, 因此, 该问题简称2RSBSBP|R|G, 以上约束对排样过程提出了特殊要求.

2BP已被证明属于NP完全问题^[4], 其计算复杂度随着问题规模的扩大呈指数方式增长.当前, 对2BP的求解算法主要包括精确求解算法、智能搜索算法和启发式算法.文献[5, 6]基于分支定界法分别给出了2BP|O|G、2BP|R|G问题的下界, 通过上界与下界进行比较, 可以衡量算法的性能.Liu等人^[7]基于动态规划的启发式算法求解2BP|×|G问题, 获得了较快的求解速度.然而, 精确求解算法在求解大规模下料问题时计算复杂度过高, 在实际问题中难以直接应用.

遗传算法^[8]、模拟退火算法^[9]、粒子群算法^[10]、禁忌搜索^[2]等智能搜索算法也广泛应用到排样问题求解中, 这些算法具有全局寻优特性, 能较快地处理大规模排样问题, 并同时得到令人满意的解.但是, 由于算法具有随机性, 优解和良解不可复现, 以及搜索很容易陷入局部最优, 因而大大限制了其在工程上的应用.

为了求解大规模矩形件排样问题, 许多启发式算法相继被提出.张德富等人^[11]针对可旋转的一刀切条带排样问题, 提出启发式的递归排样算法, 之后其针对矩形条带排样又提出了一种砌墙式启发式算法^[12], 该算法通过局部搜索尝试改变工件的填充顺序, 从中选择最好的结果, 相比元启发式算法, 这两种启发式算法具有明显优势.蒋兴波等人^[13]提出了底部左齐择优匹配(lowest-level left align best fit)算法并结合遗传算法(genetic algorithm)解决二维条带装箱问题.彭碧涛等人^[14]提出了求解二维矩形条带装箱问题的树形迭代搜索方法, 并选择最高装载适应度的矩形来装载空间.曹大勇等人^[15]结合一维装箱问题的最优匹配递减算法和多递归层算法, 构造了适合2BP|O|G问题的两阶段算法.

国内研究主要集中在条带排样上, 对于2BP|×|G的研究文献较少.许多国外文献将矩形件排样求解过程分为一阶段排样算法和两阶段排样算法.Berkey和Wang^[16]针对2BP|O|G提出了FFF(finite first fit)算法, 将条带直接在板材上生成, 将工件排放在最低的条带上, 是一阶段排样算法, 而提出的FBS(finite best strip)算法是两阶段排样算法, 把工件排列到固定长度的条带上, 再将条带排布在板材上.Lodi等人^[17]扩展FFF和FBS算法到2BP|R|G问题, 之后针对2BP|×|G提出了两阶段近似算法^[2], 首先针对条带排样提出了FC(floor ceiling)算法和KP(knapsack problem)算法, 将问题转化为1BP, 然后使用禁忌搜索对排样结果进行动态的邻域搜索.

启发式搜索算法强烈依赖于启发式规则, 搜索过程可以结合快速、有效的元启发式规则和算法来提高搜索效率.Polyakovsky等人^[18]针对2BP|×|G提出的GBL(guillotine bottom left)算法优先选择面积最大的工件放在待排区域的左下角, 同时又提出了一种基于代理(agent-based)的排样算法, 该算法采用GBL的排样规则, 通过代理的选择过程和适应度评价方法来驱动代理选择工件进行排样, 从而消除局部最优解.Parreño等人^[19]针对二维和三维单规格装箱问题提出了基于贪婪随机搜索过程(greedy randomized adaptive search procedure)和变邻域搜索(variable neighbourhood descent)相结合的混合式排样算法, 该算法结合VND算法的结构, 在启发式策略构造过程中以最大化的板材平均利用率为目标.文献[20, 21]针对单规格一刀切排样问题, 将求解过程划分为两个步骤, 首先按照工件的长、宽和面积等参数对工件进行排序, 利用贪婪搜索选择最好的一次排样结果作为问题初始解, 第2阶段利用VND、SNS(stochastic neighborhood structures)等算法提高求解质量.Alvarez-Valdes等人^[22]针对多规格装箱问题提出了路径优化链接随机搜索(path relinking GRASP)算法, 将排样问题求解分为构建和后处理两个求解阶段, 通过后处理可以极大地改善第1阶段的求解质量.Charalambous等人^[23]提出的CH (constructive heuristic)算法使用平均工件面积准则指导工件选择, 并进一步提出CHB(CH with bias)、CHBP (CHB with postprocessing)算法.Krzysztof^[24]基于树形结构存储排样过程, 提出了3种插入启发式算法及其后调整算法.Hong等人^[9]针对多规格矩形件的2BP|O|G问题, 提出一种分支搜索与模拟退火算法相结合的混合式启发算法HHA(hybrid heuristic algorithm), 该算法获得了Class系列案例2BP|O|G问题的最好实验结果.

对于较多的工件种类和工件数量的处理, 组化技术给二维排样优化问题带来了新的求解思路.Kröger^[25]提出了元矩形(meta-rectangle)这一概念, 即在排样前, 若干具有相同变长的矩形件可以组合成一个新的组合式矩形件进行排样.崔耀东^[26]提出在金属薄板先剪后冲下料时, 将各种不规则形状毛坯排成大小各异的矩形组块, 同一张板材板上可以排列多个矩形组块进行下料, 以提高板材利用率.何霖等人^[27]提出了基于组化规则的卷型材一刀切排样方法, 实验证明组块策略可以显著提高排样质量.然而, 组化技术作用机制方面还有待研究, 组化技术在应用时也有明显缺陷.其一, 工件在成组后, 待排样矩形件队列长度高速膨胀, 例如100个矩形工件两两组化后, 理论上可以形成近10 000个新二元组块, 这将导致搜索空间急剧扩大.其二, 在挑选组块进行排样时, 单个较大面积的矩形工件(面积小于二元组块)因未被较早选中, 降低了后续排样的灵活性, 导致总利用率下降.

本文针对2RSBSBP|R|G问题提出了一种基于组化技术的构造启发式算法, 即大小工件分治择优匹配(bigitem smallitem divide-and-conquer best-fit, 简称BSDBF)启发式算法, 其中, 工件的宽和高都分别大于板材宽和高一半即为大工件(bigitem), 其余为小工件(smallitem).算法在排样中大胆使用了二元组件, 二元组件具有优良的启发特性和搜索空间剪枝特性, 而不需要多元组件; 其次, “大小工件分治”策略是组化技术的关键补充, 可以避免某些单个大工件被延后排布的不利局面; 再次, 配合组块的快速举荐算法, 可以较大地提升搜索效率.最后, 通过改进的二分法排样和后处理算法, 兼顾了单块板材和整体利用率.进一步的实验结果表明, 该启发式算法在求解单规格一刀切矩形装箱问题上具有很高的求解质量和搜索效率.

本文第1节对BSDBF启发式算法进行描述.第2节对BSDBF启发式算法进行分析和实现.第3节对国际上的标准案例进行计算实验, 并与其他已发表论文进行结果对比.第4节对算法参数进行分析.第5节总结全文, 提出进一步的研究方向.

对于2RSBSBP|R|G问题的求解, 要充分考虑工件面积对整个排样结果的影响, 结合工件排放规则, 对工件选择次序进行优化, 不断调整排放顺序, 最终搜索到最优的排样方案.构造启发式算法时可以考虑如下一些重要的启发特征.(1) 优先使用面积大的工件进行排样, 面积小的工件在后续排样中将具有更高的灵活性.(2) 单块板材排样方案利用率相同的条件下, 选择切片数量最少的排样方案, 有助于提升后续排样方案的利用率.(3) 大工件的使用对排样结果有重要影响.

本文在前期研究的基础上, 构造了BSDBF启发式算法, 该算法由前置处理、主体搜索和后处理算法组成, 如图 1所示.数据前置处理中, 利用工件和板材的几何相似特征, 构造排样组块.主体搜索过程中, 基于大小工件分治策略, 快速举荐最佳适应度的组块进行排放, 根据切割选择等大量启发规则, 递归执行排样与切割, 动态构造排样区域的局部解, 并依据废料率进行快速回溯.其外围采用动态二分法遍历单块板材的排样方案, 并根据启发规则贪心选择整个排样方案.后处理算法依据板材拆分规则对排样方案进行拆分和重组, 二次优化排样结果, 提升总利用率.算法采用了确定性搜索机制, 获得的优解可以复现.

图 1

Fig. 1

Fig. 1 Algorithm description 图 1 算法描述

定义1(组化).将具有相同几何外观尺寸的矩形工件通过边长的紧密贴合, 组合成更大面积的矩形组件, 同时满足矩形组件的长和宽分别小于板材的长和宽, 其中单个工件和矩形组件统称为组块(group), 其X轴方向宽度为gw, Y轴方向高度为gl, 只能使用组块作为唯一的排样单元.

定义2(组化粒度).这是指组块中包含的工件数量, 本文取值为1或者2, 其中, 1代表工件未组合即一元组块, 2代表工件两两组合, 即二元组块.

定义3(待排矩形区r).这是指板材上每次排放组块的矩形区域, 其X轴方向宽度为rw, Y轴方向高度为rl, 待排矩形区分为A、B、C这3种类型.

(1) 初始矩形板材定义为C类型, 以其左下角为坐标原点(0, 0);

(2) 每次排放组块后分割出的子板材, 其左下角坐标为(rx, ry), 定义与组块处于切割线同一侧的子板材为A类型, 与组块处于切割线不同侧的子板材为B类型.

定义4(组块适应度).用来衡量组块和待排矩形区的匹配程度, 以此来举荐具有高适应度值的组块进行排样.

定义5(组块空间GroupList).用来保存所有待排组块的集合.

定义6(废料W).对于组块排放后分割出的待排矩形区, 检查是否能够放得下待排组块中长最小且宽也最小的那个组块, 如果放不下, 该区域就成为了板材上的废料.

算法的前置处理要求对所有待排工件进行组化操作, 组块构造算法描述如下.

算法1. Grouping.

输入:初始板材raw, 工件集合itemList, 工件数量集合itemAmountMap, 组化类型groupType, 0表示组化后X轴变长, 1表示组化后Y轴变长;

输出:组块空间GroupList.

Step 1.初始化:设定最大组化粒度为2.

Step 2.得到组化粒度为1的所有Group.遍历所有待排工件itemList, 先设定组化粒度为1, 将除正方形以外的所有工件旋转90°, 检查旋转后工件的长和宽分别小于等于板材raw的长和宽, 如果为true, 则该旋转后工件满足板材尺寸要求.将所有旋转前和旋转后满足尺寸要求的工件存放在GroupList中.

Step 3.得到组化粒度为2的所有Group.遍历GroupList中所有Group, 按照groupType两两合并, 仅当相同规格的Group数量大于1时才能与自身组合.groupType为0, 则按照Group的Y轴尺寸进行贴合, 组化后X轴尺寸变长; groupType为1, 则按照Group的X轴尺寸进行贴合, 组化后Y轴尺寸变长.检查两两合并后的组块的长和宽分别小于等于板材raw的长和宽, 将所有合并后满足尺寸要求和结构要求的Group也存放在GroupList中, 并检查该Group是否已经存在于GroupList中, 以便剔除相同结构的Group.

Step 4.返回工件组化的结果GroupList.

使用组块代替工件进行排样, 依据组块适应度择优匹配规则, 优先选择适应度大的组块排放在待排矩形区.组块排放依据左下优先BL(bottom-left)原则进行放置, 如图 2(a)所示的排放图, 将二维笛卡尔坐标系的原点设在C类型板材r₀的左下角, 对板材的切割路径定义如下.

图 2

Fig. 2

Fig. 2 Group location and cutting style 图 2 Group定位及切割方式

(1) 当排放的Group和r₀两条边都不相等时, 有两条满足“一刀切”的切割路径, 一条是沿着Group的上边线水平切割(horizontal cut, 简称HC), 如图 2(b)所示; 另一条是沿着Group的右边线垂直切割(vertical cut, 简称VC), 如图 2(c)所示.任意一种切割方式都会将r₀分割成两个面积更小的矩形区域r₁和r₂, 两块子区域面积设定为r₁＜r₂.

(2) 如果Group有一边与板材的某一边长度相等, 则r₀只会切割出一个矩形区r₁.

(3) 如果Group与板材任一边都相等, 则r₀不需要进行切割.

板材排样经过多次组块排放和切割, 最终产生如图 3(a)所示的排样图.该排样过程是一个典型的树形递归搜索过程, 如图 3(b)所示, 采用排样二叉树描述该过程:在递归排样过程中会不断切割出待排矩形区r, r对应于排样二叉树一个节点p, 其中, 根节点为C类型, 其他节点为A或B类型.分支节点中HC、VC分别代表r采用的切割方式, 叶子节点中数字代表最终排放的组块, W代表产生的废料.

图 3

Fig. 3

Fig. 3 Layout and binary layout tree 图 3 排样图和排样二叉树

首先, 基于组化规则, BSDBF启发式算法通过比较组块适应度, 快速择优推荐组块进行排放, 构造排样区域的局部解.然后, 基于废料率进行深度优先递归搜索, 寻找单块板材的布局方案.当搜索过程累加的废料面积大于预期废料率所设定的废料面积阈值时, 板材当前排样方案寻找失败, 根据废料率快速回溯, 重新选择组块进行排样, 回溯点选择为C类型或A|B类型待排矩形区.BSDBF启发式算法描述如下.

在组块集合中, BigItem类型组块是仅包含BigItem类型工件的一元组块.在所有排样方案中, 不可能出现两个BigItem同时占用一块板材的情况.如果BigItem越靠后使用, 就越会出现单个BigItem占据一块板材, 且缺少面积较小组块进行填充的现象, 导致后续板材利用率偏低, 对整个排样结果有较大影响.因此, 针对C类型待排矩形区进行排样时, 设计了基于BigItem的最佳适应度择优匹配启发规则如下.

(1) 首先遍历GroupList, 挑选出BigItem类型的一元Group, 并保存在集合BigItemGroupList中, 按照适应度函数fitness1的值对BigItemGroupList进行降序排列.fitness1适应度函数定义如下:

(2) 然后遍历GroupList, 挑选出非BigItem类型的Group, 并保存在集合NoBigItemGroupList中, 按照适应度函数fitness2的值对NoBigItemGroupList进行降序排列.fitness2适应度函数定义如下:

(3) 对C类型待排矩形区排样时, 优先从BigItemGroupList中推荐适应度值大的Group进行排放, BigItem排放完之后再从NoBigItemGroupList中推荐适应度值大的Group进行排放.假定对于C类型待排矩形区可使用的待排Group总数量为k, 则搜索区间为[1, k].

由于切割过程会出现数量众多且面积不等的A|B类型待排矩形区, 因此, 在对A|B类型待排矩形区进行排样时, 如果以最佳适应度值作为标准选择组块进行排放, 则需要针对每一个A|B类型待排矩形区反复计算组块适应度值, 并反复进行适应度值的排序.这种以组块适应度值排序作为递归计算的原子计算单位, 会极大地影响整个算法的计算速度.因此, 针对A|B类型待排矩形区排样时, 设计了基于双队列推荐适应度择优匹配启发规则

如下.

(1) 将GroupList中所有待排Group按照高降序、相同高按宽降序进行排序, 以此方法构建基于高和宽双重选择的双队列存储结构, 只需执行一次排序, 所有Group始终保持固定顺序不变.

(2) 对任意A|B类型待排矩形区进行排样, 在双队列中先按高从前向后查找Group, 再按宽从前向后查找Group, 实现对不同面积待排矩形区都有效的Group快速排序体系, 推荐具有高优先级的Group进行排放.

(3) Group对A|B类型待排矩形区的优先级匹配规则定义如下.

第1级Group两边长与板材两边长都相等;

第2级Group任一边长与板材任一边长相等;

第3级满足以上条件, 面积大的Group优先;

第4级满足以上条件, 包含工件少的Group优先;

第5级满足以上条件, 适应度函数fitness3值大的Group优先.fitness3适应度函数定义如下:

(4) 在对A|B类型待排矩形区进行排样时, 设置每块排样区域搜索Group的最大数量为limit, 可以计算出A|B类型待排矩形区对Group的整个搜索空间为limit^(m-1), 其中, m代表单块板材切割次数.

排样二叉树的每个节点最多可以选择两种切割策略, 利用约束剪枝规则, 尽量使用一种切割方式, 减少切割选择次数, 启发式切割规则如下.

(1) 如果Group任意一边和板材任意一边相等, 只选一种切割;

(2) 当板材是A|B类型且和Group都是正方形时, 只选垂直切割;

(3) 默认优先选用垂直切割方式, 只有垂直切割排样方案失败, 才会选择水平切割方式进行尝试;

(4) 分别计算两种切割方式切割后形成的两块子板材的面积差, 优先选择面积差小的切割方式.

每一个节点切割后最多出现两个分支, 优先选择面积小的分支进行排样.根据不同的待排矩形区类型, 选择不同的组块快速推荐策略, 优先推荐适应度值高的组块进行排放, 构造排样的局部解, 并通过废料率评估局部解和全局解的关系.BSDBF启发式算法采用了基于深度优先的递归搜索, 具体步骤如下.

算法2. BSDBF.

输入:待排矩形区r, 组块空间GroupList, 工件集合itemList, 工件数量集合itemAmountMap, 切割方式divide, 1表示垂直切割, 2表示水平切割;

输出:单块板材排样结果solution.

Step 1.初始化:

   板材预期废料率为λ, 计算单块板材允许的废料面积S_λ=WLλ, S为单块板材累计总废料面积.初始化λ=0, 先进行无废料排样, 如果失败, 则设定λ=0.5, 再尝试有废料排样.

Step 2.执行group的排放, 检查废料率的合法性, 返回布尔值isRectLayout

  if (r不能放得下最小工件){

   if (r是废料){

    if (S＞S_λ)

     return false

     else

     return true

   }

}

if (r不是废料){

 if (r是C类型){

   基于BigItem适应度择优匹配规则, 将GroupList中Group按适应度值降序保存到集合

   fitnessList中

 }else if (r是A|B类型){

   基于双队列推荐适应度择优匹配规则, 将GroupList中Group按适应度值降序保存到

   集合fitnessList中

}

for (遍历所有fitnessList){

  针对不同类型的r, 从相应fitnessList中选择适应度高的Group进行排放, 依据启发式切割规

  则进行r的切割, 设定切割方式为divide.

  依据divide值, 执行Step 3, 将r进行分割, 将结果赋值给isRectLayout

 if (isRectLayout)

   将排样结果添加到solution

 if (!isRectLayout)

   使用另一种切割方式, 执行Step 3, 将r进行分割, 将结果赋值给isRectLayout,

 if (isRectLayout)

   将排样结果添加到solution

  }

 }

 返回isRectLayout

Step 3.依据divide值, 对r进行分割操作, 检查是否排样成功, 返回布尔值isRectDivide

 if (Group刚好填充满r)

   将Group所包含的工件添加到排样结果集newSolution中

 if (Group未填充满r){

   依据divide值选择切割方式, 分割出两个待排矩形区r1、r2, 面积S_r1＜S_r2

   if (S_r1＞0)

     优先r1排样, 执行Step 2, 将结果赋值给isRectDivide

   if (isRectDivide)

     继续r2排样, 执行Step 2, 将结果赋值给isRectDivide

   if (isRectDivide)

      Group排放在r的左下角, 并将Group中包含的工件添加到newSolution中

 }

 返回isRectDivide

第2.2节提出了BSDBF启发式搜索算法, 可以获得单块板材的排样方案, 但单块板材的初次排样方案不一定是最优的局部方案, 也不一定能构成最优的整体排样方案, 因此要对单块板材的排样方案进行评估和进一步选择.本文设置了如下两种排样方案的择优规则.

(1) 最佳利用率优先:在单块板材所有排样方案中, 板材利用率最大的排样方案优先选择.

(2) 最少工件个数优先:在满足(1) 的条件下, 当利用率相同时, 板材使用工件数量最少的排样方案优先选择.

在BSDBF启发式算法外围, 采用了贪婪选择算法, 以获得单块板材的优解, 并构造整体排样方案的初始解.贪心选择排样方案具体步骤如下.

算法3. GreedySearch.

输入:板材集合materialList, 组块空间GroupList, 工件集合itemList, 工件数量集合itemAmountMap;

输出:初始整体排样结果solutionList.

Step 1.根据单块板材初次排样方案, 计算单块板材实际废料率.

Step 2.如果废料率为0, 则是无废料排样, 扩大k值和limit值以扩大Group搜索范围, 继续进行无废料方案搜索, 依据最少工件个数优先原则, 记录工件个数最少的无废料排样方案作为最优解bestSolution.

Step 3.如果废料率不为0, 则是有废料排样, 采用了改进的动态二分法, 逐步降低预期废料率λ, 从而获得高利用率的排样方案, 具体步骤如下.

(1) 设定预期废料率上限为λ_high=0.5, 下限为λ_low=0, 二分法上下限精度为e, 初始值e₁=0.12, 开始二分法排样.

(2) 利用BSDBF启发式算法获得单块板材的一次排样结果, 将当前废料率最小的排样方案保存到bestSolution中, 若废料率相同, 则保存工件数量最少的排样方案到bestSolution中.

(3) 计算本次排样结果的真实废料率, 重新设定废料率上下限, 继续执行(2), 直到满足条件$|{{\lambda }_{high}}-{{\lambda }_{low}}|＜e,$则

二分法终止.

(4) 此后, e按照公式e_i+1=e_i+0.01×(n-4) 产生, n等于0, 1, 2, 3, 逐步降低e, 并遍历所有e值, 继续执行(1).遍历完毕后, 将bestSolution作为本次有废料排样的最好排样结果.

Step 4.对materialList中所有板材依次进行排样, 通过组合所有单块板材排样方案结果bestSolution, 获得整体排样结果的初始解solutionList.

为了获得整个排样方案的优解, 需要对不同板材的排样结果进一步协调, 以提升整体利用率.因此, 本文基于大小工件分治策略和利用率优劣集划分策略, 设计了排样方案的后处理算法, 详细步骤如下.

算法4. PostProcess.

输入:初始整体排样结果;

输出:后处理最终排样结果.

Step 1.判断整个排样方案总废料面积, 当总废料面积大于一块板材面积时, 即启动排样后处理的检查机制.

Step 2.检查初始排样结果是否存在BigItem, 如果存在, 选择Step 3进行求解, 如果不存在, 选择Step 4进行求解.

Step 3.包含BigItem时, 重排策略如下.

(1) 找出单片利用率等于100%且包含BigItem的排样结果, 对该块板材排样结果进行锁定.当其余未锁定板材的数量大于1时, 启动局部重排.

(2) 将未锁定的板材排样结果组成重排序列, 拆分以上排样结果, 还原工件到待排样Group中, 将重排时的组化粒度设定为1和2, 分别进行排样尝试, 保存利用率最好的后处理结果.

(3) 当上一次后处理排样结果利用率提高小于0.005时, 则停止后处理.

Step 4.不包含BigItem时, 根据总利用率选择优集和劣集进行后处理, 重排策略如下.

(1) 对板材排样结果以当前总利用率为界限, 大于为优解, 小于为劣解, 将优解集合按利用率降序排序, 将劣解集合按利用率升序排序.

(2) 选择优集利用率最高的前1/3方案, 选择劣集利用率最低的前1/3方案, 组成重排序列, 拆分以上排样结果, 还原工件到待排样Group中, 将重排时的组化粒度设定为1和2, 分别进行排样尝试, 保存利用率最好的后处理结果.

(3) 当上一次后处理排样结果利用率提高小于0.005时, 则停止后处理.

Step 5.比较后处理前后的排样结果, 选择利用率高的作为最终排样结果.

基于Java语言编程, 我们开发了单规格一刀切矩形件排样软件, 且未使用多线程技术进行算法实现.算法测试平台为笔记本电脑, 操作系统为32位Windows 7 SP1, CPU为Core i3 2.13 GHz, 内存为3GB.为了检验算法的有效性, 我们测试了国际上流行的单规格矩形件排样通用测试案例.

表 1选择了cgcut、gcut和ngcut这3个系列的通用测试案例, 其中, 案例cgcut来源于Christofides和Whitlock(1977)^[28], 包含3个案例, 案例gcut来源于Beasley(1985a)^[29], 包含13个案例, 案例ngcut来源于Beasley (1985b)^[30], 包含12个案例.与其他文献中的算法进行了结果对比, 见表 1.

表 1(Table 1)

Table 1 Comparisons with other algorithms for cgcut, gcut and ngcut 表 1 cgcut、gcut和ngcut系列案例结果与其他算法对比情况 算例集 算例数量 计算板材数 VND-3NE-H[21] VND-3NE-V[21] SNS-3NE-H[21] SNS-3NE-V[21] BSDBF cgcut 3 23 24 23 24 23 gcut 13 103 103 101 101 98 ngcut 12 31 31 32 32 30

Table 1 Comparisons with other algorithms for cgcut, gcut and ngcut 表 1 cgcut、gcut和ngcut系列案例结果与其他算法对比情况

在表 1的实验结果中, cgcut系列使用板材数量等于文献报道的测试结果, gcut和ngcut系列使用板材数量均低于上述文献报道的测试结果.所有案例能在平均1s时间内完成, 说明本算法对小规模排样具有较高的求解质量.

表 2选择了Class系列10组通用测试案例, 每组Class分别有50个测试案例, 10组总计500个测试案例.其中, 前6组案例来源于Berkey和Wang(1987)^[16], 后4组案例来源于Martello和Vigo(1998)^[5].另外, 所有Class系列测试案例板材全部是正方形, 板材尺寸在10×10~300×300之间取值.每个Class系列分别包含10个20个工件、40个工件、60个工件、80个工件和100个工件的案例.Class系列测试案例包含的工件种类多, 相同种类的工件数量较少, 并且包含了二维排样的各种极端情况, 能够很好地反映算法的求解质量.Class系列测试案例与其他文献中的算法进行结果对比情况见表 2, 与其他较好结果的算法详细数据对比情况见表 3.

表 2(Table 2)

Table 2 Comparisons with other algorithms for Class 表 2 Class系列案例结果与其他算法对比情况 算法 算法来源 计算板材数 平均偏差(2007)[31] 处理器 FC Lodi, et al.(1999)[2] 1.089 SG 195MHz KP Lodi, et al.(1999)[2] 7 297 1.085 SG 195MHz TSKP Lodi, et al.(1999)[2] 7 101 1.055 SG 195MHz VND-3NE-V Chan, et al.(2010)[21] 7 124 Core2 2 GHz SNS-3NE-V Chan, et al. (2010)[21] 7 110 Core2 2 GHz GBL Polyakovsky, et al.(2009)[14, 18, 19] 7 367 1.094 Athlon XP 2800 A-B Polyakovsky, et al.(2009)[18] 7 063 1.036 Athlon XP 2800 CH Charalambous (2011)[23] 7 191 1.059 Core i3 2.13 GHz CHB Charalambous (2011)[23] 7 117 1.050 Core i3 2.13 GHz CHBP Charalambous (2011)[23] 7 064 1.037 Core i3 2.13 GHz CFIH Krzysztof (2013)[24] 7 100 1.044 Core2 2.33 GHz CFIH+J4 Krzysztof (2013)[24] 7 080 1.040 Core2 2.33 GHz BSDBF 7 051 1.026 Core i3 2.13 GHz

Table 2 Comparisons with other algorithms for Class 表 2 Class系列案例结果与其他算法对比情况

表 3(Table 3)

Table 3 Comparison of detailed results for Class 表 3 Class系列案例详细数据对比情况 算例集 排样工件数量 算例数量 计算板材数 CHBP CFIH+J4 BSDBF Class 1 20 10 66 66 66 40 10 129 129 129 60 10 195 195 195 80 10 271 271 270 100 10 314 314 313 总数 975 975 973 Class 2 20 10 10 10 10 40 10 19 19 19 60 10 25 25 25 80 10 31 32 31 100 10 39 39 39 总数 124 125 124 Class 3 20 10 48 48 49 40 10 94 94 93 60 10 136 136 137 80 10 186 185 186 100 10 223 223 221 总数 687 686 686 Class 4 20 10 10 10 10 40 10 19 19 19 60 10 25 25 23 80 10 33 33 30 100 10 38 38 37 总数 125 125 119 Class 5 20 10 59 59 59 40 10 115 117 115 60 10 176 175 175 80 10 240 241 240 100 10 282 281 282 总数 872 873 871 Class 6 20 10 10 10 10 40 10 18 18 17 60 10 21 21 21 80 10 30 30 30 100 10 34 34 32 总数 113 113 110 Class 7 20 10 52 52 52 40 10 104 106 105 60 10 148 151 147 80 10 211 214 213 100 10 255 258 254 总数 770 781 771 Class 8 20 10 53 53 53 40 10 105 105 105 60 10 150 152 150 80 10 210 211 211 100 10 258 258 259 总数 776 779 778 Class 9 20 10 143 143 143 40 10 275 275 275 60 10 435 435 435 80 10 573 573 573 100 10 693 693 693 总数 2 119 2 119 2 119 Class 10 20 10 41 42 41 40 10 73 73 73 60 10 100 101 100 80 10 130 129 128 100 10 159 159 158 总数 503 504 500 总计 7 064 7 080 7 051

Table 3 Comparison of detailed results for Class 表 3 Class系列案例详细数据对比情况

在表 3所示的实验结果中, 500个测试案例使用板材总数量为7 051, 均低于各类文献报道的测试结果.其中, Class 1、Class 3、Class 4、Class 5、Class 6、Class 10系列案例使用板材数量低于文献记录, Class 2、Class 9系列案例使用板材数量等于文献记录, Class 7、Class 8系列案例使用板材数量稍高于文献记录, 进一步说明本算法对多类型工件的小规模排样具有很高的求解质量.

BSDBF算法求解2BP|R|G问题的平均偏差值为1.026, 见表 2, 相较于几种文献报道的算法, 均取得了微弱领先的优势.文献[9]针对2BP|O|G问题, 获得更低的平均偏差值1.024.常规而言, 2BP|O|G的解构造比2BP|R|G问题更加困难, 但2BP|R|G问题比2BP|O|G问题的搜索空间更大.目前尚不清楚, 针对两类问题的算法之间是否存在可折算的比较关系.然而, 文献[9]提出的混合式元启发算法和可改变的分数选择策略, 对2BP|×|G问题的求解极具借鉴意义.Class系列部分测试案例的排样图如图 4所示, 其中阴影部分为未排样区域.

图 4

Fig. 4

Fig. 4 Packing result for Class 496 图 4 Class 496的排样结果

表 4的测试数据参考了来源于Hopper和Turton^[32]的21个C系列案例, 该21个案例利用率均为100%.我们将21个C系列案例的板材数量和工件数量分别扩大10倍, 构造了21个10C系列案例10C1P1~10C7P3, 这些案例仍可满足最优解的利用率为100%.10C系列案例的测试结果见表 4.

表 4(Table 4)

Table 4 Computational results (BSDBF) of 21 instances for 10C 表 4 10C系列案例21组算例计算结果(BSDBF) 算例 排样工件数量 板材高度 板材宽度 计算结果 板材数 利用率 计算时间(s) 10C1P1 160 20 20 10 100 ＜0.1 10C1P2 170 20 20 10 100 ＜0.1 10C1P3 160 20 20 10 100 ＜0.1 10C2P1 250 40 15 10 100 ＜0.1 10C2P2 250 40 15 10 100 ＜0.1 10C2P3 250 40 15 10 100 ＜0.1 10C3P1 280 60 30 10 100 ＜0.1 10C3P2 290 60 30 10 100 ＜0.1 10C3P3 280 60 30 10 100 ＜0.1 10C4P1 490 60 60 10 100 ＜0.3 10C4P2 490 60 60 10 100 ＜0.1 10C4P3 490 60 60 10 100 ＜0.1 10C5P1 730 90 60 10 100 ＜0.1 10C5P2 730 90 60 10 100 ＜0.1 10C5P3 730 90 60 10 100 ＜0.1 10C6P1 970 80 120 10 100 ＜0.2 10C6P2 970 80 120 10 100 ＜0.2 10C6P3 970 80 120 10 100 ＜0.4 10C7P1 1 960 240 160 10 100 ＜3.7 10C7P2 1 970 240 160 10 100 ＜0.3 10C7P3 1 960 240 160 10 100 ＜0.8

Table 4 Computational results (BSDBF) of 21 instances for 10C 表 4 10C系列案例21组算例计算结果(BSDBF)

在表 4所示的实验结果中, 21个10C系列案例均能获得利用率为100%的最优解, 表明算法对无废料测试案例可以很快找到其最优解, 具有良好的爬山特性.部分测试案例的排样图如图 5所示.

图 5

Fig. 5

Fig. 5 Packing result of 10C7P3 图 5 10C7P3的排样结果

BSDBF算法中涉及到如下两个重要参数:一是二分法排样的上下限精度e, 二是A|B类型待排矩形区搜索组块的步长limit.

使用基于遍历e值的改进二分法排样, e值在算法中的影响分析如下:第一, e值的大小和获得的排样方案利用率有一定关系, 通过遍历e, 更容易找到较好的排样结果; 第二, 在不同排样工件种类情形下, 二分法会始终朝着利用率较高的方向寻找排样结果.算法中精度e越大, 就越容易找到单块板材排样方案, 但方案的废料率往往偏大, 精度e越小, 单块板材排样方案的废料率通常更小, 但是面积较小的工件会被提前大量使用.e通过公式计算取值为0.12、0.08、0.05、0.03、0.02, 通过遍历e, 有利于兼顾单块板材废料率和整体利用率的关系, 并为后处理算法留下优化余地.由于在算法中采用遍历e值的策略, 因此大大降低了e值对算法的影响.

对单块板材排样, 在不考虑切割选择的影响这一情况下, 假设每次只选择一种切割方式, 则搜索组块数量为k×limit^(m-1).对A|B类型待排矩形区执行排样时, limit取值越大, 搜索组块的范围越大, 则越容易找到利用率高的排样方案, 但会极大地增加搜索时间.因此搜索步长limit的取值, 对算法搜索时间有显著影响, 需要设置合理的limit取值, 兼顾排样方案质量和搜索效率的关系.在算法中, 对无废料排样, limit取值为2, 对有废料排样, limit取值可以放宽一些, 有利于找到利用率高的排样结果.

本文提出了求解单规格一刀切矩形排样问题的BSDBF启发式搜索算法, 该算法基于组化规则, 大胆地使用了二元组块排样, 获得了良好的局部子解特性, 同时避免了组块空间的无限扩大; 提出的“大小工件分治择优匹配”策略和组块快速举荐算法, 是对组化机制的关键补充, 弥补了组化机制的不足; 基于废料率的递归排样搜索, 同时兼顾了局部解和最优解的关系; 最后提出的基于“大小工件分治策略和利用率优劣集划分策略”相结合的排样结果后处理算法, 利用局部二次重排, 使算法具备了全局搜索能力.因为算法不具有随机特性, 获得的排样结果可以复现, 提高了算法的工程应用能力.对国际上大量Benchmark案例的计算结果表明, 相对于其他算法, 在排样质量上具有一定的优势.

为了保证算法的收敛性, 算法设计了两种松弛机制.

其一, 在对C类型和A|B类型的板材进行排样时, 组块的推荐范围逐步扩大, 保证了算法的全局搜索特性.

其二, 基于动态二分法的单块板材排样方案寻优, 预设二分法上下限精度适当放宽, 以降低板材利用率, 加快算法收敛.

后续的研究包括:

(1) 进一步研究组化理论及相关技术, 包括组块快速生成机制、组块重要性评估方法、组块互换性理论等.

(2) 在排样方案后处理机制上, 进一步研究板材拆分策略, 将已排样板材和拆分后的工件进行小规模重排, 不断置换出数量更多的小面积工件, 并迭代执行, 二次优化重组, 提高整体排样质量.

(3) 将算法进一步应用于多规格矩形件排样问题和三维装箱问题, 拓展算法的工程应用前景.

(4) 在工程应用中, 算法还需要根据不同工艺和原材料属性, 进一步考虑边界补偿问题.例如, 在用激光切割、水刀切割钢板时, 过宽的切缝必须看成派生排样工件, 进入待排样队列.再例如, 玻璃切割后还需要进行粗细磨边, 边界补偿可以包括在“磨边余量”这一变量中.具体应用赋予了排样问题新的特征, 这也将成为排样问题新的研究方向.

致谢在此, 我们向本文引用参考文献的作者们及给予本文研究工作支持和建议的同行们表示衷心的感谢.