基于排樣矩形的直角邊零件下料算法①

郭百海,隋 毅

(青島大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)學(xué)院,青島 266071)

直角邊零件的輪廓由直角邊組成,并且任意相鄰兩邊之間的夾角都是直角,對(duì)這種零件的排樣布局稱為直角邊零件下料問(wèn)題.直角邊零件在許多領(lǐng)域中都有廣泛的應(yīng)用,如普通機(jī)械、專業(yè)設(shè)備等制造行業(yè)的型材、金屬切割、木材加工、建筑行業(yè)的平板玻璃切割等,但直角邊零件加工普遍存在余料剩余較多,加工效率較低,原材料浪費(fèi)等問(wèn)題[1,2].因此,優(yōu)化直角邊零件排樣布局,使直角邊零件下料后產(chǎn)生的廢料最少,即板材的利用率最高,對(duì)降低企業(yè)生產(chǎn)成本具有重要意義和實(shí)用價(jià)值.

目前直角邊零件下料布局優(yōu)化問(wèn)題已有大量相關(guān)研究,Gilmore 和Gomory[3]利用動(dòng)態(tài)規(guī)劃算法求解矩形零件的布局被認(rèn)為是解決二維切割問(wèn)題的基本方法；張燕玲等[2]基于改進(jìn)的Basely 模型[4]設(shè)計(jì)實(shí)現(xiàn)了一種可用于直角邊下料問(wèn)題的整數(shù)規(guī)劃模型；戚得眾等[5]提出了一種基于工藝與形狀特征的下料零件分組下料優(yōu)化模型；Fabio Furini 等[6]通過(guò)建立混合整數(shù)線性規(guī)劃模型表示二維切削問(wèn)題中一般切刀約束的問(wèn)題；葛志輝等[7]提出一種基于工藝約束策略的二維不規(guī)則排樣算法；張旭等[8]給出了一種基于最大移動(dòng)距離的啟發(fā)式算法,改善了排樣結(jié)果.然而,由于直角邊零件下料布局優(yōu)化是NP-Hard (Non-deterministic Polynomial Hard)[9]問(wèn)題,不能在多項(xiàng)式時(shí)間內(nèi)解決,多數(shù)研究獲得的結(jié)果只能趨近于最優(yōu)解而很難達(dá)到最優(yōu)解；即便獲得最優(yōu)解,由于現(xiàn)有研究普遍將材料利用率作為唯一的優(yōu)化目標(biāo),獲得的排樣結(jié)果雖然是理論上的最優(yōu),但切割操作難度卻較大,依然存在實(shí)用性不強(qiáng)的問(wèn)題.

針對(duì)上述問(wèn)題,本文提出了一種基于排樣矩形的動(dòng)態(tài)規(guī)劃方法,將板材的布局問(wèn)題轉(zhuǎn)化為若干個(gè)優(yōu)化子問(wèn)題,而每個(gè)子問(wèn)題的最優(yōu)解能夠通過(guò)本文提出的排樣矩形得到,在此基礎(chǔ)上,基于動(dòng)態(tài)規(guī)劃思想構(gòu)建直角邊零件下料問(wèn)題的求解算法,該算法通過(guò)將NP-Hard 問(wèn)題轉(zhuǎn)換為在多項(xiàng)式時(shí)間內(nèi)可以進(jìn)行求解的一般問(wèn)題,降低了算法求解的時(shí)間復(fù)雜度.實(shí)驗(yàn)結(jié)果表明,對(duì)于一般直角邊零件,本算法與傳統(tǒng)的直角邊零件板材切割相比,板材的利用率提高了30%-50%；同時(shí),本算法在減少板材余料的同時(shí)保證了排樣簡(jiǎn)單操作可行,降低了對(duì)工藝的要求,在工廠生產(chǎn)中容易實(shí)現(xiàn).

1 問(wèn)題描述

不失一般性,將板材抽象為L(zhǎng)×W的長(zhǎng)方形R,L和W表示R的長(zhǎng)與寬,左下角為坐標(biāo)原點(diǎn)(0,0),右上角坐標(biāo)為(L,W),將R在長(zhǎng)和寬兩個(gè)方向上按照單位長(zhǎng)度進(jìn)行劃分得到L×W個(gè)小正方形,稱之為格點(diǎn)[10],格點(diǎn)的角點(diǎn)坐標(biāo)表示為(x,y),其中0≤x≤L,0≤y≤W.如圖1.

