面向可加工性的矩形件優化下料算法

魯淑飛，陳 燕，崔耀東

廣西大學 計算機與電子信息學院，南寧 530004

1 引言

二維矩形件下料廣泛存在于服裝、皮革、木材、金屬制品、機械設備等生產制造行業，作為控制企業生產成本的重點環節，采用合理的優化下料技術具有重要的意義[1]。如在鋼材、機械、汽車、造船等重工業領域，由于鋼板一般通過激光、火焰、等離子切割以及沖裁等方式切割成生產零件，切割成本較高，因此采用在提高材料利用率的同時，降低切割成本，縮短生產周期的優化下料技術，對于企業長遠發展具有重要意義。

目前針對矩形件優化下料問題，國內外專家學者大多從改進算法提高材料利用率角度進行研究，文獻[2]應用四塊排樣算法生成單個排樣方式，與基于價值修正的順序啟發式算法相結合，選擇使用板材張數最少的下料方案作為最終解；文獻[3]應用生成同質條帶四塊排樣方式的背包算法，與線性規劃算法相結合，以板材張數最少為目標選擇下料方案；文獻[4]將列生成法與有約束排樣方式算法相結合，求解同質條帶四塊排樣的矩形件下料問題以提高材料利用率；文獻[5]提出一種可以確定板材采購尺寸的二維優化下料算法，即在已知矩形件需求的情況下，在供應商規定的板材尺寸范圍內確定最佳采購尺寸，使板材利用率達到最優，降低材料成本。然而矩形件優化下料問題是具有最高計算復雜性的NP完全問題，實際下料問題涉及環節多，生成下料方案時，不僅要考慮材料利用率，同時還要考慮下料工藝、切割成本、生產效率等一系列問題，使下料方案在具有高材料利用率的同時具有良好的可加工性[6]、低的切割成本和高的生產效率。針對實際下料過程中的一些具體問題，文獻[7]提出一種支持一刀切工藝約束的放寬式搜索算法，在得到高材料利用率下料方案的同時滿足特定下料工藝；文獻[8]將基于分組降維規則與遺傳算法相結合，求解人造板矩形件優化下料問題，解決一張板材上布局矩形件種類過多導致開料鋸在切割過程中鋸路繁瑣開料速度慢的問題；文獻[9]考慮下料方案的可加工性，將根據板材單方向余料長最小化優選條帶方法與基于條帶的連續啟發式算法相結合求解矩形件優化下料問題，利用同質條帶的共邊排樣設計自動切割工藝的下料切割路徑，以縮短總的切割路徑，提高生產效率，降低下料切割成本。但是其利用板材單方向余料長最小化優選布局條帶的方法不能保證排樣方式全局最優，另外基于布局條帶的連續啟發式算法具有貪婪性，即生成下料方案中靠前排樣方式時，剩余矩形件多，容易得到高材料利用率的排樣方式；在生成靠后排樣方式時，剩余矩形件較少，得到排樣方式的材料利用率較低。

基于以上研究基礎，針對鋼板矩形件自動化切割下料問題，本文綜合考慮材料成本、下料工藝、切割成本以及生產效率，將同質條帶多級規范布局方式[10-11]生成算法與基于價值修正的順序啟發式算法[12-13（]Sequential Value Correction，SVC）相結合，以材料成本和切割成本為優化目標，提出一種面向可加工性的矩形件優化下料算法。最后通過多組算例進行實驗對比，證明應用本文算法能夠有效地提高材料利用率和生產效率，降低切割成本。

2 數學模型及相關概念

2.1 問題描述及數學模型

本文討論的是多規格、大批量的矩形件優化下料問題，即在n種長為Lj，寬為Wj，供應量為Dj(j=1,2,…,n)的板材上按照生產工藝要求切割出m種長為li，寬為wi，需求量為di(i=1,2,…,m)的矩形件。

假設下料方案有K種排樣方式，對于第k(k=1,2,…,K)個排樣方式，Sk為消耗的材料成本，λPk為切割成本（其中λ為控制參數，Pk為切割路徑長度，切割成本與切割路徑長度成正比，λ∈[1,12]，默認值為7），aki為含第i種矩形件的數量，xk為使用次數，所使用的板材種類為β(k)，其中β(k)∈[1,2,…,n]。要求滿足矩形件需求量，并使其生產成本（材料成本與切割成本之和）達到最小。則該問題的整數規劃模型為：

其中，式（1）為面向可加工性的矩形件優化下料問題的目標函數，即最小化的生產成本，其中板材成本為板材面積，切割成本為下料過程中能源、加工工時、人力資源等消耗通過控制參數以切割路徑總長度為單位統一折算而來；式（2）為約束條件，表示按此下料方案產出的矩形件數量應該等于矩形件的需求；式（3）為約束條件，表示下料方案使用每種板材的總量不能超過其供應量；式（4）為變量的取值范圍，Z+0表示非負整數集合。

2.2 條帶

