0 引言

二维板材切割问题是一个典型的NP-hard问题，该问题具有较高的复杂性和应用性。在离散行业中，随着制造技术的发展及市场需求的变化，产品的制造与加工订单量逐步增长，如何最大限度地节约成本、提高原材料利用率成为行业难题^[1]。离散行业中生产的方形件产品具有组装灵活、款式多样、加工分散等特点，且普遍存在订单组批、排样切割、批处理加工、订单分拣、单元调度等若干优化问题。因此，定制化生产模式中的切割方案对于板材利用率的提高有着至关重要的作用^[2-3]。

二维切割问题在实际生产应用非常广，求解的难度也大，许多学者为之进行了大量的研究。在排样优化方面，扈少华等^[4]研究了多卷材二维剪切下料问题，根据卷材长度方向切割最小原则来生成算法，产生一个排样方式来满足部分矩形件需求；覃广荣等^[5]从板材上分两阶段进行切割，建立整数线性规划模型，然后构造T形排样算法来生成矩形件在单张板材上的排样方式。在算法方面，黎凤洁等^[6]提出递归算法求解T形排样方式模型。Wuttke等^[7]研究根据序列相关设置时间和允许误差的二维下料问题，将排序问题描述为一个混合整数规划，并用一种带有反馈回路的顺序启发式算法。Furini等^[8]对二维切割原料问题提出了(伪)多项式混合整数规划模型。Cintra等^[9]考虑了物品的旋转、切口的长度和剩余板的价值，建立了新的整数规划模型。Furini等^[10]用列生成算法求解了两阶段模式矩形二维单料尺寸下料问题。Wang等^[11]根据一种新的切割原料问题的变种，提出了允许省略并加入设置成本的设想。苏俊等^[12]研究了多规格板材二维下料问题，板材规格多样，毛坯规格多样，提出变邻域人工蜂群算法VNABC，设计两种解码策略并改进VNABC算法的操作算子来优化。在实际的应用方面，Mostajabdaveh等^[13]应对纸张印刷行业二维切割原料问题，提出了一个非线性整数规划模型，该模型要符合三段式剪切，尽量减少由纸张和印版组成的印刷总成本。Luo等^[14]面对变压器制造业铁芯生产中出现的一种特殊的切割问题，提出了最小化带材总数的数学规划模型。然而很少有学者针对二维三阶段齐切割的下料问题进行优化。

本文研究方形件定制化生产中的三阶段齐切割问题，根据问题特征和要求，抽象化问题的关键，设计数学规划模型。设计列生成算法和遗传算法来求解大规模算例。模型和算法优化机理与优化方法可用于求解同类离散问题。给出具体算例来验证模型与算法的可行性与有效性。研究和设计的方形件三阶段齐切割的模型和算法，能够为离散行业产品生产综合决策提供支持，且具有重要的理论研究意义和应用价值。

1 问题描述

二维切割问题，根据切割工艺方式的不同，在一块板材上的切割方式分为“齐头切”和“非齐头切”，本文研究的二维切割问题是典型的具有“齐头切”约束的板型材方形件问题。三阶段切割方式是，第一阶段的切割可以选择横向切割或纵向切割，切割生成的模块称为条带(stripe)；第二阶段的切割方式垂直于第一阶段，切割生成的模块称为栈(stack)；第三阶段的切割方式垂直于第二阶段，平行于第一阶段，切割生成的模块称为产品项(item)，也就是数据集中给定的产品范围。“齐头切”根据切割的阶段数不同可以分为“精确方式”和“非精确方式”，本文只研究“精确方式”下的切割，即在切割三阶段后，最终切割生成的每个产品项都是完整的，非拼接而成，如图 1所示。

本文研究的板材原片的切割示意如图 1所示，包含了13个方形件的切割实例，其中，阴影部分为不能利用的废料。在方形件切割过程中需满足以下约束条件：相同栈(stack)里的产品项(item)的宽度(或长度)相同；任意两个方形件不能有面积重叠，但是允许边缘重合；方形件可以旋转，即方形件能以0°或90°排放。同时，本文研究板材二维切割问题，数学模型的建立与算法设计基于如下假设：

1) 板材原片仅有一种规格(2 440 mm*1 220 mm)且数量充足；

2) 切割方案不考虑切割缝隙宽度的影响；

3) 每次直线切割的方向都垂直于板材的一条边，每次切割都能使原片相互分离；

4) 同一切割方向的切割视作一个阶段，最多3个切割阶段；

