陳 燕，鄭欣亮，魯淑飛，胡小春

(1.廣西大學(xué) 計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004；2.廣西財(cái)經(jīng)學(xué)院 信息與統(tǒng)計(jì)學(xué)院，廣西 南寧 530007)

0 引言

在中國制造2025和雙碳目標(biāo)背景下，發(fā)展資源節(jié)約型、環(huán)境友好型的智能制造業(yè)已成為緊迫要求[1-2]。二維下料問題(Two Dimensional Cutting Stock Problem, TDCSP)廣泛存在于汽車、造船等產(chǎn)品制造過程中,該類問題的下料常采用火焰、等離子或激光等分離技術(shù)進(jìn)行切割[3]?？紤]切割成本的優(yōu)化下料算法能夠使企業(yè)以更低的材料成本和切割成本完成相應(yīng)的訂單需求，進(jìn)而達(dá)到節(jié)約資源、降低能耗和減少碳排放的目的。

目前，已有一些研究從不同方面實(shí)現(xiàn)了矩形件下料的多目標(biāo)優(yōu)化。文獻(xiàn)[4-6]研究了余料的再利用問題，能較好地減少整個(gè)生產(chǎn)周期的下料成本，并提高余料在未來生產(chǎn)周期中的可用性;文獻(xiàn)[7]針對(duì)二維鋼卷下料問題，不僅考慮最小化剪切損耗，還考慮固定時(shí)間和更換速度，提出一種由簇群、排序、條帶化和整數(shù)規(guī)劃組成的混合啟發(fā)式算法;文獻(xiàn)[8]同時(shí)考慮剪切損耗和機(jī)器設(shè)置成本，提出一種混合線性規(guī)劃模型的基因算法;文獻(xiàn)[9]采用可并行計(jì)算的順序分組啟發(fā)式算法，實(shí)現(xiàn)了最小化板材數(shù)量和減少排樣方式的雙目標(biāo)優(yōu)化;文獻(xiàn)[10]提出連分?jǐn)?shù)分支定界算法，在提高時(shí)間效率的同時(shí)能夠有效地簡化切割工藝;文獻(xiàn)[11]考慮材料成本和機(jī)器設(shè)置成本，提出成本均衡利用率算法，獲得總成本之和最小的下料方案;文獻(xiàn)[12]采用列生成框架和三段式布局圖設(shè)計(jì)，通過減少切割刀數(shù)，以實(shí)現(xiàn)材料成本與切割成本之和最小;文獻(xiàn)[13]通過研究任意給定布局圖的切割順序，以獲得較高材料利用率和較少切割行程的下料方案;文獻(xiàn)[14]綜述了有關(guān)激光切割路徑生成文獻(xiàn)，確定了切割路徑生成的研究趨勢(shì)和切入點(diǎn);文獻(xiàn)[15-16]利用共邊切割的優(yōu)勢(shì)，分別提出階梯型共邊切割策略和啟發(fā)式共邊排樣算法，以減少切割路徑長度、提高切割效率;文獻(xiàn)[17]綜合考慮原材料利用率高、切割加工路徑短等優(yōu)化目標(biāo)，提出一種基于候選板條的連續(xù)啟發(fā)式排樣算法，并在此基礎(chǔ)上提出采用同質(zhì)條帶共邊切割策略分離矩形件，實(shí)驗(yàn)結(jié)果表明所提算法在保證高原材料利用率的同時(shí)，能有效減少切割總路徑;文獻(xiàn)[18]使用包含材料成本和切割成本的綜合成本最小作為下料方案的優(yōu)化目標(biāo)，應(yīng)用順序價(jià)值校正(Sequential Value Correction, SVC)算法框架求解，并以所含矩形件價(jià)值最大作度量標(biāo)準(zhǔn)生成布局圖。SVC的每一次迭代同時(shí)考察多種板材，從中選擇產(chǎn)出率最大者作為當(dāng)前布局圖。文獻(xiàn)[19]在條帶切割的基礎(chǔ)上提出同質(zhì)塊切割策略，根據(jù)同質(zhì)條帶有無余料、條帶所含矩形件數(shù)的奇偶性設(shè)計(jì)板材的切割路徑，以減少切割成本。

