陳 燕，魯淑飛，胡小春，孫 宇，黃曉冬

(1.廣西大學(xué) 計算機與電子信息學(xué)院廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點實驗室，廣西 南寧 530004；2.廣西財經(jīng)學(xué)院 信息與統(tǒng)計學(xué)院，廣西 南寧 530003;3.廣西大學(xué) 機械工程學(xué)院，廣西 南寧 530004)

0 引言

近年隨著現(xiàn)代通信、計算、網(wǎng)絡(luò)和控制技術(shù)的發(fā)展，智能制造在制造企業(yè)生產(chǎn)中的重要作用日益突顯[1]。與此同時，制造業(yè)的勞動力成本也在不斷攀升，生產(chǎn)企業(yè)為了降低生產(chǎn)成本、提高生產(chǎn)效率和精細(xì)化，勢必會大量使用制造機器人、機械手。信息化與自動化結(jié)合的物聯(lián)制造和制造清單自動付諸于制造執(zhí)行等各種需求更加迫切。因此，適合智能制造的切割工藝如減少火焰切割、激光切割等是制造業(yè)未來的應(yīng)用趨勢，而制定面向可加工性的下料方案是實現(xiàn)智能制造的前提和基礎(chǔ)[2]。

下料問題(Cutting Stock Problem, CSP)是國際上一個重要研究領(lǐng)域，相關(guān)的理論研究和實踐應(yīng)用十分豐富[3-4]。然而，下料問題的涉及面非常廣，而且是具有NP難度的組合優(yōu)化問題[5]，因此面向不同應(yīng)用的下料問題需要設(shè)計具體的求解方法[6]。下料優(yōu)化排樣方法可提高原材料的利用率，路徑優(yōu)化可縮短切割加工的路徑，這對矩形件的生產(chǎn)加工具有重大的實用價值[7]。目前，很多研究已經(jīng)從單純的提高材料利用率轉(zhuǎn)向多目標(biāo)優(yōu)化、切割操作簡化和面向可加工性發(fā)展，使下料方案更符合實際生產(chǎn)需要。文獻(xiàn)[8]的研究目標(biāo)是盡量減少材料成本和設(shè)置的數(shù)量，使用整數(shù)規(guī)劃方法進(jìn)行求解；文獻(xiàn)[9-10]主要從減少排樣方式數(shù)量的方面研究，考慮減少設(shè)備重置費用；文獻(xiàn)[11]從減少切割刀數(shù)考慮來減少切割成本；文獻(xiàn)[12]主要研究減少下料過程中需要存放毛坯的堆數(shù)，以減少生產(chǎn)需要的臨時存儲空間；文獻(xiàn)[13]闡述下料問題應(yīng)綜合考慮下料工藝、切割成本、生產(chǎn)效率等因素，在保證較高利用率的同時具有良好的可加工性;文獻(xiàn)[14]提出一種支持一刀切工藝約束的多規(guī)格板材組合的構(gòu)造算法，依據(jù)工件的總面積形成多種可行的板材組合，采用組化策略和啟發(fā)式的排樣規(guī)則并用啟發(fā)式方法求解;文獻(xiàn)[12]利用同質(zhì)條帶組合構(gòu)造成塊T型塊，在滿足一刀切的工藝約束前提下提高材料利用率;文獻(xiàn)[14-15]分別利用同質(zhì)條帶的共邊切割，提出面向可加工的矩形件下料方法，綜合考慮材料利用率和切割成本的優(yōu)化，其中文獻(xiàn)[14]使用主從目標(biāo)的優(yōu)化模型，首先以材料最大利用率作優(yōu)化目標(biāo)，利用連續(xù)啟發(fā)式方法尋求最優(yōu)布局圖，再用條帶共邊切割的路徑優(yōu)化方法設(shè)計切割路徑；文獻(xiàn)[15]將綜合考慮材料成本和切割成本，以最大價值尋求最優(yōu)布局圖，使用順序價值校正(Sequential Value Correction, SVC)框架多次迭代獲得多個可行的下料方案，并從中選擇綜合成本最小的方案。