條帶根據是否含有多種不同尺寸的矩形件，可分為普通條帶和同質條帶。如圖1所示，由不同寬度的矩形件組成的條帶稱為普通條帶，由相同種類相同方向的矩形件組成的條帶稱為同質條帶。綜合考慮下料方案的可加工性，以及自動化切割的可操作性，本文采用同質條帶。

圖1 條帶

分別用X和Y標記水平方向和豎直方向，則根據條帶方向與矩形件長邊的方向，可將條帶分為XX、XY、YX和YY四種類型。其中，XX型條帶表示條帶方向水平，矩形件長邊水平；XY 型條帶表示條帶方向水平，矩形件長邊豎直；YX型條帶表示條帶方向豎直，矩形件長邊水平；YY 型條帶表示條帶方向豎直，矩形件長邊豎直。四種條帶在板材上的布局如圖2所示，其中陰影部分為條帶在板材上排樣后所產生的余料。

圖2 四種條帶布局示意圖

表1分別列出了各類型條帶的相關標記參數，則各類型條帶的相應價值如下：

表1 條帶相關參數信息表

其中，ci為第i種矩形件的價值，i=1,2,…,m。

2.3 板材切割

板材切割即按排樣方式切割出板材上所布局的矩形件。本文板材切割方法參考文獻[9]，條帶內的矩形件分離采用“之”字型切割，條帶間的分離采用直線型切割。條帶內的矩形件分離具體切割方法：當條帶為XX、XY型條帶時，若條帶內含有矩形件的數量為奇數，則自條帶左上角水平向右開始進行“之”字型切割分離矩形件；若條帶內含有矩形件的數量為偶數，則自條帶左上角豎直向下進行“之”字型切割分離矩形件。當條帶為YX、YY 型條帶時，若條帶內含有矩形件的數量為奇數，則自條帶左上角豎直向下進行“之”字型切割分離矩形件；若條帶內含有矩形件的數量為偶數，則自條帶左上角水平向右進行“之”字型切割分離矩形件。條帶間分離具體切割方法：當條帶為XX、XY 型條帶時，自左向右直線分離條帶；當條帶為YX、YY 型條帶時，自下而上直線分離條帶。

假設條帶內含有第i種矩形件的數量為a，則條帶切割路徑長度C(a)的計算方法如下：

當a為奇數時：

當a為偶數時：

一張板材的切割路徑長度為其上所布局條帶切割路徑長度之和；下料方案的切割路徑長度為其所用板材切割路徑長度之和。

3 算法設計與實現

SVC框架在求解下料問題時得到廣泛應用[12-13]。本文將基于價值修正的順序啟發式算法與排樣方式生成算法相結合，形成下料方案的生成算法。利用基于價值校正的順序啟發式算法多代、順序、價值校正的特點，經多次迭代后，從多個下料方案中優選生產成本最小者作為最終下料方案。

3.1 下料方案生成算法

按照式（1）計算下料方案總成本，Gmax為最高迭代次數，G為當前迭代次數，ri為第i種矩形件的剩余需求量(i=1,2,…,m) ，bj為第j種板材的剩余庫存量(j=1,2,…,n)，qi為排樣方式所含第i種矩形件的數量(i=1,2,…,m)，f為排樣方式的使用次數。下料方案生成算法步驟如下，其中GetPattern()函數和CorrectValue()函數將分別在3.2和3.3節中介紹。

步驟1令G=1，初始化毛坯價值ci=li×wi，i=1,2,…,m；令最佳下料方案的總成本為正無窮大。

步驟2如果G ＞Gmax，轉步驟9，否則，令矩形件的剩余需求量等于初始需求量，即ri=di，令板材的剩余庫存量等于初始供應量，即bj=Dj，其中i=1,2,…,m，j=1,2,…,n。

步驟3調用GetPattern()函數生成當前排樣方式。

步驟4根據當前使用第j種板材(j∈[1,2,…,n])的庫存量和需求量確定當前排樣方式使用次數f，，更新矩形件剩余需求量ri=ri-fqi，更新板材庫存量bj=bj-f，并將此排樣方式加入當前下料方案中。

步驟5調用CorrectValue()函數修正矩形件的價值。

步驟6對于所有的矩形件，只要存在一個ri ＞0(i=1,2,…,m)則轉步驟3，否則轉步驟7。

步驟7計算當前下料方案的生產成本，若當前下料方案的生產成本低于目前最佳下料方案的生產成本，則更新最佳下料方案。

步驟8G=G+1。轉步驟2。

步驟9輸出最佳下料方案。

3.2 GetPattern()函數

構建前瞻法，采用同質條帶多級規范布局方式，通過求解如下有界二維背包問題（6）確定當前板材的排樣方式：

前瞻法即每偽布局一根條帶，都要考慮剩余子板的所有布局可能性，并計算出其價值，最后以式（6）確定最終排樣方式，示意圖如圖3所示，具體方法描述如下。

設lmin，wmin分別為矩形件尺寸中的最小長度和最小寬度，在尺寸為x×y的板材上生成同質條帶多級規范布局方式，板材最大價值為F(x,y)，則遞推公式如下：

圖3 前瞻法示意圖

