基于列生成和遺傳算法的三階段齊切割問題

中圖分類號： TP391 文獻標志碼： A

Abstract： In industrial customized production， the three-stage guillotine cutting layout method is often used， and a complete product must be cut after three stages. To address this issue， a mixed integer programming model for two-dimensional guillotine cutting of sheet metal was established with the goal of maximizing sheet metal utilization. The three-stage cutting problem was abstracted as a sorting problem with size constraints. In the first stage， two cutting methods were used： horizontal and vertical cutting. The cut product items could be placed at 0^° or 90^° ， and the subsequent two stages of cutting must meet the requirement of no overlap between any two product items. To improve solution efficiency， the model was decomposed into a main problem and several sub problems， and an iterative re-optimization framework and algorithm for genetic algorithm and column generation were proposed to solve the problem. In each iteration， the genetic algorithm could provide multiple columns that met the conditions and added them as new columns to the main problem. In addition， the algorithm could re-optimize solutions with low utilization of sheet metal， improving the possibility of transforming the inferior solution to the optimal solution. The experimental results showed that in small-scale examples， the model could obtain accurate solutions. The proposed algorithm achieved a plate utilization rate of over 85% in large-scale examples， with a short solving time and could meet the requirements of industrial production.

Key words： three-stage guillotine cutting; mixed integer programming; column generation algorithm; genetic algorithm

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 方形件三階段齊切割圖

Figure 1 Three-stage guillotine diagram of square parts

本文研究的板材原片的切割示意如圖 1 所示，包含了 13 個方形件的切割實例，其中，陰影部分為不能利用的廢料。 在方形件切割過程中需滿足以下約束條件：相同棧（ stack） 里的產品項（ item） 的寬度（或長度） 相同;任意兩個方形件不能有面積重疊，但是允許邊緣重合;方形件可以旋轉，即方形件能以0^° 或 90^° 排放。 同時，本文研究板材二維切割問題，數學模型的建立與算法設計基于如下假設：

1） 板材原片僅有一種規格（ 2 440mm? 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; U_P 是單個批次產品項總數，上限是 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 個產品項的寬度。

第一階段為

原片 k 第一階段為豎切，原片 k 第一階段為橫切。

產品 i 放置的位置為

產品 i 放置在第 k 個原片的第 s 個條帶的第 σ_v 個棧中，其他。

產品 i 橫著放置為

產品 i 橫著放置在第 k 個原片的第 s 個條帶的第 σ_v 個棧中，其他。

產品 i 豎著放置為

產品 i 豎著放置在第 k 個原片的第 s 個條帶的第 σ_v 個棧中，其他。

板材原片使用情況為 表示第 k 個原片未被使用，表示第 k 個原片被使用。

2. 2 數學模型

擬構建的規劃模型的目標是最小化板材的利用量，即最少個數的板材被使用過。

目標函數

約束條件如下。

1） 原片 k 在第一階段切割后，每個 stripe 的長寬關系約束如式 （2）～（5） 。

l_ks?L?（1-p_k），?k∈K，s∈S，

w_ks?W?p_k，?k∈K，s∈S

當 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） 。

l_ksv^′?l_ks，?k∈K，s∈S，v∈V，

w_ksv^′?w_ks-M?p_k，?k∈K，s∈S，v∈V，

w_ksv^′?w_ks，?k∈K，s∈S，v∈V

式（6）表示 第 s 個 stripe 中的 σ_v 個 stack 的長度和小于等于所在 stripe 長度。 式（ 7） 表示當 p_k=1 時， 第 σ_v 個 stack 的長度等于所在 stripe 的 長 度;當p_?=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） 。

l_ksvi^′′?l_ksvi^′-M?p_k-M?（1-u_ksvi），

?k∈K，s∈S，v∈V，i∈N，

s∈S，v∈V，

?k∈K，s∈S，v∈V，i∈N，

式（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 的寬度;當 時， 第 i 個 item 的寬度大于 0。 式（17）表示item 的寬度不能超過 stack 的寬度。

4） 材料旋轉放置后的長寬關系如式（ 18） ～（21） 。

f_ksvi+f_ksvi^′?u_ksvi，?k∈K，s∈S，

v∈V，i∈N，

u_ksvi?f_ksvi^′，?k∈K，s∈S，v∈V，i∈N，

f_ksvi+f_ksvi^′?1，?k∈K，s∈S，v∈V，i∈N

只有把第 i 個 item 放置在原片 k 第 s 個 stripe第 σ_v 個 stack 時，才能決定產品 i 是橫放還是豎放，否則 。

5） 產品橫放或豎放的取值如式 （22）～（23） 。

l^′′_ksvi=L_i?f_ksvi+W_i?f_ksvi^′，?k∈K，s∈S，

v∈V，i∈N_：

