基于寬容分層策略的啟發式排樣算法

梁利東,賈文友

0 引言

Packing問題的排樣優化方法是工程設計及制造領域中的研究熱點,廣泛應用于機械制造、印刷業排版、木材加工、玻璃切割、家具下料、服裝裁剪等行業中,高效排樣算法的研究對提高生產效率和經濟效益具有重要的實際意義。二維(2D) Packing問題是尋找平面最優布局的優化問題,即將一系列零件不可相互重疊地合理布置在原材料中,使原材料的利用率達到最大。作為組合優化領域中計算復雜性最高的一類非確定性多項式完全(Nondeterministic Polynomial Complete, NPC)問題[1],排樣方法涉及計算機科學及數值優化理論的核心問題,因此具有深刻的理論研究價值。

通常的優化排樣問題(以矩形件為例)的數學模型可表示為:

(1)

s.t.Pi(Δxi,Δyi)∩Pj(Δxj,Δyj)=?,i≠j

(2)

0≤xim(θi,Δxi,Δyi)≤L,m=1,2,…,ni

(3)

0≤yim(θi,Δxi,Δyi)≤W,m=1,2,…,ni

(4)

其中：ti為參與排樣因子,表示零件i是否參與排樣,取值為1或0;xim和yim為零件i上第m個頂點的坐標。約束式(2)表示零件與互不重疊,約束式(3)～(4)表示所有零件不能排在原材料之外。由于面積Si是一個與位置無關的參數,因此上面的優化排樣模型中,其決策變量為θi、Δxi、Δyi、ti。

排樣問題的求解包括排序方法和定位規則兩個方面,目前研究的算法主要分為三類:精確算法、啟發式算法和元啟發式算法(meta-heurisic methods)。精確算法如樹搜索、分枝定界法等[2-3],算法的計算復雜度太高、耗時較大,對于排樣規模也有局限;而啟發式算法源于數值計算理論的有效性,可在合理的時間范圍內獲得近似較好的解而得到廣泛運用,典型的啟發式定位算法如表1所示。

隨著智能優化算法,如模擬退火算法(Simulated Annealing, SA)、遺傳算法(Genetic Algorithm, GA)、人工神經網絡(Artificial Neural Network, ANN)、粒子群優化(Particle Swarm Optimization, PSO)及蟻群優化(Ant Colony Optimization, ACO)算法等方法的日益成熟,元啟發式算法則是利用智能算法實現排樣次序的優化,并結合基本啟發式算法來求解Packing問題。如Jiang等[16]結合遺傳算法提出了GA+底部左齊擇優匹配(Lowest-Level Left Align Best Fit, LLABF)算法，Liu等[17]提出了GA+IBL(Improved Bottom Left)算法,二者都是在BL算法的基礎上對其進行改進;基于最小浪費的思想,Zhang等[18]提出了GA+IHR(Improved Heuristic Recursive)算法;Hopper等[19]將BLF與GA和SA等智能算法相結合,提出了GA+BLF、SA+BLF等算法,也都是基于BL算法所進行的優化;基于BF(Best Fit)的思想,Burke等[20]分別結合禁忌搜索(Tabu Search, TS)、SA和GA算法,實現并比較了BF+TS、BF+SA和BF+GA這三種算法的性能,取得了比BF算法更好的結果,同時發現,BF+SA可以取得最好的效果;Borfeldt[21]結合遺傳算法給出了基于層的該問題的SPGAL(Strip Packing Genetic Algorithm based on Layer)。

表1 啟發式排樣算法

上述啟發式算法在求解矩形件Packing問題中大都取得不錯的結果,特別是LSBF算法[15]和LLABF算法[16]均采用了擇優匹配的定位方法,并通過枚舉建立矩形匹配的適應度評價值,獲得部分Benchmark的完美排樣。但兩種算法的匹配優先原則都側重于完全匹配(Full Fit, FF)和部分匹配類型,如寬度匹配(Width Fit, WF)、高度匹配(Height Fit, HF)和組合匹配(Joint Fit,JF),而對于可能出現的多種可排入匹配(Placeable Fit, PF)的一般情形,由于缺乏排入匹配的評價機制,對全局排樣布局將產生不同的影響。文獻[10]的砌墻啟發式算法中通過設定絕對基準磚高度來約束每層的排樣空間,可有效控制最低排樣高度,但該算法與擇優匹配思想存在一定矛盾。

