基于两段排样方式的矩形件优化下料算法-扈少华.pdf

《基于两段排样方式的矩形件优化下料算法-扈少华.pdf》由会员分享，可在线阅读，更多相关《基于两段排样方式的矩形件优化下料算法-扈少华.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2018 年 2月 图 学 学 报 February 2018第 39 卷 第 1期 JOURNAL OF GRAPHICS Vo l . 3 9 N o . 1收稿日期： 2017-06-08；定稿日期： 2017-06-28 基金项目： 河南省科技厅科技攻关项目 (152102210320)；河南省高等学校重点科研项目 (15B52000) 第一作者： 扈少华 (1978)，男，河南郑州人，讲师，硕士。主要研究方向为 CAD、智能制造。 E-mail： 基于两段排样方式的矩形件优化下料算法 扈少华， 武书彦， 潘立武 (河南牧业经济学院软件学院，河南 郑州 450011) 摘要：针对矩形

2、件下料问题，提出一种基于两段排样方式的优化下料算法。首先构造一种约束排样算法，生成矩形件在板材上的两段排样方式。然后采用列生成算法依据矩形件剩余需求量迭代调用上述约束排样算法生成一个虚拟下料方案，按照不产生多余矩形件原则选取虚拟下料方案中的部分排样方式加入到实际下料方案中，更新矩形件剩余需求量；重复上述步骤直到矩形件剩余需求量为零。采用文献中基准例题将该算法与 2 种文献算法进行比较，数值实验结果表明该算法下料利用率比 2 种文献算法分别高 1.61%和 0.78%。 关键词 ：下料问题；两段排样方式；列生成算法；约束排样；矩形件 中图分类号： TP 391 DOI： 10.11996/JG.

3、j.2095-302X.2018010091 文献标识码： A 文 章 编 号： 2095-302X(2018)01-0091-06 An Optimization Algorithm for Rectangular Items Cutting Stock Problem Based on Two-Segment Patterns HU Shaohua, WU Shuyan, PAN Liwu (Software College, Henan University of Animal Husbandry & Economy, Zhengzhou Henan 450011, China) Abs

4、tract: For on the rectangular items cutting stock problem, an optimization algorithm based on two-segment patterns is proposed. Firstly, a constrained packing algorithm is constructed to generate the two-segment patterns of rectangular items on the plate. Then, column generation algorithm is used to

5、 generate a virtual cutting plan according to the current remaining demand of rectangular items, several patterns are added into actual cutting plan according to the rule that no redundant rectangular item is generated, and the current remaining demand of rectangular items is updated. The above step

6、s are repeated until the remaining demand of rectangular items is zero. Compared the proposed algorithm with two algorithms in the literature through benchmark instances, results of numerical experiments show that material utilization of the proposed algorithm is higher than two literature algorithm

7、s about 1.61% and 0.78%, respectively. Keywords: cutting stock problem; two-segment patterns; column generation algorithm; constrained packing; rectangular items 在机械制造业的生产过程中经常会遇到矩形件下料 (rectangular items cutting stock， RCS)问题 :用长为 L、宽为 W 的板材切割出 m 种不同规格的矩形件，其中第 i 种矩形件的长为 li、宽为 wi、需求量为 di， i1,2,m；优化目标

8、为板材使用张数最少。 RCS 问题的解是一个下料方案，由多个不同的排样方式组成，每个排样方式对应单张板材上矩形件的具体排列方式1。 万方数据 92 可视化 /可视分析 2018 年针对 RCS 问题，目前常见的求解方法有整数规划、线性规划和顺序启发式算法。 文献 2提出了基于两阶段排样方式的整数规划模型， 研究了 RCS 问题的线性松弛下界。 文献 3提出了基于三阶段排样方式的整数规划模型，该模型具有多项式个数的变量和约束条件；构造了该模型的分支定价和集合覆盖求解算法。文献 4通过扩展一维下料问题的数学模型构造了 RCS 问题基于两阶段和三阶段排样方式的整数规划模型，其中决策变量对应板材各阶段