5) 方形件产品必须排放在板材原片内部，不能超出边缘；

6) 方形件产品之间错位排放，不能发生重叠；

7) 方形件产品只有横放和竖放两种情况，即0°或90°摆放；

8) 规定产品从板材原片的左下角开始执行，并且以板材原片左下角为原点建立直角坐标系，取水平向右为X轴，竖直向上为Y轴。

2 三阶段齐切割混合整数规划模型 2.1 参数与变量定义

集合参数：K是板材原片集合，其索引为k, k∈K；S是条带(stripe)集合，其索引为s, s∈S；V是栈(stack)集合，索引为v, v∈V；N是产品项(item)序号集合，索引为i, i∈N；T是批次集合，索引为t, t∈T。

数据参数：M是一个无穷大的正数；A是单个批次产品项的面积总和，上限是250；Up是单个批次产品项总数，上限是1 000；L_i是产品项i的长度；W_i是产品项i的宽度；R_i是产品项i的材质类型；A_i是产品项i的产品面积。

问题变量参数：l_ks是第k个原片第s个条带的长度；w_ks是第k个原片第s个条带的宽度；l′_ksv是第k个原片第s个条带第v个栈的长度；w′_ksv是第k个原片第s个条带第v个栈的宽度；l″_ksvi是第k个原片第s个条带第v个栈第i个产品项的长度；w″_ksvi是第k个原片第s个条带第v个栈第i个产品项的宽度。

第一阶段为

$ p_k= \begin{cases}1, & \text { 原片 } k \text { 第一阶段为坚切, } \\ 0, & \text { 原片 } k \text { 第一阶段为横切。}\end{cases} $

产品i放置的位置为

$ u_{k s v i}= \begin{cases}1, & \text { 产品 } i \text { 放置在第 } k \text { 个原片的第 } s \text { 个 } \\ & \text { 条带的第 } v \text { 个栈中, } \\ 0, & \text { 其他。}\end{cases} $

产品i横着放置为

$ f_{k s s i}= \begin{cases}1, & \text { 产品 } i \text { 横着放置在第 } k \text { 个原片的第 } s \text { 个 } \\ & \text { 条带的第 } v \text { 个栈中, } \\ 0, & \text { 其他。}\end{cases} $

产品i竖着放置为

$ f_{k s i i}^{\prime}= \begin{cases}1, & \text { 产品 } i \text { 坚着放置在第 } k \text { 个原片的 } \\ & \text { 第 } s \text { 个条带的第 } v \text { 个栈中, } \\ 0, & \text { 其他。}\end{cases} $

板材原片使用情况为

$ y_k= \begin{cases}1, & \text { 表示第 } k \text { 个原片未被使用, } \\ 0, & \text { 表示第 } k \text { 个原片被使用。}\end{cases} $

2.2 数学模型

拟构建的规划模型的目标是最小化板材的利用量，即最少个数的板材被使用过。

目标函数

$ \min \sum\limits_{k \in K} y_k, $

(1)

约束条件如下。

1) 原片k在第一阶段切割后，每个stripe的长宽关系约束如式(2)~(5)。

$ \sum\limits_{s \in S} l_{k s} \leqslant L+M \cdot\left(1-p_k\right), \forall k \in K, $

(2)

$ l_{k s} \geqslant L \cdot\left(1-p_k\right), \forall k \in K, s \in S, $

(3)

$ \sum\limits_{s \in S} w_{k s} \leqslant W+M \cdot p_k, \forall k \in K, $

(4)

$ w_{k s} \geqslant W \cdot p_k, \forall k \in K, s \in S_{\circ} $

(5)

当p_k=0时，表示第一阶段横切，第二阶段竖切，第三阶段横切；

当p_k=1时，表示第一阶段竖切，第二阶段横切，第三阶段竖切。

式(2)表示s个stripe的长度和小于等于原片的总长度L。式(3)表示当p_k=1时，第s个stripe的长度大于0；当p_k=0时，每个stripe的长等于总长度L。式(4)表示s个stripe的宽度和小于等于原片的总宽度W。式(5)表示当p_k=0时，第s个stripe的宽度大于0；当p_k=1时，每个stripe的宽度等于总宽度W。

2) 原片k在第二阶段切割后，每个stack的长宽关系约束如(6)~(11)。

$ \sum\limits_{v \in V} l_{k s v}^{\prime} \leqslant l_{k s}+M \cdot p_k, \forall k \in K, s \in S ，$

(6)

