馬英鈞，鐘俊江

（廈門理工學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院，福建 廈門 361024）

排樣優(yōu)化問題本質(zhì)上也稱切割填充問題，優(yōu)化的目的是合理規(guī)劃方形產(chǎn)品在板材上的布局，減少下料過程中的板材浪費，簡化切割過程。下料作為眾多制造企業(yè)生產(chǎn)鏈中產(chǎn)品及零部件生產(chǎn)的第一道工序，消耗的材料和資源不容小覷，如何提高材料利用率，降低原材料消耗，是企業(yè)減少資源和能源浪費，承擔(dān)環(huán)境保護責(zé)任所要解決的關(guān)鍵問題。

針對排樣優(yōu)化問題，當(dāng)前已提出一些計算模型。王竹婷等［1］將層次聚類思想引入矩陣排樣優(yōu)化問題中，通過計算矩形組件間的結(jié)合度，將結(jié)合度最高的組件進行合并，并重復(fù)該過程來實現(xiàn)優(yōu)化方案設(shè)計。王偉等［2］提出了一種基于捕食策略的遺傳算法，通過對編碼、遺傳算子和適應(yīng)度算子進行改進，并結(jié)合最低輪廓線搜索算法來獲得最優(yōu)布局。曾曉亮等［3］利用六元數(shù)組對矩形組件進行表征，并利用多島遺傳算法來設(shè)計排樣方案，結(jié)果表明，該方案具有較高的利用率和穩(wěn)定性。近年來，陳仕軍等［4］提出反悔算子、距離受限鄰域算子、滿足容忍度3種策略來改進傳統(tǒng)的鄰域搜索算法，通過與以往方法的結(jié)果對比發(fā)現(xiàn)，該方法具有很高的求解效率。吳繼聰?shù)龋?］介紹了多種Meta-Heuristic 算法在排樣優(yōu)化研究中的應(yīng)用，并分析不同算法的性能和適用場景。與之前的方形組件的排樣優(yōu)化研究不同，張闖等［6］研究二維橢圓零件的排樣優(yōu)化問題，提出了一種在仿射坐標(biāo)系下的變換，并建立整數(shù)規(guī)劃模型。以上成果雖然推動了排樣優(yōu)化問題的研究，但是它們僅考慮如何排樣以使材料最省，很少考慮到機器的具體切割限制，比如每次的切割可以保證板材分離及切割的次數(shù)不能過多的限制等?；诖?，針對多約束排樣優(yōu)化問題的特點，本文提出了一種兩階段遺傳算法和貪婪策略相結(jié)合的排樣優(yōu)化方法，建立產(chǎn)品布局和條帶布局的數(shù)學(xué)模型，利用一種兩階段遺傳算法來進行模型求解，并設(shè)計有效的解碼方案提升模型的求解效率。同時，為了進一步提升利用率，針對“條帶余料”和“板材余料”建立2種基于貪婪策略的算法模型，并在多個數(shù)據(jù)集上執(zhí)行計算，以驗證本文算法的有效性。

1 問題分析

本研究的問題引自2022 年“中國光谷·華為杯”研究生數(shù)學(xué)建模競賽B 題第一問。本問題中的切割需要滿足以下條件：1）只考慮“齊頭切”的切割方式（直線切割、切割方向垂直于板材一條邊，并保證每次直線切割板材可分離成2塊）；2）切割階段數(shù)不超過3，同一個階段切割方向相同；3）假定板材原片僅有一種規(guī)格且數(shù)量充足；4）排樣方案不用考慮鋸縫寬度（即切割的縫隙寬度）影響；5）最終切割生成的產(chǎn)品項是完整的，非拼接而成。圖1是一種有效的3階段切割方式及其生成的模塊。

圖1 一種3階段切割方式及其生成模塊簡圖Fig.1 A three-stage cutting mode and modules it generated