目前，針對(duì)矩形件下料問題的研究大部分采用一刀切(guillotine cutting)工藝[20]，但該工藝存在剪切厚度能力有限、工件表面易塌陷變形等缺點(diǎn)。因此本文研究考慮切割成本的非一刀切(non-guillotine cutting)矩形件下料問題。目前針對(duì)該類問題的研究主要存在以下局限：在切割路徑優(yōu)化策略上沒有充分挖掘共邊切割的潛能；在算法設(shè)計(jì)上，一般是先考慮減少材料的使用量，降低切割成本只是作為輔助的優(yōu)化目標(biāo)，少量文獻(xiàn)在下料方案優(yōu)化層面將二者作為整體，但求解布局圖的子問題依然沒有將二者同時(shí)考慮。因此，本文提出兩點(diǎn)改進(jìn)：①利用不同條帶組成的等高塊共邊特性提出等高塊切割策略，并在生成布局圖的過程中設(shè)置條帶優(yōu)先級(jí)，盡可能多地生成等高塊，以充分挖掘共邊切割潛力；②提出在生成單板材布局圖時(shí)，以板材綜合價(jià)值(板材布局矩形件總價(jià)值與切割成本之差)最大作為優(yōu)化目標(biāo)，通過求解有界背包問題生成當(dāng)前板材布局圖，以板材產(chǎn)出率最高作為優(yōu)選目標(biāo)確定布局圖和所使用的板材。

1 數(shù)學(xué)模型及切割策略

1.1 問題描述及數(shù)學(xué)模型

本文討論的多規(guī)格板材的矩形件下料問題可描述為：在n種長為Lj，寬為Wj，供應(yīng)量為Dj(其中j=1,…,n)的板材上按照生產(chǎn)工藝要求切割出m種長為li，寬為wi，需求量為di(其中i=1,…,m)的矩形件。在生成布局圖的過程中，要求矩形件正交排列、互不重疊且不超過當(dāng)前所使用板材的邊界。假設(shè)下料方案有K種布局圖，則其整數(shù)規(guī)劃模型為：

(1)

s.t.

(2)

(3)

(4)

1.2 等高塊的切割策略

1.2.1 等高塊的概念

1.2.2 等高塊共邊切割策略

以等高塊規(guī)則對(duì)布局圖進(jìn)行塊的劃分，塊間采用“直線型”切割路線進(jìn)行分離，相鄰條帶內(nèi)的矩形件采用“之”字型切割路線進(jìn)行分離。等高塊的共邊切割規(guī)則如下：

板材上條帶布局后存在無余料生成和有余料生成兩種情況，條帶的布局存在水平和垂直兩個(gè)方向，同時(shí)條帶中所含的矩形件個(gè)數(shù)有奇偶之分，因此將等高塊分為8種類型。每個(gè)等高塊共有4個(gè)可供切割的切入點(diǎn)，分別為4個(gè)頂點(diǎn)，默認(rèn)板材左上角為最初切入點(diǎn)，后續(xù)塊的起點(diǎn)是根據(jù)與前一塊的切割結(jié)束點(diǎn)之間的最短空程來選擇。這8種類型等高塊以其左上角為切割起始點(diǎn)的路徑示意圖如圖2所示(其他3個(gè)角類似)，需要注意的是由于同質(zhì)塊是等高塊的特殊形式，圖2中等高塊共邊切割同樣適用于同質(zhì)塊。

2 算法設(shè)計(jì)與實(shí)現(xiàn)

求解多規(guī)格板材下料方案的算法采用SVC主框架[19]，并對(duì)其中的單板材布局圖生成算法進(jìn)行改進(jìn)，即在生成單板材布局圖時(shí)同時(shí)考慮布局圖所含矩形件價(jià)值與切割成本，在不影響材料利用率的前提下，盡可能多地生成等高塊。

2.1 考慮切割成本的單板材布局圖生成算法 SinglePattern()

2.1.1 算法設(shè)計(jì)

