英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料
一种约束二维切割问题的递归算法
摘要 本文提出了一种约束二维的递归算法矩形物品的剪断问题。这个算法将一个股票板块分割开来变成了一系列小的矩形块。对于当前被考虑的块，它选择一个项目，把它放在块的左下角，并确定分割块的方向，将块的未被占用区域划分为两个较小的块，以供进一步考虑。分割线要么沿着上边缘，要么沿着所选物品的右边缘，从无约束解中获得的上界用于缩短搜索空间。对基准问题的计算结果表明，该算法可以改进解决方案，比其他算法快。
关键词 递归算法 无约束二维切割 闸刀切割
1介绍
二维切割（TDC）问题包括从一个大的大的矩形板上切割一组小的矩形物体（毛坯），以最大限度地增加被切割的物品的总价值。这个问题被正式称为二维的、矩形的、单一的、大的物体放置问题（斜面）。它出现在几个工业领域，比如切割木板制作家具，切割纸板做盒子，以及切割玻璃板和金属板相关产品。
本文讨论了最有趣的TDC问题之一，即受限的二维切割（CTDC）问题，并提出了以下问题：板的尺寸大小R为Ltimes;W（长L和宽W）；第i块的毛坯的参数有尺寸li times;wi，价值 vi和需求量bi，i=1，2，hellip;，m。任务是将板材切割成i种毛坯形状共xi块，并且0le;xile;bi，i=1，....，m，实现总效益最大化。在本文中，作如下假设：
（1）所有的毛坯都有固定的方向，也就是说，每一块的维度（a，b）和（b，a）是不一样的；
（2）所有的应用切割都是断头台式的，即从一条边开始，然后平行于另外两条边；
（3）参数L，W，Li，Wi，和b i，i=1，hellip;，m，皆为非负整数。
我们说，整数和非负数的n维向量（x1，hellip;，xn）对应于一个切割模型，如果有可能产生xi个i类型的，i=1，....，m，在大板R中没有重叠。一些工业切割过程限制了断头台切割模式的产生。在第一阶段，切割是平行于板的一边，然后，在下一个阶段，与前面的切割正交，以此类推。如果分阶段的数量有限制，比如k，这个切割被称为k-阶段性切割；否则，它被称为非分段（注意，非分段的剪切等价于定义k足够大）。如果阶段的数量趋向于积极的无限，那么切割模式就叫做一般的断头台模式。因此，本文所考虑的断头台模式是一般的。
对于CTDC问题，它可以被区分：
（1）未加权的CTDC：每一项的值vi等于它的面积si=li wi。目标是使总占用面积最大化，这相当于尽量减少浪费。
（2）加权CTDC：项目的值独立于它们的区域。其目的是使项目削减的总价值最大化。
对于CTDC问题，有两种方法：自上而下的方法和自下而上的方法。顶部向下的方法使用树搜索过程。所有可能的削减都可以通过一棵树来列举，在这棵树中，分支与断头台切割相对应，节点代表通过断头台切割获得的子矩形。底部向上的方法是基于这样一种观察，即任何满足断头台约束的模式都可以通过水平和垂直的矩形结构来获得。所有可能的小矩形的组合都是为了获得更大的矩形，直到没有更多的断头台模式。这两种方法都可以使用上界和下界来丢弃一些没有前途的分支。
许多作者已经调查了CTDC问题。对于小实例，通过基于深度优先搜索方法的一般树搜索，以及基于最佳优先搜索方法的分支和绑定过程，提出了一些精确的算法。
对于规模相对较大的问题，已经开发出了许多启发式算法。Morabito和Arenales提供了一种基于深度优先搜索和爬山策略的算法。其他研究人员也开发了一些启发式方法来解决CTDC问题。最近，alarez-valdeset al开发了几种用于断头台（un）受限的二维切割问题的启发式算法，特别是在中等计算时间中，tabu搜索算法获得了高质量的结果。最近，Hifi提出了一种用于约束二维切割问题的混合算法，在此算法中，使用爬山策略和动态规划技术进行深度优先搜索。该算法可以为大问题实例提供良好的解决方案。崔教授为CTDC提供了两种精确的算法：一种是生成同质的t型模式的精确算法，以简化切割过程;另一种是一种精确的算法，该算法基于分支和绑定的过程，结合动态规划技术，生成同质的三阶段切割模式。这两种算法是精确的，如果只有带有特定特征的模式（比如同质的t型或三阶段模式）。它们也可以用作生成一般的CTDC模式的启发式。
如果bi（i=1，hellip;，m）被设定为无穷大，那么CTDC问题就变成了不确定的二维切割（UTDC）问题。在很多文献中已经报道了UTDC问题的算法。例如，在[19、20]中讨论了一般的断头台模式；分阶段模式在[21、22]；在[23]中的t形模式；以及[24]中的简单方块模式。如果在解决CTDC问题时使用分支和绑定技术，那么相关UTDC问题的解决方案值可以用作上限。
本文提出了一种针对CTDC的递归启发式算法。计算结果表明，该算法能在短时间内产生良好的解决方案，解决各种尺度的问题。下一节描述递归算法的方案。第3节用基准问题测试算法，并将计算结果与从其他算法中获得的结果进行比较。第4节以结论结束论文。
2方法
2.1算法的方案
假设Lmin和Wmin分别为所有毛坯的最小长度和宽度,V(x,y)为毛坯包括在当前模块xtimes;y的最大值， P是模块xtimes;y的上级模型。假定B = { 1,hellip;，Bm，Bi（i=1，hellip;，m）是在p的左下方角落里排列的毛坯形状i的数量。将块的未被占用区域划分为两个较小的块，或者水平沿上边缘（图1a）或垂直沿右侧边缘（图1b）。
假设Vxi（x，y）表示当划分切割为水平时，块xtimes;y的值，而Vyi（x，y）表示当分割是垂直的值。然后，有
（a）水平分割 （b）垂直分割
图1两种方法来划分块的未被占用区域
考虑到我们可以从m类型中选择该物品，并将其放置在区块的左下方角落，我们有以下递归公式：
V(x，y)=0，如果 x lt; Lmin 或 y lt; Wmin；
Vxi(x，y)=Vyi（x，y）=0，如果 x lt; li 或 y lt; wi 或 bi—Bilt;1；
V(x，y)=max{ Vxi(x，y)，Vyi（x，y）}，如果 x ge; li 且 y ge; wi 且bilt;Bi；
0le;xle;L,0le;yle;W，i=1，hellip;，m
虽然上面的递归算法是可行的，但是计算时间可能太长，特别是对于大规模的问题。因此，我们必须利用一些启发式规则，在合理的时间范围内产生可行的解决方案。下面的规则有助于缩短计算时间。
(1) 使用上界和下界来提高递归函数的性能。
(2) 按其值的降序排列项目。这有助于较早地获得更紧的下界，对于具有较高单位值的项目被认为是早期的。更紧的下界有助于有效地修剪搜索树。
(3) 限制当前试验块的最大计算时间。如果当前试验块的计算时间t达到给定的运行时间t最大值，则搜索过程将尽快终止。
2.2无约束解的递归过程
崔[24]为UTDC问题提供了一种递归算法。该算法可用于估计上限，因为它以与本文相同的方式生成切割模式，但不考虑要求的上界。假设递归函数URF（x，y）返回不受约束的解决方案的最大值以阻止块xtimes;y，让Uxy成为不受约束的解决方案的最大值，最初它被设置为1。递归函数URF（x，y）的步骤如下：
Step1：Return Uxy if Uxy ge;0；Return 0 if x lt; Lmin or y lt; Wmin；otherwise let Uxy = 0 and i = 0.
Step 2：Let i =i 1，Go to Step5 if i gt;m.
Step 3：Go to Step2 if x lt; li or y lt; wi ；otherwise let Ui=max（Uxi ，Uyi），in which
Uxi = vi URF(x－li，wi ) URF(li，y－wi)，
Uxy = vi URF(li，y－wi ) URF(x－li，y).
Step 4：Let Uxy =Ui if Ui gt;Uxy.Go to Step2.
Step 5：Return Uxy。
2.3带有一些启发式规则的递归函数
假设递归函数RecFun（x，y，B，C，V f，R f）返回块xtimes;y的最大值，其中B是已经放置在父模式中的毛坯的矢量，C={C 1，hellip;hellip;，C m}，用Ci表示在块中包含的项目类型i的数量，Vf是在考虑当前块xtimes;y之前已经放在盘子上的项目的总价值。它也被称为父模式的价值。Rf是一个具有值1或0的逻辑变量，其中1表示为真，0为假。B在调用递归函数之前确定。C的元素被初始化为0，在递归函数中确定，并返回父模式。假设S是板块中的区域，它是对块xtimes;y的补充，也就是这个板块由区域S和xtimes;y组成。如果S中的所有块都被考虑过，也就是没有任何东西可以被进
全文共12554字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[14148]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