$ l_{k s v}^{\prime} \geqslant l_{k s}-M \cdot\left(1-p_k\right), \forall k \in K, s \in S, v \in V, $

(7)

$ l_{k s v}^{\prime} \leqslant l_{k s}, \forall k \in K, s \in S, v \in V, $

(8)

$ \sum\limits_{v \in V} w_{k s v}^{\prime} \leqslant w_{k s}+M \cdot\left(1-p_k\right), \forall k \in K, s \in S, $

(9)

$ w_{k s v}^{\prime} \geqslant w_{k s}-M \cdot p_k, \forall k \in K, s \in S, v \in V, $

(10)

$ w_{k s v}^{\prime} \leqslant w_{k s}, \forall k \in K, s \in S, v \in V_{\circ} $

(11)

式(6)表示第s个stripe中的v个stack的长度和小于等于所在stripe长度。式(7)表示当p_k=1时，第v个stack的长度等于所在stripe的长度；当p_k=0时，原片k第s个stripe中的第v个stack的长度大于0。式(8)表示stack的长度不能超过stripe长度。式(9)表示原片k第s个stripe中的v个stack的宽度和小于等于所在stripe宽度。式(10)表示当p_k=1时，原片k第s个stripe中第v个stack的宽度等于所在stripe的宽度；当p_k=0时，原片k第s个stripe中第v个stack的宽度大于0。式(11)表示stack的宽度不能超过stripe的宽度。

3) 原片k在第三阶段切割后，每个item的长、宽关系如式(12)~(17)。

$ \begin{aligned} & \sum\limits_{i \in N} l_{k s v i}^{\prime \prime} \leqslant l_{k s v}^{\prime}+M \cdot\left(1-p_k\right), \forall k \in K, \\ & s \in S, v \in V, \end{aligned} $

(12)

$ \begin{aligned} & l_{k s v i}^{\prime \prime} \geqslant l_{k s v}^{\prime}-M \cdot p_k-M \cdot\left(1-u_{k s v i}\right), \\ & \forall k \in K, s \in S, v \in V, i \in N, \end{aligned} $

(13)

$ l_{k s v i}^{\prime \prime} \leqslant l_{k s v}^{\prime}, \forall k \in K, s \in S, v \in V, i \in N, $

(14)

$ \begin{aligned} & \sum\limits_{i \in N} w_{k s s i}^{\prime \prime} \leqslant w_{k s v}^{\prime}+M \cdot p_k, \forall k \in K, \\ & s \in S, v \in V, \end{aligned} $

(15)

$ \begin{aligned} & w_{k s i}^{\prime \prime} \geqslant w_{k s v}^{\prime}-M \cdot\left(1-p_k\right)-M \cdot\left(1-u_{k s v i}\right), \\ & \forall k \in K, s \in S, v \in V, i \in N, \end{aligned} $

(16)

$ w_{k s v i}^{\prime \prime} \leqslant w_{k s v}^{\prime}, \forall k \in K, s \in S, v \in V, i \in N_{\circ} $

(17)

式(12)表示原片k第s个stripe中第v个stack里的第i个item的长度和小于等于所在stack长度。式(13)表示当p_k=0时，原片k第s个stripe中第v个stack里的第i个item的长度等于所在stack的长度；当p_k=1时，第i个item的长度大于0。式(14)表示item的长度不能超过stack长度。式(15)表示原片k第s个stripe中第v个stack中的i个item的宽度和小于等于所在stack宽度。式(16)表示当p_k=1时，第i个item的宽度等于所在stack的宽度；当p_k=0时，第i个item的宽度大于0。式(17)表示item的宽度不能超过stack的宽度。

4) 材料旋转放置后的长宽关系如式(18)~(21)。

$ \begin{aligned} & f_{k s v i}+f_{k s v i}^{\prime} \geqslant u_{k s v i}, \forall k \in K, s \in S, \\ & v \in V, i \in N, \end{aligned} $

(18)

$ u_{k s v i} \geqslant f_{k s v i}, \forall k \in K, s \in S, v \in V, i \in N, $

(19)

$ u_{k s v i} \geqslant f_{k s v i}^{\prime}, \forall k \in K, s \in S, v \in V, i \in N, $

(20)

$ f_{k s v i}+f_{k s v i}^{\prime} \leqslant 1, \forall k \in K, s \in S, v \in V, i \in N_{\circ} $

(21)

只有把第i个item放置在原片k第s个stripe第v个stack时，才能决定产品i是横放还是竖放，否则f_ksvi=f′_ksvi=0。

5) 产品横放或竖放的取值如式(22)~(23)。