圖1 中：實豎線表示第一次切割得到兩個模塊分別是條帶1 和條帶2；長橫虛線表示對于條帶的切割（即第二次切割）得到6個棧分別是棧1、棧2、棧3、棧4、棧5和棧6；短豎虛線表示對于棧的切割（即第三次切割）最終獲得17個產(chǎn)品。由圖1可以看出，以上的每次切割都是沿著板材的一條邊進行的，并且每次切割都將板材分成2段。對于該問題直接進行二維布局，不僅計算復(fù)雜度高，而且很有可能導(dǎo)致不滿足“切割階段不超過3” 的約束。由圖1可知，第二刀切割會產(chǎn)生多個棧，每個棧都是由邊長相等的產(chǎn)品組成的，因此，研究等邊長的產(chǎn)品可以在一定程度上提升板材的利用效率。

為了減少切割的次數(shù)，先將邊長相等的產(chǎn)品拼接為條帶，并將條帶沿著板材的長邊放置。因此，根據(jù)產(chǎn)品的邊長特點，將其分為3個類別：1）類別1包含有相等的邊長，并且相等邊長小于W（板材的寬）的產(chǎn)品；2）類別2 包含邊長大于W的產(chǎn)品；3）類別3 包含與其他產(chǎn)品的邊長都不相等的產(chǎn)品。對于類別1，建立一階段模型來實現(xiàn)產(chǎn)品組合為條帶優(yōu)化；對于類別1 得到的條帶和類別2 的產(chǎn)品（每個作為一個條帶），建立二階段模型來實現(xiàn)條帶在板材上的布局優(yōu)化；對于邊長不相等的產(chǎn)品（類別3），利用前兩步的廢料和新板材，執(zhí)行余料再利用。具體求解框架見圖2。

圖2 多約束排樣優(yōu)化問題的整體求解框架Fig.2 Solution framework for multi-constraint layout optimization

2 基于兩階段遺傳算法的產(chǎn)品布局優(yōu)化

本節(jié)主要通過兩階段遺傳算法來實現(xiàn)類別1 和類別2 的產(chǎn)品在板材上的優(yōu)化布局，主要包含3 個步驟：1）建立產(chǎn)品組合優(yōu)化數(shù)學(xué)模型；2）建立條帶優(yōu)化數(shù)學(xué)模型；3）構(gòu)建兩階段遺傳算法來初步實現(xiàn)兩類產(chǎn)品在板材上的最優(yōu)布局。

2.1 產(chǎn)品組合優(yōu)化數(shù)學(xué)模型的建立

對于物品很少的分組，如果直接組合為條帶，可能會導(dǎo)致空間的浪費。因此，設(shè)置閾值ε，對邊長相等的物品數(shù)大于ε的那些分組拼接為條帶。

令M1表示需要拼接的物品的個數(shù)，li表示第i產(chǎn)品的另一邊（除了相等邊長的另一邊）的長度，M2表示預(yù)估需要的條帶個數(shù)，xij表示第i產(chǎn)品是否放置于條帶j中，當(dāng)?shù)趇產(chǎn)品置于條帶j中時，xij=1，反之，xij=0。為了使得用料最省，要求在不超過每個條帶的限制長度L（板材的長邊）情況下，使得所用的條帶的數(shù)量盡可能少。此時，其模型為

需要注意的是，以dataA1的邊長為58的產(chǎn)品為例，其84個產(chǎn)品另一邊長的總和為100 830，而每個條帶的最大長度為2 440，因此，M＞100 830/2 440 ≈41.32。對于式（1）描述的混合0～1 規(guī)劃問題，變量的個數(shù)至少為84 × 42。

2.2 條帶組合優(yōu)化數(shù)學(xué)模型的建立

式（2）中：δ(x)為判斷函數(shù)，與式（1）中的定義類似。由式（2）可以看出，目標(biāo)函數(shù)要求選取的板材數(shù)盡可能小。第一個約束條件要求每個板材剪裁的條帶的總寬度小于板材的寬度W，第二個約束要求每個條帶必須有一個板材來剪裁，第三個約束條件要求yij是0～1決策變量。

需要注意的是，以dataA1 和閾值ε=10 為例，根據(jù)類別1 拼接得到108 個條帶和類別2 的102 個條帶，一共得到210 個條帶。這些條帶的總寬度為71 754，因此，至少需要的板材數(shù)量N=71 754/1 220 ≥59。也就是說，式（2）描述的模型中決策變量的個數(shù)至少為210 × 59。

2.3 基于兩階段遺傳算法的模型求解