綜合以上算法的優劣,本文基于多目標寬容分層規劃思想,提出一種寬容分層的啟發式算法(Forbearing Stratified Heuristic Algorithm, FSHA),該算法構造擇優匹配優化模型及評價函數,以此來設計排放矩形的優先規則,并針對一般排放情況,引入寬容參數,實現矩形定位的優化過程。

1 FSHA模型

1.1 問題的描述及定義

Packing問題的最優求解是尋求諸多幾何體在不能重疊和超出邊界的約束下在給定板材區域中的最優圖形組合,以獲得最小排樣高度或最大排樣密度。在矩形排樣中,假設初始板材區域寬度為W,高度為H,待排n個矩形表示為pj(xj,yj,wj,hj),j∈{1,2,…,n}。其中:(xj,yj)表示pj的左下角坐標;(wj,hj)表示的寬度和高度。建立笛卡兒坐標系,相關定義如下:

1)排樣空間。表示當前m個空閑矩形區域,可表示為Si(sxi,syi,swi,shli,shri),i∈{1,2,…,m},其中(sxi,syi)為該空間左下角坐標,swi為該空間的寬度,(shli,shri)分別表示該空間左壁和右壁的高度。若空間左壁(或右壁)為板材邊界,則shli=H或shri=H,如圖1所示。

2)可行空間。若存在待排矩形,使得wj≤swi,則該空間為可行空間；否則為不可行空間。

3)合并空間。當存在不可行空間,該空間則與相鄰空間進行合并產生新的空間。

圖1 排樣空間的定義

排樣矩形與排樣空間建立參數匹配關系,并以此設計矩形放置規則,定義如下:

1)寬度匹配值fwij，表征可行空間Si的寬度與排入矩形pj的寬度的匹配程度,其中當swi=wj時,寬度匹配最佳。計算公式如下:

(5)

2)高度匹配值fhij表征可行空間的高度與排入矩形高度的匹配程度,其中,當Δhlij=0(左平齊)或Δhrij=0(右平齊),則fhij=1,高度匹配為最佳。計算公式如下:

(6)

基于以上排樣空間的劃分及匹配值的定義,選定最低排樣空間,遍歷所有待排矩形與該空間進行匹配排放。圖2為不同的匹配類型,基本涵蓋了待排矩形的全部可排放情景,其中假設shr≤shl;反之情況類似。

圖2 不同匹配值

1.2 匹配函數模型及適應度

當前矩形的匹配擇優過程可視為寬度匹配值和高度匹配值最大化的多目標優化問題,優化函數的數學模型表示如下:

V-maxFij=max [fwij,fhij]

(7)

s.twj≤swi

hj≤H

從圖2的4種匹配類型中,只有完全匹配為多目標目標函數的當前最優解,其他匹配情形均無法獲得最優,因此可根據不同匹配情況,設計其目標函數(或稱匹配適應度)的計算方法及排放規則:

1)完全匹配。待排矩形的寬度等于可排空間寬度即fwij=1,且高度等于可排空間高度(包括左高平或右高平)即fhij=1。匹配適應度值Fij=fwij+fhij=2,為最佳匹配。若存在多個完全匹配情形時,矩形高度hj小者優先入排。

2)部分匹配。只滿足寬度匹配或高度匹配即fwij=1,fhij<1或fwij<1,fhij=1,匹配適應度值Fij=max(fwij,fhij)=1,排入規則:

① 若多個矩形同時符合寬度匹配或高度匹配,以入排次序進行排放;

② 若多個矩形僅符合寬度匹配,矩形hj小者優先入排;

③ 若多個矩形僅符合高度匹配時,矩形寬度小者優先且向高度平齊一方靠接排放。