本文以布局圖的綜合價(jià)值最大作為優(yōu)化目標(biāo)。假設(shè)板材的長寬分別為x和y，用F(x,y)表示該板材上的綜合價(jià)值，因此最優(yōu)布局圖的求解模型可表示為：

(2)

其中：ci為第i種矩形件的價(jià)值;qi為布局圖所含第i(i=1,…,m)種矩形件的個(gè)數(shù);P為布局圖的切割成本;ri為第i種矩形件的剩余需求量;λ為非負(fù)整數(shù)，其值大小表示對(duì)切割成本的重視程度。

設(shè)lmin，wmin分別為矩形件尺寸中的最小長度和最小寬度，在尺寸為x×y的板材上生成同質(zhì)條帶的多級(jí)規(guī)范布局方式，板材的綜合價(jià)值為F(x,y)，切割成本為P(x,y)，則動(dòng)態(tài)規(guī)劃的遞推公式如下：

當(dāng)x

(3)

算法使用兩個(gè)遞歸函數(shù)來實(shí)現(xiàn)當(dāng)前規(guī)格板材最佳布局圖的生成，SinglePattern()負(fù)責(zé)進(jìn)行主板布局圖的生成，PlusPattern()負(fù)責(zé)生成剩余子板的布局圖，并返回剩余子板所含矩形件總價(jià)值與整個(gè)板材布局圖的切割成本之差的值。具體實(shí)現(xiàn)將在2.1.2節(jié)進(jìn)行介紹。

設(shè)F(i,x)表示排入由第i種矩形件組成的條帶后的分支綜合價(jià)值，則F(i,x)=條帶價(jià)值+(剩余子板所含矩形件總價(jià)值-λ×整板布局圖切割路徑總長度)，四種不同類型的同質(zhì)條帶對(duì)應(yīng)的分支綜合價(jià)值如下：

FXX(i,x)=vXX(i,x)+PlusPattern(x,y-wi)，i=1,…,m；

FXY(i,x)=vXY(i,x)+PlusPattern(x,y-li)，i=1,…,m；

FYX(i,y)=vYX(i,y)+PlusPattern(x-li,y)，i=1,…,m；

FYY(i,y)=vYY(i,y)+PlusPattern(x-wi,y)，i=1,…,m；

考慮切割成本的單板材布局圖生成過程如圖3所示。在生成布局圖的過程中，每次確定布局一根同質(zhì)條帶，直到滿足所有矩形件需求或者剩余子板不能布局任何剩余需求的矩形件為止，圖中條帶的確定順序?yàn)閍3→b1→c2→d2。考察布局新條帶的方法為：遍歷每種有剩余需求的矩形件，針對(duì)每一種矩形件，考慮XX、XY、YX、YY四種條帶布局類型(以矩形件1生成的條帶為例)，而對(duì)于每種類型的條帶，會(huì)產(chǎn)生一個(gè)剩余子板，剩余子板則根據(jù)條帶產(chǎn)出率進(jìn)行布局并返回(剩余子板所含矩形件總價(jià)值-λ*整板布局圖切割路徑總長度)的值。以條帶分支綜合價(jià)值大為目標(biāo)，確定新布局的條帶并記錄對(duì)應(yīng)的條帶信息。

2.1.2 算法實(shí)現(xiàn)

函數(shù)SinglePattern()用于生成單板材最佳布局圖，其偽代碼如下：

1 SinglePattern()

2 初始化剩余子板最大綜合價(jià)值F(x,y)_max=0，取得最大綜合價(jià)值時(shí)條帶所含矩形件號(hào)maxID=0

3 for(i=1 to nLeftTypes)

4 if(第i種矩形件剩余需求不為0)

5 if(剩余子板大小不能布局第i種矩形件)then Continue

6 else(令F(x,y)=max{FXX(i,x),FXY(i,x),FYX(i,y),FYY(i,y)})//需調(diào)用PlusPattern()

7 if(F(x,y)>F(x,y)max)then F(x,y)_max=F(x,y),maxID=i

8 if(maxID=0)then return

9 else

10 更新布局圖信息，包括新增條帶類型、所含矩形件種類與個(gè)數(shù)，以及已布局條帶總個(gè)數(shù)、所含矩形件總價(jià)值fVal、總面積fArea等