9、的切割线位置。以上文献方法只能求解规模较小的 RCS 问题，对于中大规模的 RCS 问题，耗费的计算时间让人无法忍容。 文献 5-6采用线性规划方法对 RCS 问题进行了探讨。研究表明，线性规划方法的求解速度快于整数规划方法。但线性规划方法求得的下料方案解 (各个排样方式的频数 )为小数，并非 RCS 问题的实际可行解。文献中通过对线性规划解进行向上取整操作得到 RCS 问题的实际可行解。但向上取整会增加下料方案的板材使用张数，浪费板材资源。 顺序启发式算法通过逐个生成排样方式来构造下料方案，每个排样方式满足部分矩形件需求量，当所有矩形件需求量均得到满足时，算法终止。文献 7提出了求解一维下料

10、问题的顺序启发式算法，该算法能在较短的时间内得到近似最优解。 文献 8提出了 1.5 维下料问题的迭代顺序启发式算法，其可通过改变参数得到不同的排样方式。文献 9提出了 RCS 问题基于价值修正策略的顺序启发式算法，并通过不断修正矩形件的价值使排样方式更趋于合理。文献 10提出了一种以排样方式为导向的启发式下料算法，迭代构造多个排样方式，每次选取排样价值最大的一个排样方式加入到下料方案中。文献 11构造了 3 种启发式排样规则：首次适应插入、最佳适应插入和关键适应插入，并提出了一种新颖的适应度计算公式。 本文针对 RCS 问题提出一种基于两段排样方式的优化下料算法，该算法结合了线性规划和顺序启

11、发式算法思想。首先构造两段排样方式的约束排样算法，然后采用线性规划法调用约束排样算法生成多个虚拟下料方案，按照不产生多余矩形件原则选取各个虚拟下料方案中的部分排样方式组合形成实际下料方案。数值实验结果表明本文算法能有效的节约板材资源。 1 两段排样方式及其数学模型 1.1 两段排样方式 用一条平行于板材边的分割线将板材划分为两个段，同一段中排放方向相同的条带，这种排样方式称为两段排样方式12。两段排样方式有 4种类型 (图 1)，即 HXX 型、 HXY 型、 VXY 型和VYY 型。其中 HXY 型中的 “H”表示两个段是水平排放， “XY”表示第一个段为 X 向段，第二个段为Y 向段。 (

12、a) HXX 型 (b) HXY型 (c) VXY 型 (d) VYY型 图 1 两段排样方式的类型 图 2 中，箭头所示的分界线将板材分为水平排放的两个段； 图 2(a)左右两个段中分别包含 3 条水平条带；图 2(b)左边段中包含 3 条水平条带，右边段中包含 2 条竖直条带。 (a) HXX 型排样方式 (b) HXY 型排样方式 图 2 两段排样方式例图 1.2 数学模型 约束两段排样问题：采用两段排样方式将长为 L、宽为 W 的板材切割出 m 种不同规格的矩形件，约束每种矩形件允许切割的数量不大于其需求量， li、 wi、 ci、 bi分别为第 i 种矩形件的长、宽、价值、需求量，其

13、中 i1,2,m；优化目标为使得板材切割出的矩形件总价值 C 最大。 令排样方式 P中包含 yi个第 i 种矩形件，即 万方数据 第 1 期 扈少华，等：基于两段排样方式的矩形件优化下料算法 931max0,1,2s.t.miiiiiiCycybyNi mP且满足两段排样方式约束(1) 其中， N 为自然数集合。 2 两段排样方式生成算法 令板材和矩形件的水平边为长，竖直边为宽。假设板材和矩形件的尺寸均为整数，此假设不影响本文算法的通用性，因为当板材或矩形件尺寸不为整数时，可将板材和矩形件尺寸按比例尺放大到整数。本节着重研究 HXY 型两段排样方式的生成算法，同理易得其他 3 种类型的两段排样

14、方式的生成算法。 2.1 条带的价值 对矩形件按照宽度非递减顺序编号，即 w1w2 wm。令 s(j,x)为水平条带 xwj(长： x，宽：wj)的价值，其中 j1,2,m， x0,1,L； z(i,j,x)为水平条带 xwj中包含矩形件 i 的个数，则有 11(,) max (,)(, , )s.t.(, , ) , (, , ) , 1,2, ,jiijiiisjx czijxlzi jx xzijx b zijx Ni j(2) 采用文献 13的动态规划算法求解式 (2)，由于动态规划算法具有全容量性，因此只需求解出s(m,L)即可确定所有水平条带 xwj(x0,1,L，j1,2,m)的