3)可排入匹配。待排矩形的寬度小于可排空間寬度即fwij<1,且高度與可排空間高度不相等即fhij<1,匹配適應度值為Fij=c1fwij+c2fhij,其中c1、c2(c1,c2∈(0,0.5])分別為寬度和高度寬容值,即當存在多個矩形同時滿足可排入匹配時,兩個寬容值決定寬度和高度匹配的選擇權重(在起始階段,初始空間通常對于所有矩形均為可排入匹配,且H視為無限高,第一個入排矩形的選擇根據排放序列確定)。設置寬容值旨在對兩個匹配分目標的實現分層優化策略。注意:當排樣空間左(或右)邊為板材邊界時,則采用占角規則[14]。

可見,最優化匹配適應度函數取決于排樣空間三個匹配參數的關系,即:Δw為排樣區域寬度與入排矩形寬度的絕對差值;Δhl為排樣區域的左邊(壁)高度與入排矩形高度的絕對差值;Δhr為排樣區域的左邊(壁)高度與入排矩形高度的絕對差值。表2給出匹配適應度及參數關系說明。

表2 匹配適應度評價及參數說明

注:匹配類型可通過矩形旋轉實現擇優匹配。

2 FSHA流程

FSHA是依據匹配適應度值和擇優匹配優先原則實現分層定位布局的啟發式算法,其算法設計如下。

輸入 板材的寬度W和高度H(無限高),n個待排矩形pj(xj,yj,wj,hj),j∈{1,2,…,n}。

輸出 排樣高度或排樣密度,其中

FSHA()

{

for(j=1;j<=n;j++) initialize (RectList[]);

//初始化矩形入排序列

設置寬容參數c1,c2

for(i=0;i<可行排樣空間數目,i++){

for(j=1;j<=n;j++) {

if (S(i)為不可行空間); break;

//選擇下一個最低空間

Function_FitType(i,j)

//判斷匹配類型

if (Δw=0, Δh=0,)Fij=2 break;

//完全匹配類型

Else if(Δw=0, Δh>0)Fij=1;

//寬度匹配類型

Select(min(hj));

//選擇高度最低矩形

Else if(Δw>0, Δh=0)Fij=1;

//高度匹配類型

Select(min(wj));

//選擇寬度最小矩形

Else if(Δw>0, Δh>0) {

可排入匹配類型,計算當前匹配適應度Fij

Select(max(Fij));

//選擇適應度最大矩形

}

}

Pack(i,j); 在空間i排入矩形RectList[j]

更新排樣空間S(i),并以空間最低原則排序

}

計算輸出排樣適應度(排樣高度或排樣密度)

}

基于以上算法的實現過程,FSHA的流程示意如圖3所示。

圖3 FSHA流程

3 FSHA應用舉例

算例1 給定5個待排矩形,如不考慮旋轉,可存在4種最優排樣布局,其排樣高度均為最優高度,排樣密度達到100%,如圖4所示。要獲得一個最優布局(以圖4(a)為例),對于序列模式{1,2,*,*,*} (“*”表示未列出的矩形編號),LLABF、LSBF及砌墻式算法得到排樣布局都出現空洞現象,如圖5所示。

圖4 算例1的最優排樣結果

圖5 LLABF、LSBF及砌墻式算法的排樣布局

采用FSHA匹配原理及評價方法,只要矩形1為第一個入排矩形,均可獲得如圖4(a)的最優排樣布局,算法步驟如下:

1)初始化排樣空間和參考位置原點,初始空間為S0(0,0,W,H)。

2)起始階段,所有零件均屬于可排入匹配情況,直接入排矩形1,選擇最低空間S。

3)依照算法的匹配規則,矩形2為當前最低空間S唯一可排入矩形,且滿足寬度匹配,F=1,寬度匹配不受排樣高度約束,故排入2,更新最低空間S。

4)遍歷未排矩形,矩形4和5都滿足高度匹配,maxF=1,依據寬度小者優先和匹配邊靠接原則,選擇4排入。

