基于两段排样方式的矩形件优化下料算法

扈少华，武书彦，潘立武



基于两段排样方式的矩形件优化下料算法

扈少华，武书彦，潘立武

(河南牧业经济学院软件学院，河南 郑州 450011)

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

下料问题；两段排样方式；列生成算法；约束排样；矩形件

在机械制造业的生产过程中经常会遇到矩形件下料(rectangular items cutting stock，RCS)问题:用长为、宽为的板材切割出种不同规格的矩形件，其中第种矩形件的长为l、宽为w、需求量为d，=1,2,···,；优化目标为板材使用张数最少。RCS问题的解是一个下料方案，由多个不同的排样方式组成，每个排样方式对应单张板材上矩形件的具体排列方式[1]。

针对RCS问题，目前常见的求解方法有整数规划、线性规划和顺序启发式算法。

文献[2]提出了基于两阶段排样方式的整数规划模型，研究了RCS问题的线性松弛下界。文献[3]提出了基于三阶段排样方式的整数规划模型，该模型具有多项式个数的变量和约束条件；构造了该模型的分支定价和集合覆盖求解算法。文献[4]通过扩展一维下料问题的数学模型构造了RCS问题基于两阶段和三阶段排样方式的整数规划模型，其中决策变量对应板材各阶段的切割线位置。以上文献方法只能求解规模较小的RCS问题，对于中大规模的RCS问题，耗费的计算时间让人无法忍容。

文献[5-6]采用线性规划方法对RCS问题进行了探讨。研究表明，线性规划方法的求解速度快于整数规划方法。但线性规划方法求得的下料方案解(各个排样方式的频数)为小数，并非RCS问题的实际可行解。文献中通过对线性规划解进行向上取整操作得到RCS问题的实际可行解。但向上取整会增加下料方案的板材使用张数，浪费板材资源。

顺序启发式算法通过逐个生成排样方式来构造下料方案，每个排样方式满足部分矩形件需求量，当所有矩形件需求量均得到满足时，算法终止。文献[7]提出了求解一维下料问题的顺序启发式算法，该算法能在较短的时间内得到近似最优解。文献[8]提出了1.5维下料问题的迭代顺序启发式算法，其可通过改变参数得到不同的排样方式。文献[9]提出了RCS问题基于价值修正策略的顺序启发式算法，并通过不断修正矩形件的价值使排样方式更趋于合理。文献[10]提出了一种以排样方式为导向的启发式下料算法，迭代构造多个排样方式，每次选取排样价值最大的一个排样方式加入到下料方案中。文献[11]构造了3种启发式排样规则：首次适应插入、最佳适应插入和关键适应插入，并提出了一种新颖的适应度计算公式。

本文针对RCS问题提出一种基于两段排样方式的优化下料算法，该算法结合了线性规划和顺序启发式算法思想。首先构造两段排样方式的约束排样算法，然后采用线性规划法调用约束排样算法生成多个虚拟下料方案，按照不产生多余矩形件原则选取各个虚拟下料方案中的部分排样方式组合形成实际下料方案。数值实验结果表明本文算法能有效的节约板材资源。

1 两段排样方式及其数学模型

1.1 两段排样方式

用一条平行于板材边的分割线将板材划分为两个段，同一段中排放方向相同的条带，这种排样方式称为两段排样方式[12]。两段排样方式有4种类型(图1)，即HXX型、HXY型、VXY型和VYY型。其中HXY型中的“H”表示两个段是水平排放，“XY”表示第一个段为向段，第二个段为向段。

图1 两段排样方式的类型

图2中，箭头所示的分界线将板材分为水平排放的两个段；图2(a)左右两个段中分别包含3条水平条带；图2(b)左边段中包含3条水平条带，右边段中包含2条竖直条带。

图2 两段排样方式例图

1.2 数学模型

约束两段排样问题：采用两段排样方式将长为、宽为的板材切割出种不同规格的矩形件，约束每种矩形件允许切割的数量不大于其需求量，l、w、c、b分别为第种矩形件的长、宽、价值、需求量，其中=1,2,···,；优化目标为使得板材切割出的矩形件总价值最大。令排样方式中包含y个第种矩形件，即

其中，为自然数集合。

2 两段排样方式生成算法

令板材和矩形件的水平边为长，竖直边为宽。假设板材和矩形件的尺寸均为整数，此假设不影响本文算法的通用性，因为当板材或矩形件尺寸不为整数时，可将板材和矩形件尺寸按比例尺放大到整数。本节着重研究HXY型两段排样方式的生成算法，同理易得其他3种类型的两段排样方式的生成算法。

2.1 条带的价值

对矩形件按照宽度非递减顺序编号，即1≤2≤····≤w。令(,)为水平条带´w(长：，宽：w)的价值，其中=1,2,···,，=0,1,···,；(,,)为水平条带´w中包含矩形件的个数，则有

2.2 段的价值