$ \begin{aligned} & l_{k s v i}^{\prime \prime}=L_i \cdot f_{k s v i}+W_i \cdot f_{k s v i}^{\prime}, \forall k \in K, s \in S ，\\ & v \in V, i \in N ，\end{aligned} $

(22)

$ \begin{aligned} & w_{k s i}^{\prime \prime}=W_i \cdot f_{k s v i}+L_i \cdot f_{k s v i}^{\prime}, \forall k \in K, \\ & s \in S, v \in V, i \in N 。\end{aligned} $

(23)

式(22)表示如果产品i横着放置在第k个原片的第s个stripe的第v个stack中，那么产品i的长度l″_ksvi=L_i；如果产品i竖着放置在第k个原片的第s个stripe的第v个stack中，那么产品i的长度l″_ksvi=W_i。式(23)表示如果产品i横着放置在第k个原片的第s个stripe的第v个stack中，那么产品i的宽度l″_ksvi=W_i；如果产品i竖着放置在第k个原片的第s个stripe的第v个stack中，那么产品i的宽度l″_ksvi=L_i。

6) 每个产品i都要放置在原片上的约束如式(24)~(25)。

$ u_{k s v i} \leqslant y_k, \forall k \in K, s \in S, v \in V, i \in N, $

(24)

$ \sum\limits_{k \in K} \sum\limits_{s \in S} \sum\limits_{v \in V} u_{k s v i}=1, i \in N_{\circ} $

(25)

式(26)~(30)表示尽可能优先使用序号小的原片k、条带s、栈v；式(31)表示决策变量的取值范围。

$ y_k \geqslant y_{k+1}, \forall k \in\{0, 1, 2, \cdots, |K|-1\}, $

(26)

$ l_{k s} \geqslant l_{k, s+1}, \forall k \in K, s \in\{0, 1, 2, \cdots, |S|-1\}, $

(27)

$ w_{k s} \geqslant w_{k, s+1}, \forall k \in K, s \in\{0, 1, 2, \cdots, |S|-1\}, $

(28)

$ \begin{aligned} & l_{k s v}^{\prime} \geqslant l_{k s, v+1}^{\prime}, \forall k \in K, s \in S, \\ & \;\;\; v \in\{0, 1, 2, \cdots, |V|-1\}, \end{aligned} $

(29)

$ \begin{gathered} w_{k s v}^{\prime} \geqslant w_{k s, v+1}^{\prime}, \forall k \in K, s \in S, \\ v \in\{0, 1, 2, \cdots, |V|-1\}, \end{gathered} $

(30)

$ \begin{gathered} p_k, f_{k s v i}, f_{k s v i}^{\prime}, u_{k s v i} \in\{0, 1\}, \forall k \in K, s \in S, \\ v \in V, i \in N 。\end{gathered} $

(31)

3 优化算法

为了降低模型求解的难度，提高运算效率，把模型分解为便于求解的主问题和子问题。具体而言，把模型的原问题限制到一个规模更小的主问题上，采用算法求解主问题的解，然后通过建立子问题寻找满足条件的列，将这些列添加到主问题中，直到找不到能够满足条件的列，算法停止。本文采用遗传算法搜索满足条件的列，每一次的迭代都能提供多个满足条件的列，在加快搜索效率的同时提高解的多样性。

3.1 遗传算法

遗传算法(genetic algorithm, GA)作为一种群优化算法，可广泛应用于排序和调度问题。在板材切割优化问题的三个阶段中，阶段之间切割和每一阶段内切割的产品项item顺序都可抽象为具有优先约束的排序问题，具体步骤如算法1所示。问题采用遗传算法求解能够保证其性能优势。

算法1   遗传算法

输入：种群规模(r)，交叉和变异概率(P_c, P_m)，最大迭代次数(w)，初始切割序列(I)，迭代次数t，切割序列所用板材的数量(f)。

输出：优化的切割序列(X)。

步骤1   初始化。产生种群规模为r的初始种群P；Set t←0。

步骤2   交叉操作。参考文献[15]提出的单点交叉方式，在父代中以概率P_c选择两个排样序列进行交叉操作，产生子代P^C(t)。

步骤3   变异操作。在父代中以概率P_m选择单个序列，交换其两个基因位上对应的item，产生子代P^M(t)。

步骤4   组合P^C(t)和P^M(t)构成种群P′(t)，P′(t)=P^C(t)∪P^M(t)。