任意直角邊零件m均存在一個(gè)最小外接矩形r,稱r為零件m的最小包絡(luò)矩形[11],表示為其中分別為r的右上角和左下角坐標(biāo).將記為零件的長(zhǎng),記為零件的寬,其中包絡(luò)矩形r由其右上角坐標(biāo)和左下角坐標(biāo)確定.直角邊不規(guī)則零件及其包絡(luò)矩形如圖2.定義1(m在R上的規(guī)范擺放方式).直角邊零件m在R上可以有任意種擺放方式,當(dāng)m的各直角邊要么與最小包絡(luò)矩形r的直角邊垂直要么與最小包絡(luò)矩形r的直角邊平行時(shí),稱為m在R上的規(guī)范擺放方式.

如圖1所示,板材R上的T字型零件的規(guī)范擺放方式有4 種.易見(jiàn),對(duì)任何直角邊零件m,通過(guò)旋轉(zhuǎn),其在板材R上規(guī)范的擺放方式最多有4 種.對(duì)給定的板材R(L×W),尋找一種使得直角邊零件按規(guī)范方式擺放個(gè)數(shù)最多的排樣布局,即切割后余料最少,這是一個(gè)NP-Hard 問(wèn)題,不能在多項(xiàng)式時(shí)間內(nèi)進(jìn)行求解.

圖1 板材的格點(diǎn)劃分

圖2 直角邊不規(guī)則零件及其包絡(luò)矩形

設(shè)有N個(gè)直角邊零件在R上規(guī)范擺放,ri表示直角邊零件i(1≤i≤N)的包絡(luò)矩形,令 ∩{ri|1≤i≤N}表示N個(gè)包絡(luò)矩形在R上所占區(qū)域的交集,當(dāng) ∩{ri|1≤i≤N}=Φ時(shí)表示N個(gè)包絡(luò)矩形在R上不重疊,反之則表示在R上存在重疊區(qū)域.類似的,令 ∩{mi|1≤i≤N}表示N個(gè)直角邊零件在R上所占區(qū)域的交集,當(dāng)∩{mi|1≤i≤N}=Φ時(shí)表示N個(gè)直角邊零件在R上不重疊,顯然,當(dāng) ∩{ri|1≤i≤N}=Φ時(shí)必然有 ∩{mi|1≤i≤N}=Φ.

直角邊零件下料問(wèn)題：求解在給定長(zhǎng)為L(zhǎng),寬為W的板材R上排樣N個(gè)直角邊零件最省料的排樣模式,即是求解以下目標(biāo)函數(shù)：

優(yōu)化子問(wèn)題1.求解在R上給定寬為w(w≤W)的局域長(zhǎng)方形區(qū)域內(nèi)排樣p個(gè)直角邊零件最省料的排樣模式,即是求解以下目標(biāo)函數(shù)：

優(yōu)化子問(wèn)題2.求解在R上給定長(zhǎng)為l(l≤L)的局域長(zhǎng)方形區(qū)域內(nèi)排樣q個(gè)直角邊零件最省料的排樣模式,即是求解以下目標(biāo)函數(shù)：

針對(duì)優(yōu)化子問(wèn)題1 和問(wèn)題2,要在全排列中確定一個(gè)最優(yōu)的排列組合,也是一個(gè)NP-Hard 問(wèn)題.但是,對(duì)于此問(wèn)題,數(shù)據(jù)量較少時(shí)可以通過(guò)合理的窮舉進(jìn)行解決.根據(jù)文獻(xiàn)[12],下面給出排樣矩形(Layout Rectangle)的定義.

定義2(排樣矩形).根據(jù)先驗(yàn)知識(shí)對(duì)板材R的某一小塊區(qū)域進(jìn)行手動(dòng)排樣,確定一個(gè)排樣矩形LR,使得按照LR沿水平或豎直方向進(jìn)行排樣有一定的規(guī)律可循.其中,沿水平方向有規(guī)律可循的稱為水平排樣矩形(Horizontal Layout Rectangle,HLR),HLR的寬度為常數(shù)w,長(zhǎng)度為可變參數(shù)x,零件在HLR上的排樣個(gè)數(shù)滿足規(guī)律函數(shù)Gx(x)；同樣,沿豎直方向有規(guī)律可循的稱為豎直排樣矩形(Vertical Layout Rectangle,VLR),VLR的長(zhǎng)度為常數(shù)l,寬度為可變參數(shù)y,零件在VLR上的排樣個(gè)數(shù)滿足規(guī)律函數(shù)Gy(y).

