運用啟發式算法的木板最優切割方案

徐宗煌，徐劍莆，李世龍，林慧雅，許美燕

（1.福州理工學院 應用科學與工程學院，福建 福州 350506；2.福州理工學院 計算與信息科學學院，福建 福州 350506；3.福州理工學院 商學院，福建 福州 350506 ）

本文討論的問題和應用的數據均來源于2019 年第十六屆五一數學建模競賽B 題.木板切割，實際上是屬于二維下料優化問題，其主要應用在機械加工、切割下料以及工廠車間布局等制造生產加工領域[1].由于二維下料優化問題自身的復雜性，在實際生產應用中，往往會造成原料的大量浪費，從而提高產品成本.因此，如何提高原材料的利用率而節省產品加工成本，具有非常重要的實用價值.

從數學計算復雜性理論看，木板切割的優化問題屬于NP 完全問題[2].目前，國內外許多學者對二維下料優化問題進行了諸多研究，主要是采用啟發式算法、禁忌搜索算法、遺傳算法以及模擬退火算法等大量的優化方法.本文基于循環嵌套啟發式貪心算法、遺傳模擬退火算法以及價值修正的順序啟發式算法等優化方法，分別對切割單個產品、多個產品以及考慮生產任務需求的木板切割優化方案進行了探究分析.

1 模型假設

在問題求解過程中，考慮到實際情況與簡化計算的需要，提出以下假設：1）將木板和產品的長度和寬度均看作是矩形；2）在切割過程中，木板厚度和割縫寬度忽略不計；3）該批木板的材質分布均勻，不會影響切割產品的效果；4）所給的木板和產品尺寸均為真實有效.

2 單個產品木板最優切割方案

2.1 研究思路

在一塊木板上只切割P1 產品，首先利用循環嵌套式的啟發式算法，使得沿木板四條邊方向上的利用率達到最優；再結合Packing 問題的貪心算法，以木板利用率最高為優化目標，逐層優化，最終得到單個產品的最優切割方案.

2.2 模型建立

設木板尺寸為L×W，P1 產品尺寸為l×w，要使木板切割盡可能多的P1，應盡量利用l 和w 的各種組合，使得L 和W 方向上的利用率盡可能高，即對L 和W 邊上同時對l 和w 進行組合優化[3]，使得木板四條邊的尺寸利用達到最優.其優化示意圖如圖1.

圖1 基于循環嵌套啟發式算法的優化示意圖

2.2.1 確定目標函數 顯然，最優切割方案的目的是為了使木板的利用率最高，令μ 為木板的利用率；N 為木板切割P1 產品的數量，則P1 產品的最優切割方案的目標函數為

2.2.2 確定約束條件 如圖1 所示，當木板上L 邊上切割了m 個l 邊，則可以再切割n=[（L-ml）/w]個w邊；而當右W 邊上切割了i 個l 邊，則還可切割w 邊的個數為j=[（W-il）/w]；同理，可根據木板上L 邊上l 的個數p 和右W 邊上l 的個數s 分別確定各自邊上w 的個數q 和t，結合問題的要求與已知條件，主要考慮以下3 個約束條件.

1) 約束條件1

基于保證木板在L 邊和W 邊的利用率，即要保證木板四條邊上所留的空隙不能再放入P1 產品的較小邊，即w 邊，則該約束條件為

2) 約束條件2

基于i 和t 以及p 和n 之間的約束條件為

式(3)中，“[ ]”表示取整符號.

3) 約束條件3

基于保證在切割時不能出現P1 產品之間發生干涉的情況，該約束條件為

2.3 問題求解

基于以上分析，利用在貨物裝載和木材下料等領域應用廣泛的二維矩形Packing 問題的貪心算法[4-7]，同時結合循環嵌套式的啟發式算法[8-9]，以木板利用率最高為優化目標，由外及里，逐層優化，如圖2 所示.利用MATLAB 編程得到P1 產品的最優方案切割圖，如圖3 所示.最優的切割方案為：P1 產品的數量為59 件，木板利用率為98.297 9%.

圖2 模型主程序流程圖

圖3 P1 產品的最優方案切割圖

3 多個產品木板最優切割方案

3.1 研究思路

考慮到P1 和P3 產品的切割次序和切割方向是影響木板切割利用率最重要的因素，將遺傳算法和模擬退火算法結合起來形成自適應遺傳模擬退火算法[10-11].這樣不僅可以大大提高計算的效率，而且可以避免陷入局部最優，從而在木板上切割P1 和P3 產品可以取得比較理想的結果，同時給出木板利用率由高到低排序的前3 種切割方案.

3.2 模型建立

3.2.1 確定目標函數 通過以上分析，顯然，最優切割方案使木板的利用率最高.令μ為木板的利用率，Ni為切割第i 種產品的數量，則最優切割方案的目標函數為

3.2.2 確定約束條件 同樣的，已知木板尺寸為L×W，產品尺寸為li×wi（i=1,3），即P1 產品尺寸為l1×w1，P3 產品尺寸為l3×w3，Ni為切割第i 種產品的數量.而mi表示第i 種產品橫放時所需的行數，ni表示第i種產品豎放時所需的行數，xi表示豎放時一行的產品個數，yi表示橫放時一行的產品個數，ri=0 表示該產品的豎放方式，ri=1 表示該產品的橫放方式.結合問題的要求與已知條件，主要考慮以下兩個約束條件.

1) 約束條件1