5)依次類推,可依次排入矩形3和5,構成最佳排樣布局,如圖6所示。

可以看出, FSHA對于排序模式{2,*,*,*,*}、{5,*,*,*,*}、{3,*,*,*,*},也均可獲得其他最優布局如圖4(b)、(c)和(d)。

圖6 算例1的排樣過程

算例2 假設板材寬度W=100,高度H不限,取6個矩形,并任意給定各矩形的寬度和高度,矩形序列P可表示為{p1(42,30),p2(40,18),p3(40,26),p4(40,10),p5(16,44),p6(44,8)},如圖7(a)所示?？梢园l現,無論怎樣排放均無法獲得理想的最優布局,此為大規模排樣中常見的一般情形,因此,快速尋求較好的有效解是設計排樣算法的關鍵。

以{1,*,*,*,*}排入模式為例(暫不考慮旋轉),根據本文算法規則首先排入矩形1,確定最低空間S,由于不存在完全匹配和部分匹配,按照式(5)～(6)分別計算剩余待排矩形{p2,p3,p4,p5,p6}與S的匹配適應度,Fi=c1fwi+c2fhi。取c1=c2=0.5,可得:F2=0.644 8,F3=0.778 2,F4=0.511 5,F5=0.404 6,F6=0.512 6。若調整寬容參數為c1=0.5,c2=0,1,可得F2=0.404 8,F3=0.431 5,F4=0.378 1,F5=0.191 2,F6=0.406 0?？芍猰axF=F3,故選擇矩形3排入。依次類推,排完所有待排矩形,可得到排放序列{1,3,5,2,6,4},排樣高度Hpack=48,排樣密度為93.25%,此為較好的有效解,如圖7(g)所示。對于排入模式{1,2,3,4,5},LLABF和砌墻式算法,得到排樣結果如圖7(h)和(i)所示。若要獲得更好解,還需進行排序優化。

4 GA+FSHA

FSHA的匹配規則雖對排序進行了局部優化,但隨排樣規模的增加仍依賴于矩形序列的全局尋優,本文采用遺傳算法GA與FSHA結合方式來求解二維矩形條排樣優化問題。由GA確定種群規模、編碼方式并隨機生成初始矩形集合的排序,利用FSHA決定矩形的排放規則,通過遺傳操作和適應度評價來實現矩形排樣的最優化過程。

4.1 編碼及適應度函數

對于矩形Packing問題,通常采用序號編碼方式進行編碼設計,個體染色體序號編碼可表示為Ek={1,2,…,n}。編碼中序號對應入排零件,正負表示矩形旋轉與否。例如編碼{1,3,-2,4,-5},表示矩形排入順序為13 245,其中矩形2和5需旋轉90°。

設給定板材的規格尺寸(寬度W和高度H為定值),個體的適應度評價分兩種情況:

1)如果所有待排矩形均可排入,優化目標為最低排樣高度或最大排樣密度,個體適應度函數表示為Fit=1/Hpack,其中Hpack為個體的矩形排樣高度。

2)如果所有待排矩形不可能全部排入,根據匹配適應值和個體排序的不同,可導致即使同一塊板材,多次排樣結果所包含的零件數量和種類亦不相同。因此,排樣目標為每個入排矩形匹配值求和的最大值,個體適應度函數如下表示:

(8)

4.2 遺傳操作

1)選擇運算。對種群中所有個體的適應度值從大到小排序,優選首位基因不同的m個最優個體(視種群規模而定)直接作為下一代個體,其余n-m個體以輪盤賭方式[18]進行選擇。該選擇方法是基于匹配定位規則的局部排序優化,實現個體的最優保存和種群多樣性策略。

2)交叉運算。本文采用兩點交叉,以一定的概率pc交換兩個體的基因片斷而產生新個體的過程。即在區間[1,n]內生成兩個不等的隨機數p和q作為交叉位,設p