已有的考慮可加工性的矩形件下料問題研究中，在切割路徑優(yōu)化策略上只考慮毛坯或條帶的共邊切割，忽略了相同條帶所組成的同質(zhì)塊的共邊特性，不能充分挖掘塊共邊切割的潛能。而且大部分研究都是先考慮材料的最大利用，其他可加工性等約束只作為輔助優(yōu)化目標(biāo)，不利于綜合成本最小的整體優(yōu)化。因此，本文首先提出考慮材料成本和切割成本綜合最小的多目標(biāo)規(guī)劃問題(Multi-Objective Programming, MOP)模型。在此基礎(chǔ)上，提出同質(zhì)塊的共邊切割策略，根據(jù)同質(zhì)條帶有無余料、條帶所含毛坯數(shù)的奇偶性設(shè)計板材的切割路徑，以減少切割成本。設(shè)計生成布局圖的前瞻法時，不僅要考慮當(dāng)前條帶利用率，還要考慮布局當(dāng)前條帶后板材的整體利用率，以減少材料成本。切割成本與材料成本的減少相互并不沖突，但如果生成布局圖的啟發(fā)式方法不當(dāng)，很難在有限時間內(nèi)尋找到近似最優(yōu)的解。本文通過前瞻法判斷每塊拼入的毛坯對利用率的影響、拼入的條帶對切割成本的影響，每次選取放置的毛坯都優(yōu)先考慮組成同質(zhì)塊。實驗數(shù)據(jù)證明，所提方法實現(xiàn)了綜合成本最小的Pareto改進(jìn)，在保證材料利用率較高的基礎(chǔ)上減少了切割的路徑。

1 考慮可加工性的矩形件下料方案的優(yōu)化方法

1.1 下料方案的問題描述及數(shù)學(xué)模型

多規(guī)格板材的矩形件下料問題可描述為：在n種長為Lj、寬為Wj、供應(yīng)量為Dj(其中j=1,…,n)的板材上切割出m種長為li、寬為wi、需求量為di(其中i=1,…,m)的矩形件。假設(shè)有K種排樣方式，則下料方案的整數(shù)規(guī)劃模型為：

(1)

s.t.

(2)

(3)

(4)

1.2 毛坯和條帶的布局

將矩形件(或矩形毛坯)布局在規(guī)則板材上，毛坯的布局不能超過板材的邊界，毛坯之間不允許重疊。毛坯可旋轉(zhuǎn)90度放置，即可水平放置和垂直放置兩種方式。本文采用同質(zhì)條帶的布局方式，即條帶內(nèi)毛坯相同、放置的方向亦相同?？捎肵和Y標(biāo)記毛坯和條帶的放置方向，用T=(t1t2)表示條帶，其中：t1表示條帶方向，t1={X,Y};t2表示毛坯的方向,t2={X,Y}。因此，有T={XX,XY,YX,YY}四種條帶類型，具體信息如表1所示。其中一種毛坯的同質(zhì)條帶在長、寬分別為L和W的板材上的4種布局方式如圖1所示，陰影部分為余料。

表1 條帶類型信息表

1.3 條帶優(yōu)選方法

由于本文使用的是有約束的排樣方式，每次放置條帶時必須考慮當(dāng)前的剩余毛坯需求。m種毛坯的基本信息為可用元組(i,li,wi,ri,vi)表示，其中vi和ri分別為第i種毛坯的價值和剩余需求。利用條帶的產(chǎn)出率對條帶進(jìn)行優(yōu)選，條帶的產(chǎn)生率=條帶所含有效毛坯總價值/條帶面積。所謂有效的毛坯是指條帶布局的毛坯數(shù)量不能超過當(dāng)前的剩余毛坯的需求數(shù)量。

分別用XXi、XYi、YXi和YYi表示第i種毛坯對應(yīng)的4種條帶類型，用O(XXi)、O(XYi)、O(YXi)和O(YYi)分別表示第i種毛坯對應(yīng)4種條帶的產(chǎn)出率，其值分別為：

O(XXi)=(vi×min(ri,?L/li?)/(L×wi)，

O(XYi)=vi×min(ri,?L/wi?)/(L×li)),

O(YXi)=(vi×min(ri,?W/wi?)/(W×li)，

O(YYi)=vi×min(ri,?W/li?)/(W×wi))。

其中：L和W分別表示待排樣板材的長和寬;?L/li?、?L/wi?、?W/wi?和?W/li?分別表示上述4處條帶所含的毛坯個數(shù)。當(dāng)遍歷共m種毛坯時，最多的可行條帶數(shù)為4m根。

1.4 布局圖生成方法

最優(yōu)布局圖是指根據(jù)當(dāng)前需求的毛坯，尋求在給定板材上合理的放置方式，使布局圖的綜合價值最大。假設(shè)板材的長寬分別為L和W，用F(L,W)表示該板材上的綜合價值，則最優(yōu)布局圖的模型可表示為：

(5)