節(jié)2.1 和節(jié)2.2 描述的問題都是混合0～1 規(guī)劃模型，并且模型中決策變量的個數(shù)都比較多，利用傳統(tǒng)的優(yōu)化方法很難求解，甚至很難得到可行解?；诖?，本研究采用遺傳算法進行求解?，F(xiàn)以產(chǎn)品組合優(yōu)化的求解進行介紹。

遺傳算法的優(yōu)化方案包含編碼、生成初始種群、計算適應(yīng)度、交叉、變異等操作。

1）編碼。為了提升編碼效率，本研究使用序號編碼來生成染色體。對于M個產(chǎn)品，任意一條染色體可表示為X={x1，x2，…，xM}，其中{x1，x2，…，xM}表示產(chǎn)品編號{1，2，…，M}的任意排列。染色體X表示的意義是依次實現(xiàn)產(chǎn)品x1，x2，…，xM的剪裁。

2）目標(biāo)函數(shù)。對于染色體X={x1，x2，…，xM}，條帶的長度限制L，產(chǎn)品另一邊長度{l1，l2，…，lM}，計算條帶總數(shù)的計算步驟如下：

Step1將產(chǎn)品項按照染色體X={x1，x2，…，xM}的順序排列；初始化K=0，i=1，j=1，F(xiàn)1=?，Z=0。

Step2將當(dāng)前第i個產(chǎn)品放入Fj中，即Fj={Fj，xi}，并計算Z=Z+lxk。

Step3當(dāng)Z≤L時，表示前條帶有剩余；否則，刪除集合Fj的最后一個元素，選擇下一個條帶，即j=j+1，F(xiàn)j={xi}，Z=0。

Step4i=i+1，若i≤M，執(zhí)行步驟Step2和Step3；否則，返回需要的條帶總數(shù)K=j。

在以上步驟中，集合Fj表示第j條帶剪裁的產(chǎn)品集合，K表示條帶總數(shù)。由以上步驟可以看出，解碼步驟的算法復(fù)雜度為O(n)。本研究中的每個染色體都是利用貪心算法進行解碼，不僅保證每個染色體是可行解，而且是局部最優(yōu)的。

3）交叉和變異。由于本文采用序號編碼，在交叉的時候可能會導(dǎo)致染色體損壞。因此，采用部分交叉映射來對染色體進行修正［7-9］。部分交叉映射的主要思想是：對兩個待交叉染色體交叉區(qū)域內(nèi)的基因互換，并利用交叉區(qū)域內(nèi)的映射關(guān)系將交叉區(qū)域外的基因進行修正。為了提升計算效率，保證變異之后染色體的有效性，變異操作采用基因交換的方式，即隨機選擇待變異染色體兩個位置的基因進行交換［10］。

4）重組。為了提升算法效率，保證優(yōu)秀染色體可以進入下一代，本文設(shè)置代溝操作，并在每一次交叉變異之后，選取上一代最優(yōu)的10%的個體直接進入下一代。

遺傳算法的具體流程見圖3。

圖3 遺傳算法流程圖Fig.3 Genetic algorithm flow

綜上，首先利用遺傳算法求解節(jié)2.1的問題來獲取產(chǎn)品組裝為條帶的最優(yōu)方案，然后再利用遺傳算法求解節(jié)2.2實現(xiàn)條帶在板材上的最優(yōu)布局。

3 基于貪心策略的余料再利用

在產(chǎn)品組合優(yōu)化和條帶組合優(yōu)化的過程中，都可能會出現(xiàn)余料，合理利用這些余料可以在很大程度上提升板材的利用效率。因此，基于貪心策略［11-12］，本文提出兩方面的余料利用策略，即產(chǎn)品組合的余料再利用和條帶組合的余料再利用。

3.1 產(chǎn)品組合的余料再利用

條帶剪裁產(chǎn)品的過程中，若條帶中產(chǎn)品項的總長度小于L，導(dǎo)致余料S1產(chǎn)生。圖4 給出了余料S1的再利用示意圖。

圖4 余料S1的再利用示意圖Fig.4 Reuse of residual material S1