11 根據(jù)新增布局條帶類型更新剩余子板尺寸

12 遞歸調(diào)用SinglePattern()

其中：步驟2初始化剩余子板最大綜合價(jià)值和取得最大綜合價(jià)值時(shí)條帶所含矩形件號(hào)。步驟3～步驟7為遍歷所有剩余種類的矩形件，并找出使剩余子板綜合價(jià)值最大的一根條帶作為布局圖的新增條帶。其中步驟6為考察第i矩形件的4種布局類型并選擇綜合價(jià)值最大的布局方式。步驟8用于判斷是否已完成板材布局圖的生成，若完成則退出函數(shù)，否則轉(zhuǎn)步驟10～步驟12。其中，步驟10為更新布局圖信息，步驟11為更新剩余子板尺寸，步驟12為遞歸調(diào)用自身函數(shù)以循環(huán)生成新增條帶直至完成板材布局圖的生成。

函數(shù)PlusPattern()返回當(dāng)前剩余子板所含矩形件總價(jià)值與整板布局圖總切割成本之差的值，其偽代碼如下：

1 PlusPattern()

2 接收剩余子板尺寸(x,y)，初始化條帶最大產(chǎn)出率Omax=0，剩余子板已布局矩形件總價(jià)值V=0

初始化矩形件剩余需求，并保存主板已布局條帶的相關(guān)信息(條帶類型、含矩形件種類及個(gè)數(shù))