當x ＜lmin或y ＜wmin，同時x ＜wmin或y ＜lmin，F(x,y)=0。

否則，

式（7）的時間復雜度為O(mLW)，而且其具有全容量特性：一旦計算出F(x,y) ，那么對于所有的x×y(x∈[1,L]?y∈[1,W])，F(x,y) 的值均已計算出來。即每一步根據F(x,y)的取值情況，可以確定板材x×y的排樣方式。

設函數getPattern(x,y)返回當前排樣板材最大價值，函數算法步驟如下：

步驟1令F(x,y)=0，i=1。

步驟2令VXX=0，VXY=0，VYX=0，VYY=0。若當前待排樣板材x×y不能布局任何一種矩形件條帶，則轉步驟 5；否則：如果x≥li，而且y≥wi時，則令VXX=uXX(i,x)+getPattern(x,y-wi)，VYX=uYX(i,y)+getPattern(x-li,y)；若x≥wi且y≥li，令VXY=uXY(i,x)+getPattern(x,y-li)，VYY=uYY(i,y)+getPattern(x-wi,y)。

步驟3令V=max{VXX,VXY,VYX,VYY} 。

步驟4如果F(x,y)＜V，令F(x,y)=V。

步驟5令i=i+1。如果i≤m，則轉步驟2。

步驟6返回F(x,y)。

在實際生成排樣方式的過程中，初始化x=Lj，y=Wj(j=1,2,…,n)，依次調用函數getPattern(x,y)，得到每種可用板材最大價值的排樣方式。根據2.3 節計算每種板材的切割路徑長度，按下式計算板材的產出率：

以最高產出率確定最終使用板材種類及其排樣方式。

3.3 CorrectValue()函數

下料方案生成算法中，每生成一個排樣方式后，都對矩形件價值進行修正[12]，調整矩形件的優先級，解決局部最優問題，實現下料方案多樣化。矩形件價值修正公式[14]如下：

其中，g1+g2=1；g2=εqi(di+ri)；參數ε∈[0.6,0.9]，默認值為0.75；ρ為略大于1的控制參數，默認值為1.02；U為當前排樣方式利用率，。

4 實驗結果與分析

本實驗采用C#編程，實驗用計算機配置為Intel Core i5-4590 CPU，3.3 GHz 主頻，4 GB 內存。其中參數Gmax=500。

4.1 單一算例實驗對比

采用文獻[9]中的例題，僅有1組矩形件和1組板材尺寸（分別為500×400、800×600、1 000×800）。本文算法運行結果如圖4所示，共有3個排樣方式，每個排樣方式使用次數為1、板材尺寸均為800×600，其中圖4（d）中帶箭頭的紅色實線表示分離矩形件的切割線，帶箭頭的藍色虛線表示分離條帶的切割線。本文算法與文獻[9]算法材料利用率均為99.58%，切割總路徑分別為36 180和36 660，前者小于后者，與后者相比前者切割總路徑降低1.31%。由此可知，針對本算例，與文獻[9]相比，本文算法在材料利用率相同的情況下，下料方案具有更短的切割路徑和更高的生產效率。

圖4 下料方案及排樣方式切割路徑圖

4.2 多組算例實驗對比

由于單一算例實驗結果具有偶然性，為了進一步驗證本文算法的有效性與可行性，從文獻[15]中選取20道基準實例與文獻[9]算法進行對比，其中每道題都有20組矩形件，5 種可供使用板材（尺寸分別為1 400×700、1 700×850、2 000×1 000、2 800×1 400 和4 000×2 000）。表2列出了本文算法與文獻[9]算法的測試結果，其中U和CL分別代表本文算法的材料利用率和切割路徑總長度，U1和CL1則分別代表文獻[9]算法的材料利用率和切割路徑總長度，ΔU和ΔCL分別表示材料利用率和切割路徑總長度的差值，其中ΔU=U-U1，ΔCL=CL-CL1。從表中可以看出，兩種算法的平均材料利用率分別為95.66%和88.62%，前者較后者提高7.04%；平均切割路徑分別為83 218.8 和87 741.6，前者較后者減少4 552.8，與后者相比前者切割總路徑降低5.19%。由數據對比可知，本文算法能夠有效地降低生產成本，縮短下料時間，提高下料效率。

表2 兩種算法的實驗結果及對比情況

5 結束語

本文以材料利用率和切割成本為優化目標，提出一種面向可加工性的矩形件優化下料算法，其中算法以低割成本和高材料利用率為目標，建立了以生產成本（材料成本與切割成本之和）最小為目標函數的數學模型，模型中將下料過程中能源、加工工時、人力資源等消耗通過控制參數統一折算為切割成本，以生產成本最小為目標函數，簡化了優化下料過程中相關環節的處理方法，對優化下料問題的研究具有重要意義。另外，最后通過實驗對比證實本文提出的優化下料算法符合實際生產的需求，能在維持高材料利用率的同時，使下料方案具有較低的切割成本和良好的可加工性，提高下料效率，對于企業的長遠發展具有重要意義。