基于保證木板在L 邊和W 邊方向上，P1 和P3 產品尺寸和不能超過木板尺寸，則該約束條件為

式(6)中，k 表示有k 種產品.

2) 約束條件2

基于在切割P1 和P3 產品時，其數量關系必須滿足以下限制約束條件

3.3 問題求解

利用自適應遺傳模擬退火算法[12]從一組隨機產生的初始解（初始群體）開始全局最優解的搜索來產生P1 和P3 產品的切割次序以及切割方向，其主要步驟如下.

3.3.1 設計基因編碼 為降低算法復雜性，采用十進制編碼方式對木板切割進行優化，設有n 個切割產品，則切割產品次序編號為1，2，…，n，第i 個切割產品的編號為i，則這n 個待切割產品的一個排列為δ=[x1,x2,…,xn]，其中xi表示排列δ 中第i 個切割產品的編號.由于各個產品在切割過程中可以90°旋轉，因此在排列δ 中為各個切割產品增加旋轉變量ri，即

3.3.2 設計適應度函數 問題的目標在于提高木板的利用率，因此采用最優切割方案的目標函數式(5)作為適應度函數，即

式(9)中，Xi為種群中的某一個個體，代表唯一的產品切割方案，因此f（Xi）即為切割序列Xi的木板利用率，f（Xi）值越大，表明木板切割方案最優.

3.3.3 交叉和變異操作 采用一種自適應調整交叉和變異概率的方法來改善算法的行為和性能，同時利用以下概率調整公式

來調整種群中的某一個個體Xi的交叉和變異概率.式(10)中：Pc和Pm分別為該算法的交叉和變異概率；fb（X）、fw（X）和f（Xi）分別表示每一代所有個體中最優、最差個體以及Xi的適應度值.

3.3.4 模擬退火操作 對經過交叉和變異操作后生成的新種群個體Xi，基于Metropolis 的接受準則，計算新個體被接受的概率，其接受準則為

式(11)中，fi(T)為個體基本變換前適應度；fj(T)為個體基本變換后適應度；T 為當前溫度.

3.3.5 構造初始種群的個體 一半通過優先級函數產生，一半通過隨機數作為優先級產生，優先級函數公式為

式（12）中，Pi為第i 個產品基因優先級；pr為該產品長寬比值所占權重；ps為產品面積所占權重且滿足pr+ps=1；函數生成的隨機數Ri∈（0，1）.

利用MATLAB 編程，將木板、P1 和P3 產品的尺寸輸入，可得到P1 和P3 產品的切割方案，圖4 所示為木板利用率由高到低排序的前3 種方案切割圖.木板利用率前3 的切割方案為：1) P1 產品的數量為0件，P3 產品的數量為48 件，木板利用率為99.172 3%；2) P1 產品的數量為43 件，P3 產品的數量為13件，木板利用率為98.500 0%；3)P1 產品的數量為59 件，P3 產品的數量為0 件，木板利用率為98.297 9%.

4 考慮生產任務需求的最優切割方案

4.1 研究思路

在生產任務需求一定的情況下，考慮到順序啟發式算法可以在木板切割產品過程中，隨著產品的生成數量不斷的增加，其切割所需剩余量也發生相應變化.但傳統的SHP 算法[13-14]在生成木板切割方案時存在一定的缺陷，它容易使得好的切割方案在前面出現，而導致后面的切割方案的材料利用率偏低.采用順序價值修正策略[15-17]，依次生成各個切割方案，并根據該切割方案中產生的產品數來修正產品生產任務剩余量，重復此過程，直至所有產品剩余的生產任務均為零，從而得到木板總利用率最高的切割方案，其主要流程圖如圖5 所示.

圖5 順序啟發式算法流程圖

4.2 模型建立

假設初始化各個產品的價值為產品各自的面積，則生成切割方案可根據單位面積價值的大小確定，且產品的當前待切割方案為Pj=[a1j,a2j,…，anj]，aij為該方式中含產品i 的個數，i=1,2，…，n.而每生成一個切割方案都通過

式(13)中aij＞0，si為產品i 的面積；p＞1 為控制參數；g1和g2為價值修正的控制系數，g1+g2=1，且滿足

式(14)中，di為產品i 的生產任務為產品i 剩余的工作任務需求；Ω 為隨機產生，Ω?且

式(13)可寫成

4.3 問題求解

通過以上分析，利用MATLAB 編程，將木板的尺寸、P1～P4 產品的尺寸以及生產任務輸入，得到木板總利用率最高的切割方案，圖6 所示為完成P1～P4 產品生產任務的木板切割方案圖.表1 為考慮生產任務需求的最優切割方案.

圖6 最優方案切割圖

表1 考慮生產任務需求的最優切割方案

由表1 可以看出，當需要同時完成P1～P4 產品的生產任務時，需要7 種切割方案才能使木板的總利用率最高.此時木板的數量為139 塊，總利用率為97.757 7%.

5 結論

本文基于循環嵌套啟發式貪心算法、遺傳模擬退火算法以及價值修正的順序啟發式算法等優化方法，分別對切割單個產品、多個產品以及考慮生產任務需求的木板切割優化方案進行了探究分析.在保證思路嚴謹的前提下，基于啟發式算法化繁為簡，大大降低了算法的計算復雜度，可操作性強，最終得到較為理想的切割方案，對機械加工、切割下料以及工廠車間布局等制造生產加工的過程有一定理論指導和參考價值.