记(,,)为向段´(长：、宽：)中包含矩形件的个数，其中(,,0)=0。可通过动态规划递推可得段的价值(,)，即

其中，(,0)=0；e表示段中排入水平条带´w所获得的价值增量。同理可确定向段´的价值。

2.3 排样方式生成算法

步骤1. 根据2.1节内容，生成与向段´主排样相关的所有水平条带´w(=0,1,···,；=1,2,···,)和与向段´主排样相关的所有竖直条带l´。

步骤2. 根据2.2节内容，生成向段´的主排样，记两段排样方式价值=F(,)。

步骤3. 从1到枚举分割线位置。

步骤3.1. 确定向段´的主排样。

步骤3.2. 生成与向段(–)´辅排样相关的所有竖直条带，确定向段(–)´的辅排样。

步骤3.4. 生成与向段´辅排样相关的所有水平条带，确定向段´的辅排样。

步骤4. 输出最优两段排样方式。

3 下料算法

RCS问题的解即下料方案，其由多个不同的排样方式组成，其中每个排样方式的频数(使用次数)为非负整数，RCS问题的整数规划数学模型为

式(5)的线性松弛形式为

本文下料算法步骤如下[1]：

步骤1. 初始化实际下料方案为空，即不包含任何排样方式。

步骤2. 初始化剩余下料问题为原始下料问题，即矩形件的剩余需求量为d。

步骤3. 采用基于列生成的线性规划算法[15]迭代调用2.3节两段排样方式生成算法求解当前剩余下料问题的线性松弛式(6)，得到一个虚拟下料方案(由于每种排样方式的频数可能为小数，因此并不符合实际)。

步骤4. 按照一定规则选取当前虚拟下料方案中的部分排样方式加入到实际下料方案中，更新每种矩形件的剩余需求量；若当前所有矩形件的剩余需求量均为0，则转步骤5，否则转步骤3。

步骤5. 输出实际下料方案。

步骤3~4反复求解剩余下料问题的线性松弛式直到所有矩形件的需求量均得到满足。步骤3采用列生成算法迭代调用第2节排样方式生成算法得到虚拟下料方案中的各个排样方式。

令max为当前虚拟下料方案中排样方式频数的小数部分的最大值，有0≤max<1，令参数在区间[0,1]取值。记为虚拟下料方案中当前正在考察的排样方式，=[1,2,···,y]，其中y为中包含矩形件的数量，令为的频数。步骤4按照以下规则选取虚拟下料方案中的排样方式加入到实际下料方案中：

方案1.对虚拟下料方案中的排样方式按照其频数非递增顺序进行排序。

方案2.按顺序逐个考察排样方式，如果≥max且对任意Î{1,2,···,}有y≤d，则将加入到实际下料方案中。

分析可知，方案2每次至少选取了一个排样方式加入到实际下料方案中，这是因为y≤d对每个排样方式均满足且至少存在一个排样方式其频数大于等于max，这保证了下料算法的收敛性。另外可知取值越小，加入到实际下料方案中的排样方式个数就越多。

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

表1 实验统计结果

4.2 与文献[6]算法的比较

某电机厂，需要用长为1 000 mm，宽为600 mm的板材切割出10种矩形件，矩形件长宽尺寸在区间[70 mm,220 mm]分布，需求量在区间[4000,10000]分布，具体数据见文献[6]中的表3。文献[6]算法生成的下料方案使用2 285张板材，下料利用率为99.18%；本文算法(取值为0.85)生成下料方案，计算时间为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问题广泛地存在于机械制造业的板料成形生产过程中，一个好的优化下料算法可减少板材消耗，降低板材切割难度。本文设计了一种基于动态规划和列生成的顺序启发式下料算法。首先采用动态规划算法生成对矩形件数量有约束的两段排样方式，然后采用列生成算法迭代调用动态规划算法依次生成多个虚拟下料方案，按照不产生多余矩形件原则在各个虚拟下料方案中选取若干排样方式构成实际下料方案。数值实验结果表明，本文下料算法可有效地节省板材资源，且计算时间能满足实际应用需要。

[1] 胡钢, 杨瑞, 潘立武. 基于价值修正的圆片下料顺序启发式算法[J]. 图学学报, 2016, 37(3): 337-341.

[2] LODI A, MARTELLO S, VIGO D. Models and bounds 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 CARVALHO 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 Engineers, 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 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 bin-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 & Operations 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.

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)

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 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 steps 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 algorithms about 1.61% and 0.78%, respectively.

cutting stock problem; two-segment patterns; column generation algorithm; constrained packing; rectangular items

TP 391

10.11996/JG.j.2095-302X.2018010091

A

2095-302X(2018)01-0091-06

2017-06-08；

2017-06-28

河南省科技厅科技攻关项目(152102210320)；河南省高等学校重点科研项目(15B52000)

扈少华(1978–)，男，河南郑州人，讲师，硕士。主要研究方向为CAD、智能制造。E-mail：hshhnmy@163.com