w_?svi^′′=W_i?f_ksvi+L_i?f_ksvi^′，?k∈K，

s∈S，v∈V，i∈N

式（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^′′= Li。

6） 每個產品 i 都要放置在原片上的約束如式（24） ～ （25） 。

u_?ksvi?y_?k，?k∈K，s∈S，v∈V，i∈N，

式（26） ～ （30） 表示盡可能優先使用序號小的原片 k 、 條帶 σ_s 、 棧 σ_v ; 式（31） 表示決策變量的取值范圍。

y_k?y_k+1，?k∈{0，1，2，…，|K|-1}

w_ks?w_k，s+1，?k∈K，s∈{0，1，2，…，|S|-1}，

w_ksv^′?w_ks，v+1^′，?k∈K，s∈S，

v∈{0，1，2，…，∣V∣-1}，

3 優化算法

為了降低模型求解的難度，提高運算效率，把模型分解為便于求解的主問題和子問題。 具體而言，把模型的原問題限制到一個規模更小的主問題上，采用算法求解主問題的解，然后通過建立子問題尋找滿足條件的列，將這些列添加到主問題中，直到找不到能夠滿足條件的列，算法停止。 本文采用遺傳算法搜索滿足條件的列，每一次的迭代都能提供多個滿足條件的列，在加快搜索效率的同時提高解的多樣性。

3. 1 遺傳算法

遺傳算 法 （ genetic algorithm， GA） 作 為 一 種 群優化算法，可廣泛應用于排序和調度問題。 在板材切割優化問題的三個階段中，階段之間切割和每一階段內切割的產品項 item 順序都可抽象為具有優先約束的排序問題，具體步驟如算法 1 所示。 問題采用遺傳算法求解能夠保證其性能優勢。

算法 1 遺傳算法

輸入： 種群規模 （r） ， 交叉和變異概率 （P_c ，P_m ），最大迭代次數 Π（wΠ） ，初始切割序列 （I） ，迭代次數 χ_t ，切割序列所用板材的數量 （f） 。

輸出： 優化的切割序列 （X） 。

步驟 1 初始化。 產生種群規模為 r 的初始種群 P;Sett←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_c 評估 P^′（t） ， 并選擇最優排樣序列P^best（t） ， Setf^*←g（P^best（t）） 。

步驟 6 若 f^** ， 并保留當前最優序列 XP^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 為例）。 根據編碼方式和解碼策略，設計基于順序插入的遺傳算法求解問題及其模型。

圖 2 方形件切割的編碼示例

Figure 2 Example of coding for cutting square pieces

根據編碼向量 I 依次判斷各 item 是否能放到已有原片 m_k 中。 若能放下，則將添加 item 至原片 m_k ;否則，新建一個原片 m_k 放置 item。 以第一刀豎切為例，產品 i 進 stack 條件為

條帶 stripe 新開一個 stack 的條件為

遺傳算法解碼流程需要將每個產品依次與已有原片的 stack 進行比較，當有合適的 stack 就將該產品放入。 最壞情況為每個產品只有一個 stack，且無其他產品可加入，則每個產品都要與其他產品的stack 進行比對，最大比對 n² 次。

3. 2 列生成算法

列生成算法是一種用于求解比較大規模的線優化問題的算法，通過將原問題轉為一個規模更小，使用部分問題的模型是原問題的子問題。 然后通過子問題來計算并生成新的變量。

本文上面采用遺傳算法求解雖然能夠適用于大規模算例，但難以保證求解質量。 為了提升算法的求解精度，本文在遺傳算法的基礎上加入列生成算法。 初始可行解和新列的生成采用遺傳算法求解。在尋找新列時，選取切割面積利用率最小的 θ 個原片中的產品，帶入遺傳算法中重新求解。 具體而言，若當前迭代的切割方式解為 X ， 選擇 X 中利用率最低的 θ 個解， （ X 中其余解為 X^′ ），繼續進行 τ+1 次迭代。 如果迭代次數大于 T 或檢驗數 σ?0 ， 則算法停止迭代，輸出最終結果。 綜上，在迭代重優化框架內重復執行遺傳算法，對板材利用率較低的解進行重優化，提高劣解變換到最優解的可能性，如算法 2 所示。

由于遺傳算法計算一次能夠生成多個新解，每個新解都可作為主問題中的新列。 因此，新解集合為 X^new ， 檢驗數 σ 取值為

算法 2 列生成算法（CGA）

輸入：板材的數量 N ，產品項 χ_i 的長度 ， 產品項 i 的寬度 M_i ，板材的長度 L ，產品板材的寬度 M ，迭代次數 τ ， 切割產品項所用板材的數量 z 。

輸出：優化的切割序列 X 。