式中：qi為第i(i=1,…,m)種毛坯布局圖放置的個數(shù);ri為第i種毛坯的剩余需求量;ci為第i種毛坯的價值。該問題是有約束的二維背包問題，具有NP難度，可用具有分支遍歷的前瞻法求解。板材上放置一根條帶后，整板面積會劃分為放置條帶面積與剩余板材面積兩部分；然后將剩余板材面積作為母板再次進(jìn)行布局，直至板材不能布局任何下一根條帶或已經(jīng)滿足所有毛坯需求。布局圖生成算法思想如圖2所示，其中虛線箭頭表示遞歸算法的回推過程。

1.5 下料方案求解方法

SVC框架技術(shù)相對成熟，已在多種下料問題中獲得成功的應(yīng)用[9，12]。SVC是基于價值校正的順序啟發(fā)式算法，經(jīng)過多次毛坯價值校正和生成多個方案后，可從中選擇綜合成本最小的下料方案。生成下料方案的算法如下：

輸入：毛坯的初始需求(ri,li,wi)和板材供應(yīng)(Dj,Lj,Wj)，其中i=1,…,m，j=1,…,n。

步驟1令G=1，Gmax=100作為最高迭代次數(shù)，令毛坯初始價值為毛坯的面積vi=li×wi，令最佳下料方案的總成本Zbest=+∞。

步驟2令剩余毛坯需求量等于初始毛坯需求量ri=di。

步驟3令j=1，最佳布局圖的利用率為0，使用步驟3.1～步驟3.5生成最優(yōu)布局圖。

步驟3.1：令當(dāng)前剩余毛坯需求bi=ri。若Dj≤0，則轉(zhuǎn)步驟3.5；否則針對每種剩余毛坯考察在當(dāng)前板材上的4種可能的布局。板材布局條帶的總產(chǎn)出率U(L,W)等于確定放置的第一根條帶的產(chǎn)出率與剩余子板材(x,y)所布局條帶的總產(chǎn)出率O。令已確定條帶所含毛坯個數(shù)為ni，更新當(dāng)前剩余的毛坯需求，令bi=bi-ni。

步驟3.2：根據(jù)當(dāng)前剩余的毛坯需求和子板材的尺寸(x,y)，考察每種剩余毛坯在子板材上的4種布局，U(x,y)等于放置的第二根條帶產(chǎn)出率與剩下的子板材的條帶總產(chǎn)出率。更新當(dāng)前剩余的毛坯需求，令bi=bi-ni。

步驟3.3：若剩下的子板材還可以再放置毛坯，且還有剩余的毛坯需求，即bi>0，則轉(zhuǎn)步驟3.2；否則剩余子板材不能再放置毛坯或已滿足所有毛坯需求，轉(zhuǎn)步驟3.4。

步驟3.5：若j

步驟4根據(jù)f=min{ri/zi|zi>0∧i∈{1,…,m}}確定本次所得布局圖使用次數(shù)，將當(dāng)前布局圖加入當(dāng)前的下料方案。更新剩余的毛坯需求數(shù)，ri=ri-zi，其中zi為當(dāng)前布局圖所含第i種毛坯的總數(shù)，更新板材的可用數(shù)量，令Dj=Dj-f。

步驟5若剩余的毛坯需求ri>0，調(diào)整毛坯的價值。

步驟6若還有剩余需求的毛坯，則轉(zhuǎn)步驟3；否則根據(jù)式(1)計算當(dāng)前下料方案的Z，并記錄當(dāng)前最好的下料方案。

步驟7令G=G+1，如果G≤Gmax，轉(zhuǎn)步驟2。

輸出：最好的下料方案。

因為每次迭代結(jié)束就得到一種下料方案，所以通過毛坯的價值調(diào)整，可生成多樣化的布局圖和多樣性的下料方案。當(dāng)整個算法結(jié)束時，已經(jīng)考察了Gmax個下料方案，G為當(dāng)前迭代次數(shù)。

2 路徑優(yōu)化計算方法

2.1 塊切割路徑優(yōu)化方法

板材切割即按布局圖切割出板材上所布局的矩形件，采用有效可行的切割路徑優(yōu)化設(shè)計對縮短零件生產(chǎn)周期、提高生產(chǎn)效益具有重要意義。針對板材切割路徑的優(yōu)化，文獻(xiàn)[14]利用條帶中毛坯的共邊布局設(shè)計條帶共邊切割策略，即條帶內(nèi)采用“之”字型切割分離毛坯，條帶間采用“直線型”分離，以條帶為單位進(jìn)行板材的切割。在此基礎(chǔ)上，本文提出同質(zhì)塊概念以及基于同質(zhì)塊的共邊切割方法，不僅考慮毛坯間的共邊布局，還考慮條帶間的共邊布局，可進(jìn)一步縮短空刀行程，降低切割成本，提高加工效率。下面將介紹同質(zhì)塊概念及其共邊切割規(guī)則。