步骤5   适应度计算。根据解码算法，依次计算种群P′(t)内序列P′_x(t)对应的板材数量，其中，x=1, 2, …, r。评估P′(t)，并选择最优排样序列P^best(t)，Setf^*←g(P^best(t))。

步骤6   若f^* < f，则更新f←f^*，并保留当前最优序列X←P^best(t)。

步骤7   选择操作。通过精英选择的方式在P(t)和P^best(t)中选择排样序列，构成新种群P(t+1)。

步骤8   Set t←t+1。

步骤9   终止条件。如果算法达到最大迭代次数w则停止迭代，输出最优排样序列X。

遗传算法的设计关键包括：1) 适用于问题结构特点的编码策略；2) 用于邻域的变换产生新解的交叉算子和变异算子；3) 用于筛选与保留优良个体的选择策略。算法固有的种群进化方式，能够保证解向最优方向进化的同时保持多样性，避免算法陷入局部最优。交叉概率和变异概率作为参数控制最优解的局部搜索速率和全局搜索概率。本文采用序列编码的方式编定产品项，即产品项依次分布在染色体的基因上；解码采用顺序插入策略把最优序列解码为产品项在板材上。图 2为方形件切割的编码方式(取item的数量10为例)。根据编码方式和解码策略，设计基于顺序插入的遗传算法求解问题及其模型。

根据编码向量I依次判断各item是否能放到已有原片m_k中。若能放下，则将添加item至原片m_k；否则，新建一个原片m_k放置item。以第一刀竖切为例，产品i进stack条件为

$ w_{k s v}=W_i, l_{k s v}+L_i \leqslant l_{k s}, \sum\limits_s l_{k s} \leqslant L_{\circ} $

(32)

条带stripe新开一个stack的条件为

$ \sum\limits_v w_{k s v}+W_i \leqslant W_{\circ} $

(33)

遗传算法解码流程需要将每个产品依次与已有原片的stack进行比较，当有合适的stack就将该产品放入。最坏情况为每个产品只有一个stack，且无其他产品可加入，则每个产品都要与其他产品的stack进行比对，最大比对n²次。

3.2 列生成算法

列生成算法是一种用于求解比较大规模的线优化问题的算法，通过将原问题转为一个规模更小，使用部分问题的模型是原问题的子问题。然后通过子问题来计算并生成新的变量。

本文上面采用遗传算法求解虽然能够适用于大规模算例，但难以保证求解质量。为了提升算法的求解精度，本文在遗传算法的基础上加入列生成算法。初始可行解和新列的生成采用遗传算法求解。在寻找新列时，选取切割面积利用率最小的θ个原片中的产品，带入遗传算法中重新求解。具体而言，若当前迭代的切割方式解为X，选择X中利用率最低的θ个解，$ \bar{X}=\left\{m_1, m_2, \cdots, m_\theta\right\}$(X中其余解为X′)，继续进行τ+1次迭代。如果迭代次数大于Γ或检验数σ≥0，则算法停止迭代，输出最终结果。综上，在迭代重优化框架内重复执行遗传算法，对板材利用率较低的解进行重优化，提高劣解变换到最优解的可能性，如算法2所示。

由于遗传算法计算一次能够生成多个新解，每个新解都可作为主问题中的新列。因此，新解集合为X^new，检验数σ取值为

$ \sigma=\min \left\{1-\sum\limits_i a_{i k} \mid \forall k \in X^{\text {new }}\right\} 。$

(34)

算法2   列生成算法(CGA)

输入：板材的数量N，产品项i的长度L_i，产品项i的宽度M_i，板材的长度L，产品板材的宽度M，迭代次数τ，切割产品项所用板材的数量z。

输出：优化的切割序列X。

步骤1   初始化设定，τ=0, Γ=10, z^*=∝，其中τ为迭代次数，Γ为最大迭代次数，z^*为目标值。

步骤2   调用遗传算法生成初始切割序列X←GA(N, L_i, M_i, L, M)。

步骤3   根据X构建主问题RMP。

步骤4   求解RMP得到π_i, z，z^*←min(z, z^*)。

步骤5   选取X中θ个解中的产品项构成集合l，X^new←GA(N, L_i, M_i, L, M)。

步骤6   计算校验数σ←min{ $ 1- \sum_{\mathrm{i}} \pi_i \sigma_{i k} \mid \forall k \in X^{\mathrm{new}}, \tau \leftarrow \tau+1$}，通过遗传算法进一步迭代优化序列中的切割序列。

步骤7   更新参数τ和σ，如果条件τ < Γ和σ < 0满足，则继续迭代。

