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

郭百海,隋 毅

(青島大學 計算機科學技術學院,青島 266071)

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

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

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

1 問題描述

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

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

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

圖1 板材的格點劃分

圖2 直角邊不規則零件及其包絡矩形

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

直角邊零件下料問題：求解在給定長為L,寬為W的板材R上排樣N個直角邊零件最省料的排樣模式,即是求解以下目標函數：

優化子問題1.求解在R上給定寬為w(w≤W)的局域長方形區域內排樣p個直角邊零件最省料的排樣模式,即是求解以下目標函數：

優化子問題2.求解在R上給定長為l(l≤L)的局域長方形區域內排樣q個直角邊零件最省料的排樣模式,即是求解以下目標函數：

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

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

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

對于直角邊零件m,假設總共有4 種不同的規范擺放方式,對于每種擺放方式,都分別存在一個HLR和VLR,則直角邊零件m共有8 個排樣矩形.將直角邊零件m沿第j(j=1,2,3,4,下同) 種規范擺放方式得到的水平排樣矩形記為HLRj,排樣矩形的寬度記為wj,m在HLRj的排樣個數滿足的規律函數記為Gxj(x)；同理,m沿第j種規范擺放方式得到的豎直排樣矩形記為VLRj,排樣矩形的長度記為lj,m在HLRj的排樣個數滿足的規律函數記為Gyj(y).圖3(a)和圖3(b)分別是T 字型零件和工字型零件的水平排樣矩形和豎直方向排樣矩形,其中紅色和藍色區域可以進行排樣,淺灰色區域為排樣矩形的未利用部分.基于排樣矩形可以確定規律函數Gxj(x)、Gyj(y)的具體形式.

針對于直角邊下料問題,把它分解成若干優化子問題1 和優化子問題2,然后從這些子問題的解得到原問題的解.

由定義2 可得,采用HLR進行排樣可以使得在寬度為w的矩形中零件m的數量最多,因此優化子問題1的解轉換為：

同理可得,采用VLR進行排樣可以使得在長度為l 的矩形中零件m的數量最多,因此優化子問題2 的解轉換為：

按照動態規劃[13]的思想,直角邊零件在(x,y)處按照方式j(j=1,2,3,4)放置時點(x,y)的最大放置數量N(x,y)的有：

圖3 排樣矩形

(1)如果排樣矩形采用HLR,當y＞wj時,設點(x,y) 的最大放置數量為N(x,y),則N(x,y) 與點(x,y?wj)的最大放置數量N(x,y?wj)有關.點(x,y)的最大放置數量N(x,y)可表示為：

(2)如果排樣矩形采用VLR,當x＞lj時,點(x,y)的最大放置數量為N(x,y),則N(x,y)與點(x?lj,y)的最大放置數量N(x?lj,y)有關.點(x,y)的最大放置數量N(x,y)可表示為：

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

采用文獻[14]的動態規劃算法對建立的式(8)進行求解,具體的算法步驟如下：

Step 1.根據特定的直角邊零件m,確定排樣矩形對應的規律函數Gxj(x)、Gyj(y).建立兩個矩陣NL×W、TL×W,初始化為全0 矩陣.其中N矩陣用來存儲各點處的零件最大放置數量,T矩陣用來記錄具體的排樣方式.

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

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

Step 4.根據動態規劃的思想,如果已經求得當前點的所有子狀態的最優解,那么當前狀態的最優解根據式(8)可用所有子狀態的最優解推導出來.

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

算法的偽代碼如算法1.

算法1.切割算法輸入：問題的實例參數N,T,wj,lj(j=1,2,3,4),規律函數,輸出：問題實例的最優解方案GxjGy j 0 初始化N,T 1 N=zeros(L,W)2 T=zeros(L,W)3 For x in range(0,L)：#約束個數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)=對應N(x,y)取最大值時的切割方案13 Endfor 14 Endfor

3 算例與結果分析

使用的計算機配置環境為Win10,intel CORE i5 8th Gen,8 GB 內存.選用的軟件語言Python 3.7.

采用幾組相關的基準數據進行測試,基準數據[2]由北京鐵路信號公司的生產實例中產生.

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

表1 不同尺寸板材切割利用率結果

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

圖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 字型和十字型零件板材利用率對比(單位：%)

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

4 總結與展望

本文針對直角邊零件下料優化布局問題,提出了一種基于排樣矩形的動態規劃求解算法,該算法通過將整塊板材的優化問題轉換為若干最小子優化問題,采用動態規劃的思想進行模型的建立與求解.實驗表明,與現有的排樣算法相比,本算法能夠顯著提高材料利用率,同時減少了復雜排樣的產生,便于在生產中進行操作.未來將進一步拓展本文算法將其應用于二維不規則零件的下料布局優化問題.