如圖4所示，對于組裝條帶產(chǎn)生的余料S1，其高為h1，寬為w1，從剩余的產(chǎn)品中選擇可以放入S1的產(chǎn)品集合，即={x|min {hx，wx}＜min {h1，w1}且max {hx，wx}＜max {h1，w1}}。從集合中選擇面積最大的產(chǎn)品C1進行放置，為保證切割總數(shù)不超過3 的約束，C1的左下角必須與余料S1的左下角重合。此時，如圖4兩邊的兩個圖所示，由于C1的擺放方式不同，可得到不同的可使用余料分別為和，容易看出余料可使用面積更大，因此，按照圖4 中最右圖的方式擺放。余料S1的再利用步驟如下：

Step1令余料S1的寬為w、高為h，且剩余m個需要剪裁產(chǎn)品{C1，C2，…，Cm}的寬分別為{w1，w2，…，wm}，高分別為{h1，h2，…，hm}，當(dāng)前可用產(chǎn)品集合T=?。

Step2當(dāng)min{w，h}＞min{wi，hi} 且 max{w，h}＞max{wi，hi}，說明此時第i個產(chǎn)品項可利用余料S1剪裁，更新T={T，i}。

Step3i=i+1，若i≤M，執(zhí)行步驟Step2；否則，執(zhí)行Step4。

Step4從T中挑選面積最大的第k產(chǎn)品放入余料S1中，且保證該產(chǎn)品左下邊頂點與S1左上頂點重合，計算此時可用余料。

Step5計算產(chǎn)品旋轉(zhuǎn)90o后的可用余料，當(dāng)旋轉(zhuǎn)后依舊可以放置，并且＞S′1時，將該產(chǎn)品旋轉(zhuǎn)90o，更新余料S1=，更新余料S1的寬w′和高h(yuǎn)′，T=?；否則，更新余料S1=，更新余料S1的寬w′和高h(yuǎn)′，T=?。

Step6更新步驟Step2、Step3、Step4 和Step5，直至不能找到可放置的產(chǎn)品。返回關(guān)于當(dāng)前余料S1的再利用方案。

根據(jù)以上步驟可以看出，對于任意產(chǎn)品的放置，都需要對所有的可能產(chǎn)品遍歷一次，因此，其算法復(fù)雜度為O(n2)。

3.2 條帶組合的余料再利用

在板材剪裁條帶的過程中，若板材中條帶的總寬度小于W，導(dǎo)致余料S2產(chǎn)生。余料S2的再利用示意圖見圖5。

圖5 余料S2的使用示意圖Fig.5 Reuse of residual material S2

板材剪裁條帶過程中產(chǎn)生的余料如圖5所示。首先，利用貪心策略，從剩余需要剪裁的產(chǎn)品中選擇最優(yōu)的，即滿足剪裁要切，面積最大，且放置方式要保證可利用余料的可利用面積最大。然后，經(jīng)過第一次放置，有2塊余料產(chǎn)生，即余料和余料。對于余料的處理方式與第一步類似，而余料的處理方式如節(jié)3.1余料S1的再利用步驟所示。余料S2的再利用步驟如下：

Step1令余料S2的寬w和高h(yuǎn)，且剩余m個需要剪裁產(chǎn)品{C1，C2，…，Cm}的寬分別為{w1，w2，…，wm}，高分別為{h1，h2，…，hm}。

Step2按照余料S1的再利用算法，尋找產(chǎn)品放入S2中，得到剩余余料和余料。

Step3對剩余余料，重復(fù)余料S1的再利用算法，直至不能放置產(chǎn)品。

Step4對剩余余料，重復(fù)步驟Step2和Step3，直至不能放置產(chǎn)品。輸出余料S2的再利用方案。

4 模型整體求解結(jié)果和分析

4.1 兩階段遺傳算法的優(yōu)化性能分析

對于類別1和類別2中的產(chǎn)品，利用兩階段遺傳算法來獲得產(chǎn)品的初始布局?，F(xiàn)以dataA1中邊長為58 的84 個產(chǎn)品組合條帶和210 個條帶組合在板材上布局為例來分析兩階段遺傳算法的優(yōu)化性能，結(jié)果見圖6。

圖6 關(guān)于dataA1的兩階段遺傳優(yōu)化過程圖Fig.6 Two-stage genetic optimization process for dataA1