步骤8   将X^new添加至RMP。

步骤9   检查终止条件，如果迭代终止，则结束算法。

4 数值实验与结果分析

本实验的计算机参数配置为：Intel(R) Core(TM) i5-8250U CPU@1.80 GHz，8 GB内存。用CPLEX 12.9.0作为求解模型的求解器。

4.1 数据来源

实验所使用的算例是一个产品订单数据集datasetA，一共包含4组实例，分别命名为dataA1~dataA4，每组实例有1个excel文件描述，文件介绍了每一个item的序号、材质、数量、长度、宽度、订单号。对于每一块板材原片的尺寸，统一为2 440*1 220，即长2 440个单位，宽1 220个单位。每个数据集的材质相同，不额外区分。数据集dataA1~dataA4中每个实例分别有752，731，823，799个产品项。

4.2 实验结果

本文使用Python进行编程，为了验证模型的正确性，对混合整数规划模型使用数据集dataA1的前15个算例进行验证，得到的结果如表 1所示。

可以看出，15个产品项共放在4个原片上面，部分输出算例结果的长和宽与原给定长和宽发生倒置，长和宽发生倒置的产品项为90°放置，并且条带、栈、产品项均满足问题描述的约束条件，验证了模型的正确性和有效性。

根据公式，原片利用率=产品项面积之和/使用原片面积之和。本文通过Python计算输出文件中的产品X方向长度*产品Y方向长度的面积之和，再除以每个数据集利用的原片数量的总面积，计算出原片利用率的结果见表 2。

datasetA是数据集A1~A4中的所有产品，分别按批次、材质、原片进行分类，使每个原片上的产品面积除以原片的总面积，求出dataset A的总原片利用率。

同时，用两种典型的算法即贪心算法与经典遗传算法来使用数据集dataA1进行相同的三阶段齐切割的排样，结果如表 3所示。实验表明，原片的利用率分别提高了6.41个百分点和4.86个百分点，本文所提及的算法依然有一些优势。

对结果进行进一步验证，本文以dataA1结果为例，将所有排样后的原片进行可视化处理，见图 3。经验证，结果均符合问题约束，且已在最大程度上最小化原片用量。

4.3 实验结果分析

每个数据集原片利用率的分布图如图 4所示。可以看出，4个数据集的利用率均呈现右偏分布，说明本文的模型和算法的求解结果呈现向好性，原片利用率较高。从整体上看，4个数据集的原片利用率较多分布在85%~90%之间。

求解难度取决于模型的0~1变量的维度，本文的0~1变量共4个维度。为了进一步降低模型的求解难度，本文采用CPLEX对模型进行求解，计算dataA1的10~20个算例的求解时间(见表 4)。从表 4可以看出，模型求解时间随产品数量的增加而迅速增加。11个算例求解时间为73.5 s，而20个算例的求解时间为450.14 s。求解规模扩大1倍，求解时间几乎是原来6倍。

列生成算法求解数据集dataA1的结果在生成初始解后前4次求解子问题均找到了可以改进的新列，而超过4次后算法无法更新求解结果，检验数σ始终在-1左右，无法大于0。进一步分析可知设计的遗传算法迭代和解码策略较为有效，能够快速找到可更新的新列。但遗传算法在解码时第一阶段的切法固定为竖切，且不会再旋转产品，导致无法找到更优的列。算法迭代达到最大次数后停止计算，求解时间约为5 min。总体来看，在顺序插入策略设计下的该算法求解过程较为有效，能够快速找到一个较优解。

5 结语

本文针对二维三阶段齐切割下料问题，将问题抽象为尺度约束的切割问题，依照三个阶段的切割方向和要求，为实现板材原片利用率最大化，通过建立混合整数规划模型，利用CPLEX来求解，由于精确算法的求解的规模很小，随着规模的增大而难以求解。因此，对于大规模的算例，为提高算法求解效率并生成满意解，结合列生成算法的快速求解性能和遗传算法的多样性搜索优势，设计了列生成与遗传算法的混合算法求解模型。具体而言，用列生成算法先求解出新列，选取利用率最小的产品项，返回到遗传算法中重新求解。设计基于优先插入策略的解码算法，使得利用率最大化与算法求解效率得到平衡，提高算法的求解性能。模型和算法可使得板材的利用率在85%以上且求解时间相对较少，所设计的算法在解的质量和计算时间上具备显著优势，能够推广到类似组合优化问题的求解中，有效降低板材原片的使用量、提高其利用率，服务于生产。