15、价值， 算法时间复杂度为1miiOL b。同理可确定所有竖直条带的价值。 2.2 段的价值 记 n(i,x,y)为 X 向段 xy (长： x、宽： y)中包含矩形件 i 的个数，其中 n(i,x,0)0。可通过动态规划递推可得段的价值 F(x,y)，即 (, ) max (, 1), (, ),1,2,j jjFxy Fxy Fxy w eywj m；其中， (3) 1min ( , , ), ( , , )mji i jiec zijxbnixyw (4) 其中， F(x,0)0； ej表示段中排入水平条带 xwj所获得的价值增量。同理可确定 Y 向段 xy 的价值。 2.3 排样方式生成

16、算法 分割线将板材划分为两个段，即 X 向段 xW和Y 向段 (Lx)W。称其中一个段为主段，另外一个段为辅助段。主段上的排样方式称为主排样，由初始矩形件生成， 此时矩形件 i(i1,2,m)的需求量为 bi；辅助段上的排样方式称为辅排样，由剩余矩形件生成，此时矩形件 i 的需求量为 bizi，其中， zi为主段包含矩形件 i 的数量14。对于段 xy，当其为 X 向段时记其主排样价值为 FM(x,y)， 辅排样价值为 FA(x,y)；当其为 Y 向段时记其主排样价值为 (, )MFxy，辅排样价值为 (, )AFxy。两段排样方式生成算法为： 步骤 1. 根据 2.1 节内容，生成与 X 向

17、段 xW主排样相关的所有水平条带 xwj(x0,1,L；j1,2,m)和与 Y 向段 xW 主排样相关的所有竖直条带 ljW。 步骤 2. 根据 2.2 节内容，生成 X 向段 LW 的主排样，记两段排样方式价值 VFM(L,M)。 步骤 3. 从 1 到 L 枚举分割线位置 x。 步骤 3.1. 确定 X 向段 xW 的主排样。 步骤 3.2. 生成与 Y 向段 (Lx)W 辅排样相关的所有竖直条带，确定 Y 向段 (Lx)W 的辅排样。 步骤 3.3. 如果 (, ) ( , )MAFxW FLxW V时，此排样方式为最优排样方式，令 (, )MVF xW= (,)AFLxW 。 步骤 3

18、.4. 生成与 X 向段 xW 辅排样相关的所有水平条带，确定 X 向段 xW 的辅排样。 步骤 3.5. 如果 (, ) ( , )AMFxW FLxW V时，此排样方式为最优排样方式，令 (, )AVF xW= (,)MFLxW 。 步骤 4. 输出最优两段排样方式。 步骤 1 时间复杂度为1miiOL b+1miiOW b；步骤 2 时间复杂度为1miiOW b；步骤 3 对于每条分割线位置 x，步骤 3.13.5 时间复杂度分别为1miiOW b、1miiOW b+1()miiOLx b、 O(1)、1miiOx b+1miiOW b、 O(1)，故步骤 3 总的时间复杂度为212(

19、3)miiOLL LW b；步骤 4 时间复杂度为 O(1)。由于 1L ，故本文两段排样方式生万方数据 94 可视化 /可视分析 2018 年成算法的时间复杂度为21(3)miiOL LW b。 3 下料算法 RCS 问题的解即下料方案，其由多个不同的排样方式组成，其中每个排样方式的频数 (使用次数 )为非负整数， RCS 问题的整数规划数学模型为 11min,1,2,s.t.,1,2,KkkKik k ikkZxax d i mxNk K(5) 式 (5) 中需要考察的排样方式集合 P1, P2,PK； xk表示排样方式 Pk的频数； aik表示排样方式 Pk包含矩形件 i 的数量； di

20、为矩形件 i的需求量。式 (5)目标函数为最小化板材使用张数 Z，约束条件1Kik k ikax d表示每个矩形件的需求量均得到满足。由于可能的排样方式的数量非常庞大，对于中大规模的 RCS 问题不可能枚举出所有可能的排样方式，因此式 (5)难以采用整数规划方法直接求解。本文采用线性规划方法对式 (5)进行间接求解。 式 (5)的线性松弛形式为 11min,1,2,s.t.0, 1,2, ,KkkKik k ikkZxax d i mxk K(6) 本文下料算法步骤如下1： 步骤 1. 初始化实际下料方案为空，即不包含任何排样方式。 步骤 2. 初始化剩余下料问题为原始下料问题，即矩形件 i