2 基于排樣矩形的直角邊下料模型

對(duì)于直角邊零件m,假設(shè)總共有4 種不同的規(guī)范擺放方式,對(duì)于每種擺放方式,都分別存在一個(gè)HLR和VLR,則直角邊零件m共有8 個(gè)排樣矩形.將直角邊零件m沿第j(j=1,2,3,4,下同) 種規(guī)范擺放方式得到的水平排樣矩形記為HLRj,排樣矩形的寬度記為wj,m在HLRj的排樣個(gè)數(shù)滿足的規(guī)律函數(shù)記為Gxj(x)；同理,m沿第j種規(guī)范擺放方式得到的豎直排樣矩形記為VLRj,排樣矩形的長(zhǎng)度記為lj,m在HLRj的排樣個(gè)數(shù)滿足的規(guī)律函數(shù)記為Gyj(y).圖3(a)和圖3(b)分別是T 字型零件和工字型零件的水平排樣矩形和豎直方向排樣矩形,其中紅色和藍(lán)色區(qū)域可以進(jìn)行排樣,淺灰色區(qū)域?yàn)榕艠泳匦蔚奈蠢貌糠?基于排樣矩形可以確定規(guī)律函數(shù)Gxj(x)、Gyj(y)的具體形式.

針對(duì)于直角邊下料問(wèn)題,把它分解成若干優(yōu)化子問(wèn)題1 和優(yōu)化子問(wèn)題2,然后從這些子問(wèn)題的解得到原問(wèn)題的解.

由定義2 可得,采用HLR進(jìn)行排樣可以使得在寬度為w的矩形中零件m的數(shù)量最多,因此優(yōu)化子問(wèn)題1的解轉(zhuǎn)換為：

同理可得,采用VLR進(jìn)行排樣可以使得在長(zhǎng)度為l 的矩形中零件m的數(shù)量最多,因此優(yōu)化子問(wèn)題2 的解轉(zhuǎn)換為：

按照動(dòng)態(tài)規(guī)劃[13]的思想,直角邊零件在(x,y)處按照方式j(luò)(j=1,2,3,4)放置時(shí)點(diǎn)(x,y)的最大放置數(shù)量N(x,y)的有：

圖3 排樣矩形

(1)如果排樣矩形采用HLR,當(dāng)y＞wj時(shí),設(shè)點(diǎn)(x,y) 的最大放置數(shù)量為N(x,y),則N(x,y) 與點(diǎn)(x,y?wj)的最大放置數(shù)量N(x,y?wj)有關(guān).點(diǎn)(x,y)的最大放置數(shù)量N(x,y)可表示為：

(2)如果排樣矩形采用VLR,當(dāng)x＞lj時(shí),點(diǎn)(x,y)的最大放置數(shù)量為N(x,y),則N(x,y)與點(diǎn)(x?lj,y)的最大放置數(shù)量N(x?lj,y)有關(guān).點(diǎn)(x,y)的最大放置數(shù)量N(x,y)可表示為：

根據(jù)上述討論可知,板材在點(diǎn)(x,y)若要獲得最大的零件放置數(shù)量,需要考慮以下8 種情況：

采用文獻(xiàn)[14]的動(dòng)態(tài)規(guī)劃算法對(duì)建立的式(8)進(jìn)行求解,具體的算法步驟如下：

Step 1.根據(jù)特定的直角邊零件m,確定排樣矩形對(duì)應(yīng)的規(guī)律函數(shù)Gxj(x)、Gyj(y).建立兩個(gè)矩陣NL×W、TL×W,初始化為全0 矩陣.其中N矩陣用來(lái)存儲(chǔ)各點(diǎn)處的零件最大放置數(shù)量,T矩陣用來(lái)記錄具體的排樣方式.

Step 2.按照由左至右、由上至下的順序遞推出在該點(diǎn)(x,y)處的零件最大放置數(shù)量,并將(x,y)處的切割方案記錄在T(x,y)中.

Step 3.判斷當(dāng)前坐標(biāo)可否放置零件.將當(dāng)前坐標(biāo)記為(x,y),若min(x,y)＜min{wj,lj}(j=1,2,3,4),則表示當(dāng)前坐標(biāo)不能放置零件,N(x,y)=0,T(x,y)=0,轉(zhuǎn)至Step 2,否則轉(zhuǎn)至Step 4.