3)變異運算。采用雙變異方式,即按照變異概率pm對個體的排序和旋轉進行操作。其中排序變異是對隨機產出的兩變異點(α1,α2)的矩形互換位置;旋轉變異則是對變異點r的矩形旋轉角度90°。如:選擇個體為{1,2,3,4,5},變異點(α1,α2)=(3,5),r=4,經過變異操作后產生的新個體表示為{1,2,5,-4,3}。

5 實驗與分析

本文開發環境為VB 6.0+SQL Server 2000,實驗平臺為Intel CPU 2.4 GHz, 4 GB RAM, Windows 10。設定種群規模為20,預設寬容系數c1=c2=0.5,交叉概率pc=0.8,變異概率pm=0.5。

實驗1 對兩組理想排樣布局進行算法測試,其中一組以200×200的板材隨機劃分生成算例數據,如表3所示。另一組來自文獻[19]的C1P1(Category1 Problem1)問題(W×H=20×20, 16 items),運用FSHA運行10次,均獲得最優排樣布局如圖8所示。

表3 隨機算例的測試數據

圖8 實驗1的最優排樣布局

實驗2 為驗證算法的有效性,根據問題規模的不同,本文對benchmark的7類數據[19]分別進行測試,不同算法的實驗對比結果如表4所示。

表4 算例的測試數據的 Gap 值 %

表4中:Gap表示為排樣的相對高度,即Gap=(Hpack-H*)/H*,其中H*為理想高度?？梢钥闯?本文算法對于小規模問題均可獲得滿意的最優解,隨著問題規模的增加,相對于A1及LLABS算法,Gap的平均值降低了2%。注意:以上測試結果在FSHA求解中,是通過隨機調整不同的寬容值c1和c2而獲得的最優結果。實驗發現,寬容系數c1和c2的不同取值對實驗結果具有一定的影響:c1越大,寬度匹配越優先于高度匹配，反之亦然；其大小的選擇往往隨著排樣問題和排樣規模的不同而需測試調整。

實驗3 針對不同矩形類型入排的一般情況,本文從benchmark的7類數據中隨機選擇兩組數據進行測試,GA迭代次數為50,最優排樣結果如圖9所示。其中,一組數據取自C1P1+C3P1中的33個矩形,設置板材寬度為20,高度不限(水平方向),計算排樣高度為24,排樣密度為93.35%;另一組數據從C2～C7中任選66個矩形,設置板材寬度為100,高度不限,計算排樣高度為339,排樣密度為91.28%。

圖9 實驗3的最優排樣布局

實驗4 FSHA方法也可應用于異形件排樣,數據取自某船舶零件,設置板材規格W*H=2 000*6 000。排樣過程采用了異形件的矩形化包絡和組合填充的預處理操作,在每個包絡零件排入后再進行正交靠接。圖10為不經過排序優化由初始序列一次得到排樣結果,可排入65個零件,排樣密度達到87.37%,其中排樣密度為排入零件的面積之和與板材面積的比率。排樣結果的板材利用率雖不算太高,但可以說明該算法在異形件排樣過程中的有效性?；诋愋瘟慵D形的不規則特征,可結合相關不規則件排樣算法進行研究探索。

圖10 異形件的排樣布局

6 結語

本文針對二維矩形Packing問題,提出了基于寬容分層規則及匹配函數評估的優化算法FSHA,并給出了算法的思想、模型，以及具體實現方法。實驗結果表明,該算法的定位寬容分層匹配策略明確了不同匹配類型的劃分和優先放置規則,可有效優化排樣結果,并可結合碰靠算法應用于異形件packing問題的求解。由于寬容值的大小設定直接影響排樣定位規則和最優布局,寬容參數的取值決定了寬度匹配和高度匹配的優先程度,如何將其與排放矩形和排樣空間的圖形屬性建立關系,將是下一步研究的重點。

參考文獻(References)

[1] LODI A, MARTELLO S, MONACI M. Two-dimensional packing problems: a survey[J]. European Journal of Operational Research, 2002, 141(2): 241-252.

[2] LESH N, MARKS J, MAHON A, et al. Exhaustive approaches to 2D-rectangular perfect packings[J]. Information Processing Letters, 2004, 90(1): 7-14.