21、的剩余需求量为 di。 步骤 3. 采用基于列生成的线性规划算法15迭代调用 2.3 节两段排样方式生成算法求解当前剩余下料问题的线性松弛式 (6)，得到一个虚拟下料方案 (由于每种排样方式的频数可能为小数，因此并不符合实际 )。 步骤 4. 按照一定规则选取当前虚拟下料方案中的部分排样方式加入到实际下料方案中，更新每种矩形件的剩余需求量；若当前所有矩形件的剩余需求量均为 0，则转步骤 5，否则转步骤 3。 步骤 5. 输出实际下料方案。 步骤 34 反复求解剩余下料问题的线性松弛式直到所有矩形件的需求量均得到满足。步骤 3采用列生成算法迭代调用第 2 节排样方式生成算法得到虚拟下料方案中的各

22、个排样方式。 令 xmax为当前虚拟下料方案中排样方式频数的小数部分的最大值，有 0 xmax1，令 参数在区间 0,1取值。记 P 为虚拟下料方案中当前正在考察的排样方式， Py1,y2,yn，其中 yi为 P 中包含矩形件 i 的数量，令 x 为 P 的频数。步骤 4 按照以下规则选取虚拟下料方案中的排样方式加入到实际下料方案中： 方案 1. 对虚拟下料方案中的排样方式按照其频数非递增顺序进行排序。 方案 2. 按顺序逐个考察排样方式 P，如果 xxmax且对任意 i1,2,n有 yi di，则将 P 加入到实际下料方案中。 分析可知，方案 2 每次至少选取了一个排样方式加入到实际下料方案

23、中，这是因为 yi di对每个排样方式均满足且至少存在一个排样方式其频数大于等于 xmax，这保证了下料算法的收敛性。另外可知 取值越小， 加入到实际下料方案中的排样方式个数就越多。 4 数值实验计算 用 C+语言编程实现本文下料算法，在英特尔奔腾双核 G4400 CPU， 主频 3.3 GHz， 内存 4 GB计算机上进行实验，实验平台为 Microsoft Visual Studio 2012。采用文献中基准例题，将本文下料算法与文献 5和 6算法进行比较。 4.1 与文献 5算法的比较 用本文下料算法求解文献 5的 6 道例题(ID1-ID6)。考察 =0.65、 0.75、 0.85、

24、 0.95 的 4 种情形。实验统计结果见表 1，其中 U、 T 分别为本文下料算法的下料利用率和计算时间。从表 1 可以看出， 本文下料算法的计算时间随着 的增加而增加，下料利用率随着 的增加先增加后减少。这是因为 越大， 每次加入到实际下料方案的排样方式越少，矩形件剩余需求量递减的速度较慢，算法迭代次数较多；当 的取值超过某一临界值后，每次只能加入一个排样方式到实际下料方案中，算法贪婪性变强，使得下料利用率变低。文献 5算法平均下料利用率为 97.14%；本文下料算法在=0.85 时平均下料利用率最高，比文献 5算法高1.61%。本文下料算法的计算时间不超过 3 s，计算 万方数据 第 1

25、 期 扈少华，等：基于两段排样方式的矩形件优化下料算法 95表 1 实验统计结果 ID =0.65 =0.75 =0.85 =0.95 U(%) T(s) U(%) T(s) U(%) T(s) U(%) T(s) 1 98.13 2.47 98.96 2.53 99.17 2.58 98.93 2.67 2 99.18 2.45 99.43 2.55 99.54 2.57 99.37 2.63 3 97.46 2.40 98.37 2.49 98.76 2.54 98.52 2.86 4 97.62 2.36 98.40 2.41 98.71 2.37 98.31 2.97 5 98.10

26、2.27 98.16 2.37 98.28 2.60 98.18 2.72 6 96.59 2.46 97.81 2.53 98.06 2.76 97.92 2.81 平均 97.85 2.40 98.52 2.48 98.75 2.57 98.54 2.78 时间在实际应用中比较合理。 4.2 与文献 6算法的比较 某电机厂， 需要用长为 1 000 mm， 宽为 600 mm的板材切割出 10 种矩形件，矩形件长宽尺寸在区间70 mm,220 mm分布，需求量在区间 4000,10000分布，具体数据见文献 6中的表 3。文献 6算法生成的下料方案使用 2 285 张板材， 下料利用率为9