3 do{ //以條帶產(chǎn)出率最大作為擇優(yōu)條件循環(huán)布局剩余子板

4 for(i=1 to nLeftTypes)

5 若第i種矩形件還有剩余需求且能夠放入剩余子板，令O=max{uXX(i,x),uXY(i,x),uYX(i,y),uYY(i,y)}求出第i種矩形件四種布局圖中產(chǎn)出率最大的條帶

6 若O=Omax且此條帶與前一根已布局條帶共邊或O>Omax，則令Omax=O，并更新條帶信息

7 if(存在產(chǎn)出率最大的條帶)

8 將此條帶布局到剩余子板，更新布局此條帶后的相關(guān)信息，包括該條帶布局類型、所含矩形件種類及數(shù)量、矩形件剩余需求、主板已布局條帶數(shù)量，更新剩余子板已布局矩形件總價(jià)值V=V+此條帶價(jià)值，根據(jù)新增條帶布局類型更新剩余子板尺寸，重置Omax=0

9 else break

10 while(true)

11 根據(jù)等高塊切割規(guī)則計(jì)算當(dāng)前整板布局圖的切割路徑總長度cutLen

12 根據(jù)板材綜合價(jià)值計(jì)算公式計(jì)算當(dāng)前整板布局圖的綜合價(jià)值F(x,y)=fVal+V-λ*cutLen

13 if(F(x,y)>F(x,y)max)

14 更新整板布局圖最大綜合價(jià)值、切割路徑總長度、布局圖所含條帶個(gè)數(shù)。記錄最佳布局圖條帶信息。

15 return V-λ*cutLen

其中：步驟2接收函數(shù)SinglePattern()中步驟11更新后的剩余子板尺寸，并初始化條帶最大產(chǎn)出率和剩余子板已布局條帶總價(jià)值，初始化矩形件剩余需求和主板已布局的條帶信息。步驟3～步驟10對(duì)剩余子板進(jìn)行條帶布局。其中步驟4～步驟8每執(zhí)行一次便確定布局一根條帶，直至剩余子板布局完成。步驟4至步驟6遍歷每種剩余矩形件的4種條帶布局類型，以條帶產(chǎn)出率最大作為選擇待布局條帶的目標(biāo)，其計(jì)算公式為：

若出現(xiàn)條帶產(chǎn)出率相等的情況，則優(yōu)先放置與已布局的上一根條帶共邊的條帶從而形成等高塊。步驟11根據(jù)等高塊切割規(guī)則計(jì)算當(dāng)前整板布局圖的切割路徑總長度。步驟12為計(jì)算當(dāng)前整板布局圖的綜合價(jià)值。步驟13判斷當(dāng)前整板布局圖的綜合價(jià)值是否大于已記錄的整板布局圖的最大綜合價(jià)值，若是則執(zhí)行步驟14更新整板布局圖相關(guān)信息，并記錄布局圖所含條帶信息為最佳布局圖條帶信息。步驟15返回剩余板材所含矩形件總價(jià)值與整板布局圖切割成本之差的值供函數(shù)SinglePattern()調(diào)用。

2.2 最優(yōu)布局圖選擇算法GetPattern()

SVC啟發(fā)式算法每次遍歷所有剩余規(guī)格板材并調(diào)用單板材布局圖生成算法生成布局圖，并從中選擇一個(gè)最優(yōu)布局圖作為下料方案的一部分[19],本文將板材產(chǎn)出率最大作為選擇布局圖的擇優(yōu)目標(biāo)，其中板材產(chǎn)出率=板材中所布局矩形件總面積/板材面積+λ×板材切割路徑總長度。設(shè)函數(shù)SinglePattern()返回當(dāng)前待排樣板材最優(yōu)布局圖，U為板材最大產(chǎn)出率，最優(yōu)布局圖選擇算法步驟如下：

步驟1令j=1，U=0。

步驟2若bj>0，則初始化x=Lj，y=Wj；否則，轉(zhuǎn)步驟5。

步驟3調(diào)用函數(shù)SinglePattern()生成當(dāng)前板材的布局圖。

步驟5若j

步驟6輸出最優(yōu)布局圖。

其中：步驟1為算法開始時(shí)的初始化。步驟2～步驟3為生成當(dāng)前規(guī)格板材的布局圖。步驟2判斷當(dāng)前板材是否還有剩余庫存，若有，則初始化布局圖生成函數(shù)的板材規(guī)格。步驟3為生成當(dāng)前規(guī)格板材的布局圖。步驟4為計(jì)算當(dāng)前板材的產(chǎn)出率，并判斷是否進(jìn)行最優(yōu)布局圖的更替。步驟5為判斷是否所有規(guī)格的板材均已生成布局圖。步驟6為輸出所有規(guī)格板材中的最優(yōu)布局圖。

3 實(shí)驗(yàn)結(jié)果與分析

算法用C#實(shí)現(xiàn)，實(shí)驗(yàn)環(huán)境為i7-8565U的CPU，參數(shù)Gmax=500，λ=7。實(shí)驗(yàn)分為3部分：①單獨(dú)驗(yàn)證等高塊切割策略的有效性;②采用單算例實(shí)驗(yàn)與相關(guān)文獻(xiàn)及商用軟件優(yōu)化結(jié)果進(jìn)行對(duì)比，以驗(yàn)證本文算法和切割策略的疊加優(yōu)化效果;③在多組隨機(jī)算例上進(jìn)一步驗(yàn)證。

3.1 等高塊與同質(zhì)塊的切割路徑長度對(duì)比

由于板材的切割可與下料方案的生成過程解耦，為充分說明等高塊的切割比同質(zhì)塊的切割更有利于減少路徑長度，使用文獻(xiàn)[17]和文獻(xiàn)[18]的下料方案，與文獻(xiàn)[19]的同質(zhì)塊切割路徑長度進(jìn)行對(duì)比。結(jié)果如表1所示，表中SL和IL分別表示同質(zhì)塊和等高塊的切割路徑長度，ΔL表示兩者的差值，ΔL%表示路徑長度減少的百分比；T_SL和T_IL分別表示下料方案總的切割路徑長度，ΔTL表示兩者的差值，ΔTL%表示減少的百分比。

從表1可看出，在所有布局圖中，采用等高塊切割的路徑均有不同程度的減少，最多達(dá)到11.74%，最少也有2.93%。文獻(xiàn)[17]和文獻(xiàn)[18]的下料方案總切割路徑長度分別減少1 480和3 360，平均減少7.33%。由此說明：等高塊切割策略在減少切割路徑方面具有有效性。

表1 切割路徑的比較

3.2 單一算例實(shí)驗(yàn)對(duì)比分析

為了驗(yàn)證本文算法和切割策略在矩形件切割下料過程中的可行性和有效性，采用文獻(xiàn)[19]的單一算例進(jìn)行實(shí)驗(yàn)，分別運(yùn)用本文算法和商用軟件Cutleader(https://cutleader.com/)對(duì)算例進(jìn)行優(yōu)化處理，得到兩種不同的下料方案。本文算法生成的下料方案如圖4所示，含3種布局圖，每種布局圖使用次數(shù)為1，板材尺寸均為800×600，其中圖4d的帶箭頭實(shí)線是塊內(nèi)的切割線，帶箭頭虛線是塊間的切割線。將本文算法生成的下料方案與Cutleader及文獻(xiàn)[19]生成的下料方案進(jìn)行數(shù)據(jù)對(duì)比，如表2所示。

表2 兩種算法生成的下料方案相關(guān)性能數(shù)據(jù)表

從表2的數(shù)據(jù)可知：①相較于CutLeader，本文算法材料利用率提高了2.79%，切割路徑減少了24.25%；②本文算法與文獻(xiàn)[19]生成的下料方案利用率均為99.58%，切割路徑減少了5 320，減少約15.75%。而由表1可知，若使用同一個(gè)下料方案，僅使用等高塊的切割方法對(duì)路徑進(jìn)行優(yōu)化，減少的路徑長度僅為9.95%。由此可知，本文算法在材料利用率相同的情況下，由于改進(jìn)的布局圖算法策略在考慮切割成本時(shí)會(huì)優(yōu)先生成等高塊，下料方案的切割路徑將會(huì)得到進(jìn)一步的優(yōu)化。因此，本文算法和切割策略在矩形件切割下料過程中具有可行性和有效性。

3.3 多組算例實(shí)驗(yàn)對(duì)比分析

為了進(jìn)一步驗(yàn)證算法和切割策略的可行性和有效性，采用文獻(xiàn)[18]的20個(gè)基準(zhǔn)算例進(jìn)行測(cè)試，并與文獻(xiàn)[19]及商用優(yōu)化軟件——仁霸板材優(yōu)化企業(yè)版(http://www.renbakeji.com/)的結(jié)果進(jìn)行比較。實(shí)驗(yàn)結(jié)果如圖5所示，其中SU_R、SU_C和SU_S分別為仁霸、文獻(xiàn)[19]和本文算法的下料方案利用率，CL_R、CL_C和CL_S分別為仁霸、文獻(xiàn)[19]和本文下料方案的切割路徑長度。

由圖5可知：本文算法得到的下料方案利用率比仁霸和文獻(xiàn)[19]總體上略有提高，分別提高了1.32%和0.16%；本文算法平均切割路徑長度比仁霸和文獻(xiàn)[19]分別減少了18 612和2 403，減少比例分別達(dá)到19.56%和3.04%。從圖5三種算法實(shí)驗(yàn)數(shù)據(jù)對(duì)比折線圖可以看出，本文算法和切割策略在提高材料利用、降低切割路徑方面具有可行性和有效性。

4 結(jié)束語

本文針對(duì)多規(guī)格矩形件下料問題，以生產(chǎn)成本(材料成本與切割成本之和)最小為下料方案的優(yōu)化目標(biāo)。在SVC算法框架基礎(chǔ)上，提出在生成單板材布局圖時(shí)，以布局圖綜合價(jià)值(所含矩形件總價(jià)值與切割成本之差)最大作為優(yōu)化目標(biāo)，通過求解有界背包問題，前瞻性地考慮子板與當(dāng)前考察條帶拼合后的綜合價(jià)值最大化。在路徑優(yōu)化方面，提出等高塊概念并設(shè)計(jì)等高塊共邊切割策略。通過多組基準(zhǔn)算例實(shí)驗(yàn)數(shù)據(jù)對(duì)比分析證明了本文所提算法和切割策略的可行性和有效性。3.1節(jié)的實(shí)驗(yàn)結(jié)果說明等高塊切割規(guī)則并不受限于某種算法，而是可以作為一種策略為不同算法所調(diào)用，在此研究基礎(chǔ)上，筆者將把本文所提出的等高塊共邊切割策略引入十進(jìn)制灰狼算法以開展后續(xù)的研究工作。