由圖6（a）可以看出，初始隨機方案的條帶數(shù)為51，條帶利用率為100 830/(2 440 × 51)=81.03%。隨著算法進行，所需的條帶數(shù)逐漸降低，最終需要的條帶數(shù)為46，條帶利用率為100 830/(2 440 ×46)=89.83%。條帶的數(shù)量降低4 個，條帶的利用率提升8.81%。由圖6（b）可以看出，隨著迭代過程的進行，組裝210個條帶需要的板材數(shù)量逐漸降低。初始隨機生成的組裝方案需要64個板材，板材的橫向利用率為71 754/(1 220 × 70)=84.02%，其中71 754為210個條帶的總寬度；當(dāng)?shù)螖?shù)為150次以后，板材的個數(shù)穩(wěn)定到64個，板材的橫向利用率為71 754/(1 220 × 64)=91.90%，提升了7.88%。

4.2 閾值對模型性能的影響

如節(jié)2.2所述，對于某些存在邊長相等但數(shù)量很少的物品，直接組合為條帶可能會導(dǎo)致板材的浪費。通過設(shè)置閾值ε=2，3，…，20來分析相等邊長物品的數(shù)量與板材利用率的關(guān)系。具體地，當(dāng)ε=2時，考慮所有存在邊長相等的物品（相等邊長小于1 220）；當(dāng)ε=3 時，考慮相等邊長的物品數(shù)量≥3的情況。以dataA1為例，對于不同的閾值，代入以上過程，可得到相應(yīng)的板材利用率，結(jié)果見圖7。

圖7 dataA1中閾值和利用率的關(guān)系Fig.7 Relationship between threshold and utilization in dataA1

由圖7可以看出，隨著閾值的增加，板材的利用率也在逐漸提高，當(dāng)閾值ε=10左右時，板材的利用率最高可達(dá)到82.71%。因此，對于數(shù)據(jù)集1，本文取ε=10，即對那些邊長相等的物品數(shù)量≥10的分組利用第2節(jié)的操作來組合為條帶，邊長相等的物品數(shù)量小于10的個體歸入類別3。

4.3 板材布局

對于2022 年“中國光谷·華為杯”研究生數(shù)學(xué)建模競賽B 題中的dataA1、dataA2、dataA3、dataA4和dataA5這5個數(shù)據(jù)集，利用以上過程來執(zhí)行排樣優(yōu)化，并選取禁忌搜索算法［13-14］進行對比，最終得到的結(jié)果見表1。

表1 排樣優(yōu)化在5個數(shù)據(jù)集上的結(jié)果對比Table 1 Results of layout optimization across five data sets compared

由于并不知道實際的最優(yōu)板材數(shù)量，但可以計算最優(yōu)板材數(shù)量的下界，即“最優(yōu)板材數(shù)量下界”，它通過利用產(chǎn)品項的總面積和除以板材面積，并向上取整得到。由表1 可以看出，本文的方法在5個數(shù)據(jù)集上的板材利用率基本上都可保持在80%以上，并且高于禁忌搜索算法的結(jié)果。其中，對于dataA1，物品總面積為2.486 9×108，需要的板材數(shù)量為101 個，板材的利用率為82.71%。圖8 給出了dataA1的第一個板材上的排樣效果圖。

圖8 dataA1中第一個板材上的產(chǎn)品排樣Fig.8 Product layout on the first plate in dataA1

5 結(jié)論

針對多約束產(chǎn)品排樣問題，提出一種兩階段遺傳算法和貪心策略相結(jié)合的排樣優(yōu)化方法。該方法通過分析產(chǎn)品排樣問題的特征，設(shè)計局部最優(yōu)解碼方案，采用兩階段遺傳算法來實現(xiàn)產(chǎn)品和條帶的最優(yōu)布局，并針對產(chǎn)品余料和條帶余料分別設(shè)計基于貪心策略的再利用方案。利用2022年研究生數(shù)學(xué)建模競賽B題的5種數(shù)據(jù)集進行測試，通過模型對比和分析，驗證了本研究模型的有效性。該模型的建立為有切割次數(shù)和切割限制的排樣優(yōu)化問題提供了一種新的求解方案。下一步的工作將針對多約束排樣優(yōu)化問題的特點建立集成學(xué)習(xí)模型，從而設(shè)計更為有效的鄰域搜索策略，以進一步提升板材的利用率。