同質(zhì)塊是由長度和方向均相同、相鄰且有共邊的同質(zhì)條帶組成的矩形區(qū)域。如圖3所示的布局圖共有7塊同質(zhì)塊，圖形邊上標(biāo)弧線的數(shù)字為塊數(shù)，條帶內(nèi)的數(shù)字表示該條帶所布局的毛坯號數(shù)。該圖共包含4種毛坯，可組成4種同質(zhì)條帶。例如：3號同質(zhì)塊由3根2號毛坯布局的同質(zhì)XX型條帶組成。值得注意的是，圖中塊1與塊7均為4號毛坯組成的同種類型的同質(zhì)條帶，但在板材上的布局條帶不同，而且區(qū)域不相鄰、長度不相同，因此是兩個不同的塊。同理，塊3與塊5也是不同的塊。由以上描述可知，塊包含了條帶，當(dāng)塊內(nèi)只有一根條帶組成時，塊就簡化成了條帶，即同質(zhì)條帶是同質(zhì)塊的特例。

由于板材上條帶布局后存在有余料生成和無余料生成兩種情況，而條帶的布局存在垂直和水平兩個方向，同時條帶中所含的矩形件個數(shù)也有奇偶之分，因此排樣方式中所布局的同質(zhì)條帶塊根據(jù)其是否有余料生成、所含條帶布局方向以及條帶所含矩形件個數(shù)的奇偶性可以分為8種類型的同質(zhì)條帶塊。而根據(jù)同質(zhì)塊類型的不同，其切割規(guī)則也不盡相同，具體分類以及切割路徑規(guī)則如圖4所示。

切割路徑的走向與塊切割起點的選擇有關(guān)?，F(xiàn)實情況中，無論是火焰切割還是激光切割，通常默認(rèn)從板材的左上角開始；后續(xù)塊的起點根據(jù)與前一塊的切割結(jié)束點之間的最短空程來選擇，每個塊的4個頂點均可作為切割的起點。以左上角作切割起始點為例，如圖5所示為8種類型塊的切割路徑走向示意圖。

2.2 整板切割路徑優(yōu)化方法

在同質(zhì)塊切割路徑優(yōu)化設(shè)計完成的基礎(chǔ)上，合理安排布局圖中同質(zhì)塊的切割次序，能夠有效地減少板材切割時同質(zhì)塊之間的空刀行程，從而降低切割板材的成本、提高切割板材的效率。由于同質(zhì)塊具有4個可切入點，在一個同質(zhì)塊切割完畢后，選擇具有最短空刀行程距離切割點的同質(zhì)塊進(jìn)行切割，依次循環(huán)直至完成整個板材的切割。如圖6所示為一個布局圖的整塊板材切割的路徑示意圖，圖6a為板材的布局圖，圖6b為切割過程中走刀的路線圖。圖中實線箭頭為同質(zhì)塊內(nèi)部毛坯的切割路徑與方向，虛線箭頭表示同質(zhì)塊間的切割路徑與方向。實際操作過程中只要按照上述路徑走刀，即可完全把毛坯分離出來，完成下料過程。

3 實驗結(jié)果與分析

實驗算法用C#編程實現(xiàn)，研究環(huán)境為Intel Core i5-4590 CPU，3.3 GHz主頻，4 GB內(nèi)存。算法設(shè)置參數(shù)Gmax=100，λ=7。先在單一基準(zhǔn)算例上將文獻(xiàn)[14]的方法(簡寫為WU)和文獻(xiàn)[15]的方法(簡寫為LU)應(yīng)用塊切割策略進(jìn)行路徑優(yōu)化計算對比分析；然后在多組隨機基準(zhǔn)算例上用本文方法(簡寫為SV)進(jìn)行實驗測試，主要從材料利用率和切割路徑長度兩方面與LU方法進(jìn)行對比分析。

3.1 單一算例實驗對比分析

下面與文獻(xiàn)[14-15]采用相同的基準(zhǔn)算例進(jìn)行測試，分別采用兩種不同的切割策略，分析對切割路徑長度的影響。先用塊切割策略對WU與LU下料方案的切割路徑進(jìn)行優(yōu)化，結(jié)果如表2所示。表中：PID表示4種方法的代號;WT和WS表示W(wǎng)U方法分別用條帶切割和塊切割;LT和LS表示