27、9.18%；本文算法 ( 取值为 0.85)生成下料方案， (a) 方式 1： 706 张 (b) 方式 2： 195 张 (c) 方式 3： 126 张 (d) 方式 4： 69 张 (e) 方式 5： 517 张 (f) 方式 6： 88 张 (g) 方式 7： 125 张 (h) 方式 8： 276 张 (i) 方式 9： 39 张 (j) 方式 10： 121 张 (k) 方式 11： 1 张 (l) 方式 12： 1 张 (m) 方式 13： 1 张 (n) 方式 14： 1 张 (o) 方式 15： 1 张 图 3 本文算法生成的下料方案 万方数据 96 可视化 /可视分析 201

28、8 年计算时间为 2.67 s，下料方案使用 2 267 张板材，下料利用率为 99.96%；本文算法下料利用率比文献 6算法高 0.78%。 另外本文算法板材下料利用率接近 100%，说明该算法在节省板材资源和提高板材利用率方面是有效的。 本文算法在生成下料方案的过程中总共考察了 109 个排样方式， 平均每个排样方式耗时 0.024 s。 图 3 为本文算法生成的下料方案，共包含 15 个排样方式，其中 “图 3(a)方式 1：706 张 ”表示按照排样方式 1 切割板材 706 张。 5 结 论 RCS 问题广泛地存在于机械制造业的板料成形生产过程中，一个好的优化下料算法可减少板材消耗，

29、降低板材切割难度。本文设计了一种基于动态规划和列生成的顺序启发式下料算法。首先采用动态规划算法生成对矩形件数量有约束的两段排样方式，然后采用列生成算法迭代调用动态规划算法依次生成多个虚拟下料方案，按照不产生多余矩形件原则在各个虚拟下料方案中选取若干排样方式构成实际下料方案。数值实验结果表明，本文下料算法可有效地节省板材资源，且计算时间能满足实际应用需要。 参 考 文 献 1 胡钢 , 杨瑞 , 潘立武 . 基于价值修正的圆片下料顺序启发式算法 J. 图学学报 , 2016, 37(3): 337-341. 2 LODI A, MARTELLO S, VIGO D. Models and bou

30、nds for two-dimensional level packing problems J. Journal of Combinatorial Optimization, 2004, 8(3): 363-379. 3 PUCHINGER J, RAIDL G R. Models and algorithms for three-stage two-dimensional bin packing J. European Journal of Operational Research, 2007, 183(3): 1304-1327. 4 SILVA E, ALVELOS F, DE CAR

31、VALHO J M V. An integer programming model for two-and three-stage two-dimensional cutting stock problems J. European Journal of Operational Research, 2010, 205(3): 699-708. 5 CUI Y. Generating optimal T-shape cutting patterns for rectangular blanks J. Proceedings of the Institution of Mechanical Eng

32、ineers, Part B: Journal of Engineering Manufacture, 2004, 218(8): 857-866. 6 易向阳 , 仝青山 , 潘卫平 . 矩形件二维下料问题的一种求解方法 J. 锻压技术 , 2015, 40(6): 150-154. 7 HAESSLER R W. A heuristic programming solution to a nonlinear cutting stock problem J. Management Science, 1971, 17(12): B793-B802. 8 SONG X, CHU C B, NIE

33、 Y Y, et al. An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem J. European Journal of Operational Research, 2006, 175(3): 1870-1889. 9 黄少丽 , 杨剑 , 侯桂玉 ,等 . 解决二维下料问题的顺序启发式算法 J. 计算机工程与应用 , 2011, 47(13): 234-237. 10 CHARAMBOUS C, FLESZAR K. A constructive b

34、in-oriented heuristic for the two-dimensional bin packing problem with guillotine cuts J. Computers & Operations Research, 2011, 38(10): 1443-1451. 11 FLESZAR K. Three insertion heuristics and a justification improvement heuristic for two-dimensional bin packing with guillotine cuts J. Computers & O

35、perations Research, 2013, 40(1): 463-474. 12 潘卫平 , 陈秋莲 , 崔耀东 . 考虑切割刀数的最优两段排样算法研究 J. 广西大学学报 : 自然科学版 , 2014, 39(3): 687-692. 13 KELLERER H, PFERSCHY U, PISINGER D. Knapsack problems M. Berlin: Springer, 2004: 56-79. 14 CUI Y, HUANG B. A heuristic for constrained T-shape cutting patterns of circular items J. Engineering Optimization, 2011, 43(8): 867-877. 15 车念 , 张军 , 潘立武 . 冲裁条带剪切下料问题的一种求解算法 J. 机械设计与制造 , 2016(2): 37-40. 万方数据