Step 4.根據(jù)動(dòng)態(tài)規(guī)劃的思想,如果已經(jīng)求得當(dāng)前點(diǎn)的所有子狀態(tài)的最優(yōu)解,那么當(dāng)前狀態(tài)的最優(yōu)解根據(jù)式(8)可用所有子狀態(tài)的最優(yōu)解推導(dǎo)出來(lái).

Step 5.求解得到整塊板材的最優(yōu)解N(L,W),根據(jù)矩陣T(L,W)回溯得到具體的切割方案.

算法的偽代碼如算法1.

算法1.切割算法輸入：?jiǎn)栴}的實(shí)例參數(shù)N,T,wj,lj(j=1,2,3,4),規(guī)律函數(shù),輸出：?jiǎn)栴}實(shí)例的最優(yōu)解方案GxjGy j 0 初始化N,T 1 N=zeros(L,W)2 T=zeros(L,W)3 For x in range(0,L)：#約束個(gè)數(shù)4 For y in range(0,W)：5 If y＞=wj：Gxj 6 tyj=N(x,y?wj)+ (x)7 Endif 8 If x＞=lj：Gy j 9 txj=N(x?lj,y)+ (y)10 Endif 11 N(x,y)=max(tyj,txj)12 T(x,y)=對(duì)應(yīng)N(x,y)取最大值時(shí)的切割方案13 Endfor 14 Endfor

3 算例與結(jié)果分析

使用的計(jì)算機(jī)配置環(huán)境為Win10,intel CORE i5 8th Gen,8 GB 內(nèi)存.選用的軟件語(yǔ)言Python 3.7.

采用幾組相關(guān)的基準(zhǔn)數(shù)據(jù)進(jìn)行測(cè)試,基準(zhǔn)數(shù)據(jù)[2]由北京鐵路信號(hào)公司的生產(chǎn)實(shí)例中產(chǎn)生.

針對(duì)不同的排樣零件類型以及不同的板材尺寸,生成相應(yīng)地排樣方案,并計(jì)算出對(duì)應(yīng)的板材利用率,與傳統(tǒng)排樣算法進(jìn)行比較,具體結(jié)果如表1及圖4至圖11所示.如表1所示,針對(duì)不同的直角邊零件,本文提出的算法與傳統(tǒng)的排樣算法相比其材料利用率都有較大的提高.

表1 不同尺寸板材切割利用率結(jié)果

對(duì)于一些常見(jiàn)的直角邊零件,將本文算法與已有研究文獻(xiàn)中的算法進(jìn)行比較,具體結(jié)果如表2和表3所示.結(jié)果表明,針對(duì)于T 字型零件、十字型零件、凸字型零件,本文提出的算法在材料利用率優(yōu)于文獻(xiàn)[2,15,16]闡述的算法,包括格點(diǎn)改造算法、頂點(diǎn)覆蓋算法、以及滾動(dòng)優(yōu)化算法.同時(shí),排樣矩形的引入使得本文算法提供的排樣方案有一定的規(guī)律可循,與目前存在的所有算法相比,降低了對(duì)機(jī)器工藝的要求,更具有實(shí)際操作意義.

圖4 T 字型切割方案圖(210×150)

圖5 T 字型切割方案圖(2000×940)

圖6 凸字型切割方案圖(1000×500)

圖7 凸字型切割方案圖(2000×1000)

圖8 十字型切割方案圖(1200×500)

圖9 十字型切割方案圖(2000×1000)

圖10 工字型切割方案圖(320×160)

圖11 工字型切割方案圖(650×320)

表2 T 字型和十字型零件板材利用率對(duì)比(單位：%)

表3 凸字型零件板材利用率對(duì)比(單位：%)

4 總結(jié)與展望

本文針對(duì)直角邊零件下料優(yōu)化布局問(wèn)題,提出了一種基于排樣矩形的動(dòng)態(tài)規(guī)劃求解算法,該算法通過(guò)將整塊板材的優(yōu)化問(wèn)題轉(zhuǎn)換為若干最小子優(yōu)化問(wèn)題,采用動(dòng)態(tài)規(guī)劃的思想進(jìn)行模型的建立與求解.實(shí)驗(yàn)表明,與現(xiàn)有的排樣算法相比,本算法能夠顯著提高材料利用率,同時(shí)減少了復(fù)雜排樣的產(chǎn)生,便于在生產(chǎn)中進(jìn)行操作.未來(lái)將進(jìn)一步拓展本文算法將其應(yīng)用于二維不規(guī)則零件的下料布局優(yōu)化問(wèn)題.