步驟 1 初始化設定， τ=0，T=10，z^*=∞ ， 其中 τ 為迭代次數， T 為最大迭代次數， 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}- ， 通過遺傳算法進一步迭代優化序列中的切割序列。

步驟 7 更新參數 τ 和 σ ， 如果條件 τ

步驟 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 的序號、材質、數量、長度、寬度、訂單號。 對于每一塊板材原片的尺寸，統一為 2440* 1 220，即長 2 440 個單位，寬 1 220 個單位。 每個數據集的材質相同， 不額外區分。 數據集 dataA1 ～dataA4 中 每 個 實 例 分 別 有 752，731，823，799 個 產品項。

4. 2 實驗結果

本文使用 Python 進行編程，為了驗證模型的正確性，對混合整數規劃模型使用數據集 dataA1的前 15 個 算 例 進 行 驗 證， 得 到 的 結 果 如 表 1所示。

表 1 模型算例結果說明Table 1 Explanation of model calculation result

注：1 表示切割方向為豎切;0 表示切割方向為橫切。

可以看出，15 個產品項共放在 4 個原片上面，部分輸出算例結果的長和寬與原給定長和寬發生倒置，長和寬發生倒置的產品項為 90^° 放置，并且條帶、棧、產品項均滿足問題描述的約束條件，驗證了模型的正確性和有效性。

根據公式，原片利用率 σ=σ 產品項面積之和/ 使用原片面積之和。 本文通過 Python 計算輸出文件中的產品 X 方向長度 ? 產品 Y 方向長度的面積之和，再除以每個數據集利用的原片數量的總面積，計算出原片利用率的結果見表 2。

表 2 數據集求解結果

Table 2 Solution results for dataset

datasetA 是數據集 A1～ A4 中的所有產品，分別按批次、材質、原片進行分類，使每個原片上的產品面積除以原片的總面積，求出 dataset A 的總原片利用率。

同時，用兩種典型的算法即貪心算法與經典遺傳算法來使用數據集 dataA1 進行相同的三階段齊切割的排樣，結果如表 3 所示。 實驗表明，原片的利用率分別提高了 6. 41 個百分點和 4. 86 個百分點，本文所提及的算法依然有一些優勢。

表 3 不同算法對數據集求解結果對比表

對結果進行進一步驗證，本文以 dataA1 結果為例，將所有排樣后的原片進行可視化處理，見圖 3。經驗證，結果均符合問題約束，且已在最大程度上最小化原片用量。

圖 3 dataA1 切割方案效果圖

4. 3 實驗結果分析

每個數據集原片利用率的分布圖如圖 4 所示。可以看出，4 個數據集的利用率均呈現右偏分布，說明本文的模型和算法的求解結果呈現向好性，原片利用率較高。 從整體上看，4 個數據集的原片利用率較多分布在 85%～90% 之間。

圖 4 各數據集原片利用率分布圖

Figure 4 Distribution of original slice utilization rate in different dataset

求解難度取決于模型的 0 ～ 1 變量的維度，本文的 0 ～ 1 變量共 4 個維度。 為了進一步降低模型的求解難度，本文采用 CPLEX 對模型進行求解，計算dataA1 的 10 ～ 20 個 算 例 的 求 解 時 間 （ 見 表 4） 。 從表 4 可以看出，模型求解時間隨產品數量的增加而迅速增加。 11 個算例求解時間為 73. 5 s，而 20 個算例的求解時間為 450.14s 。 求解規模擴大 1 倍，求解時間幾乎是原來 6 倍。

表 4 數據集 dataA1 的部分數據求解時間

Table 4 Partial data solution time for dataset dataA1

列生成算法求解數據集 dataA1 的結果在生成初始解后前 4 次求解子問題均找到了可以改進的新列，而超過 4 次后算法無法更新求解結果，檢驗數 σ 始終在-1 左右，無法大于 0。 進一步分析可知設計的遺傳算法迭代和解碼策略較為有效，能夠快速找到可更新的新列。 但遺傳算法在解碼時第一階段的切法固定為豎切，且不會再旋轉產品，導致無法找到更優的列。 算法迭代達到最大次數后停止計算，求解時間約為 5min 。 總體來看，在順序插入策略設計下的該算法求解過程較為有效，能夠快速找到一個較優解。

5 結語

本文針對二維三階段齊切割下料問題，將問題抽象為尺度約束的切割問題，依照三個階段的切割方向和要求，為實現板材原片利用率最大化，通過建立混合整數規劃模型，利用 CPLEX 來求解，由于精確算法的求解的規模很小，隨著規模的增大而難以求解。 因此，對于大規模的算例，為提高算法求解效率并生成滿意解，結合列生成算法的快速求解性能和遺傳算法的多樣性搜索優勢，設計了列生成與遺傳算法的混合算法求解模型。 具體而言，用列生成算法先求解出新列，選取利用率最小的產品項，返回到遺傳算法中重新求解。 設計基于優先插入策略的解碼算法，使得利用率最大化與算法求解效率得到平衡，提高算法的求解性能。 模型和算法可使得板材的利用率在 85% 以上且求解時間相對較少，所設計的算法在解的質量和計算時間上具備顯著優勢，能夠推廣到類似組合優化問題的求解中，有效降低板材原片的使用量、提高其利用率，服務于生產。