[3] MARTELLO S, MONACI M, VIGO D. An exact approach to the strip-packing problem [J]. INFORMS Journal of Computing, 2003, 15(3): 310-319.

[4] BAKER B, COFFMAN E, RIVEST L. Orthogonal packings in two dimensions [J]. SIAM Journal on Computing, 1980, 9(4): 846-855.

[5] CHAZELLE B. The bottom left bin packing heuristic: an efficient implementation [J]. IEEE Transactions on Computers, 1983, C-32(8): 697-707.

[6] HOPPER E, TURTON B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research, 2001, 128(1): 34-57.

[7] LESH N, MITZENMACHER M. BubbleSearch: a simple heuristic for improving priority-based greedy algorithms [J]. Information rocessing Letters, 2006, 97(4): 161-169.

[8] BURKE E, KENDALL G, WHITWELL G. A new placement heuristic for the orthogonal stock-cutting problem[J]. Operations Research, 2004, 52(4): 655-671.

[9] BORTFELDT A, GEHRING H. New large benchmark instances for the two-dimensional strip-packing problem with rectangular pieces[C]// Proceedings of the 39th Hawaii International Conference on Systems Sciences. Washington, DC: IEEE Computer Society, 2006: 30.

[10] 張德富, 韓水華, 葉衛國.求解矩形Packing問題的砌墻式啟發式算法[J]. 計算機學報, 2008, 31(3) : 509-515.(ZHANG D F, HAN S H, YE W G. A bricklaying heuristic algorithm for the orthogonal rectangular packing problem[J]. Chinese Journal of Computers, 2008, 31(3): 509-515.)

[11] 姚怡, 吳金波, 賴朝安. 采用分層搜索填充策略的啟發式帶排樣算法[J]. 武漢大學學報(工學版), 2014, 47(6): 854-859.(YAO Y, WU J B, LAI C A. Heuristics for rectangular strip packing problem based on hierarchical search filled strategy[J]. Engineering Journal of Wuhan University, 2014, 47(6) : 854-859.)

[12] 何琨, 姬朋立. 求解二維矩形Packing面積最小化問題的動態規約算法[J]. 軟件學報, 2013, 24(9): 2078-2087.(HE K, JI P L. Heuristics for solving the 2D rectangle packing area minimization problem basing on a dynamic reduction method[J]. Journal of Software, 2013, 24(9): 2078-2087.)

[13] HUANG W, CHEN D, XU R. A new heuristic algorithm for rectangle packing[J]. Computer & Operations Research, 2007, 34(11): 3270-3280.

[14] CHEN M, HUANG W. A two-level search algorithm for 2D rectangular packing problem[J]. Computer & Industrial Engineering, 2007, 53(1): 123-136.

[15] 張懷宇, 楊根科, 白杰. 二維Strip Packing問題的嵌套啟發式算法[J]. 系統仿真學報, 2012, 24(8): 1601-1605, 1623.(ZHANG H Y, YANG G K, BAI J. Nested heuristic algorithm for two-dimensional strip packing problem[J]. Journal of System Simulation, 2012, 24(8) : 1601-1605, 1623.)

[16] JIANG X, LU X, LIU C. Lowest-level left align best-fit algorithm for the 2D rectangular strip packing problem[J]. Journal of Software, 2009, 20(6): 1528-1538.

[17] LIU D, TENG H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles[J]. European Journal of Operation Research, 2006, 172(3): 814-837.

[18] ZHANG D, CHEN S, LIU Y. An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem[J]. Acta Automatica Sinica, 2007, 33(9): 911-916.

[19] HOPPER E, TURTON B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research, 2001, 128(1): 34-57.

[20] BURKE E, KENDALL G, WHITWELL G. Metaheuristic enhancements of the best-fit heuristic for the orthogonal stocking cutting problem: NOTTCS-TR-2006-3[R]. Nottingham: University of Nottingham, 2006.

[21] BORTFELDT A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces[J]. European Journal of Operational Research, 2006, 172(3): 814-837.

This work is partially supported by the National Natural Science Foundation of China (51576001).