LU方法分別用條帶切割和塊切割；P和PL表示每種算法生成的最優(yōu)布局圖序號及其切割路徑長度；SL表示下料方案總的切割路徑長度，ΔL和Δ/%表示每種方法使用塊切割與條帶切割的路徑長度的實際差值和優(yōu)化的百分比。表2中WT和LT的數(shù)據(jù)分別從文獻(xiàn)[14]和文獻(xiàn)[15]復(fù)制而來，WS和LS的數(shù)據(jù)是使用本文方法求解，并使用塊切割策略對切割路徑進(jìn)行優(yōu)化的結(jié)果。

由表2可看出，WS比WT減少了5 200的切割路徑，優(yōu)化的百分比是14.2%(=(5 200/36 660)×100%)；LS比LT減少了2 400的切割路徑，優(yōu)化的百分比是6.63%(=(2400/36180)×100%)。從這兩個算例的結(jié)果來看，使用塊切割策略的路徑優(yōu)化減少平均約為10.41%(=(14.18%+6.63%)/2)，已經(jīng)超過了10%，優(yōu)化效果非常明顯。由此可知：塊切割比條帶切割的優(yōu)化較為明顯，可在保持材料利用率不變的基礎(chǔ)上進(jìn)一步減少切割成本。

表2 切割路徑的比較

3.2 多組算例實驗對比分析

用文獻(xiàn)[15]的20個基準(zhǔn)算例進(jìn)行測試，每個算例都有20種毛坯需求，每種毛坯的長和寬取值范圍是[50，450]、需求量取值范圍是[1,10]。上述取值均服從隨機的正態(tài)分布，且均為整數(shù)。供使用的板材有5種，尺寸分別為1 400×700、1 700×850、2 000×1 000、2 800×1 400和4 000×2 000。

分別用本文方法SV與文獻(xiàn)[15]的LU方法求解，其下料方案的利用率和切割路徑長度結(jié)果如表3所示。表中：U_LU和U_SV分別為LU和SV算法求解的利用率，L_LU和L_SV分別為LU和SV算法求解的切割路徑長度，ΔU=U_SV-U_LU，ΔU=U_SV-U_LU；Avg.表示各項的平均值。由表3可知：針對每一個算例，與LU相比SV求解的切割路徑都更短，其平均切割長度降低了5.15%，從而充分說明本文應(yīng)用的塊切割策略比文獻(xiàn)[15]應(yīng)用的條帶切割更優(yōu)。SV與LU相比，利用率并沒有降低，其中6組還略有提高，從平均數(shù)看提高了約0.16%。通過多組隨機算例的測試可充分說明，本文提出的塊切割是用條帶切割，而后者是用塊切割，因此只影響了切割成本。

表3 多組算例的測試結(jié)果

續(xù)表3

3.3 多目標(biāo)優(yōu)化的Pareto改進(jìn)分析

通過實驗測試結(jié)果證明，本文所提方法可實現(xiàn)Pareto改進(jìn)(Pareto Improvement)，即在保證材料利用率、不增加廢料的前提下，使切割路徑長度大幅度降低。分別從單一算例和多組算例的路徑長度和利用率角度分析Pareto的改進(jìn)，如圖7所示。從圖7a可看出，在單一算例測試中，4種算法均獲得最優(yōu)的材料利用率，與WU與LU相比，本文提出的方法對減少切割路徑長度有明顯的效果；由圖7b可以看出，在多組隨機算例測試中，SV的Pareto改進(jìn)程度更大。

4 結(jié)束語

本文研究了多規(guī)格、大批量的矩形件切割路徑優(yōu)化問題，創(chuàng)新之處在于提出了以材料成本和切割成本綜合最小的多目標(biāo)規(guī)劃模型；生成單張板材的布局圖時，設(shè)計了同質(zhì)塊的共邊切割策略，允許毛坯可轉(zhuǎn)向布局，考察了4種類型的條帶組合，利用條帶的產(chǎn)出率對考察的條帶進(jìn)行優(yōu)選，使條帶的利用率最大化；在生成整板布局時前瞻性地考慮了子板與當(dāng)前考察條帶拼合后的綜合價值最大化，設(shè)計并實現(xiàn)了綜合成本最小化的Pareto改進(jìn)的路徑和方法。通過多組基準(zhǔn)算例測試，證實了所提方法的有效性和實用性，該方法同時實現(xiàn)了多目標(biāo)優(yōu)化的Pareto改進(jìn)。未來將在此研究基礎(chǔ)上，針對二維異形件的切割加工路徑優(yōu)化設(shè)計方法開展后續(xù)的研究工作。