參考文獻：

[1] 秦曉宇， 徐偉， 詹先旭. 定制家具企業訂單組批方式 對板材利 用 率 的 影 響 [ J]. 林 業 工 程 學 報， 2022， 7 （2） ： 193-198. QIN X Y， XU W， ZHAN X X. Effect of order batching rules on utilization rate of panels for customized furniture enterprises[ J] . Journal of forestry engineering， 2022， 7 （2） ： 193-198.

[2] 高勃， 張紅艷， 朱明皓. 面向智能制造的不規則零件 排樣優化算法[ J]. 計算機集成制造系統， 2021， 27 （6） ： 1673-1680. GAO B， ZHANG H Y， ZHU M H. Optimization algorithm of irregular parts layout for intelligent manufacturing [ J] . Computer integrated manufacturing systems， 2021， 27（6） ： 1673-1680.

[ 3] CUI Y D， ZHAO Z G. Heuristic for the rectangular twodimensional single stock size cutting stock problem with two-staged patterns [ J] . European journal of operational research， 2013， 231（2） ： 288-298.

[4] 扈少華， 何寶榮， 武書彥， 等. 多卷材二維下料問題 的一 種 啟 發 式 算 法 [ J] . 鍛 壓 技 術， 2017， 42 （ 9） ： 163-167. HU S H，HE B R，WU S Y，et al. A heuristic algorithm for two-dimensional cutting problem with multiple coils [ J ] . Forging amp; stamping technology， 2017， 42 （ 9 ） ： 163-167.

[5] 覃廣榮， 丘剛瑋， 王坤， 等. 可減少條帶數的矩形件 二維下料算法[ J] . 鍛壓技術， 2022， 47（1） ： 63-68. QIN G R， QIU G W， WANG K， et al. Two-dimensional blanking algorithm reducing the number of strips for rectangular parts [ J ] . Forging amp; stamping technology， 2022， 47（1） ： 63-68.

[6] 黎鳳潔， 胡小春， 陳燕. 面向制造業的可加工性矩形 件優化下料方法[J]. 鄭州大學學報（理學版）， 2021， 53（3） ： 85-92. LI F J， HU X C， CHEN Y. Manufacturing-oriented machinability rectangular parts optimization cutting stock method[ J] . Journal of Zhengzhou university （ natural science edition） ， 2021， 53（3） ： 85-92.

[7] WUTTKE D A， HEESE H S. Two-dimensional cutting stock problem with sequence dependent setup times[ J] . European journal of operational research， 2018， 265（ 1） ： 303-315.

[8] FURINI F， MALAGUTI E. Models for the two-dimensional two-stage cutting stock problem with multiple stock size[ J] . Computers and operations research， 2013， 40 （8） ： 1953-1962.

[9] CINTRA G F， MIYAZAWA F K， WAKABAYASHI Y， et al. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation [ J ] . European journal of operational research， 2008， 191（1） ： 61-85.

[10] FURINI F， MALAGUTI E， MEDINA DURáN R， et al. A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size[ J] . European journal of operational research， 2012， 218（1） ： 251-260.

[11] WANG D N， XIAO F， ZHOU L， et al. Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation[ J] . European journal of operational research， 2020， 286（2） ： 547-563.

[12] 蘇俊， 徐震浩， 顧幸生. 基于 VNABC 的多規格板材二 維下料問題[ J]. 華東理工大學學報（ 自然科學版）， 2023， 49（5） ： 712-723. SU J， XU Z H， GU X S. Two-dimensional cutting stock problem of multi-specification plates based on VNABC [ J] . Journal of East China university of science and technology， 2023， 49（5） ： 712-723.

[13] MOSTAJABDAVEH M， SALMAN F S， TAHMASBI N. Two dimensional guillotine cutting stock and scheduling problem in printing industry[ J] . Computers amp; operations research， 2022， 148： 106014.

[14] LUO Q， DU B， RAO Y Q， et al. Metaheuristic algorithms for a special cutting stock problem with multiple stocks in the transformer manufacturing industry[ J] . Expert systems with applications， 2022， 210： 118578.

[15] MENG Q， WANG X C. Intermodal hub-and-spoke network design： incorporating multiple stakeholders and multi-type containers[ J] . Transportation research part B： methodological， 2011， 45（4） ： 724-742.