劉 虓，徐 磊，陳超核，劉嘉敏

(1.華南理工大學(xué) 土木與交通學(xué)院，廣東 廣州 510640；2.沈陽(yáng)工業(yè)大學(xué) 信息科學(xué)與工程學(xué)院，遼寧 沈陽(yáng) 110870)

0 引言

三維排樣是在三維空間將多個(gè)零件在容器內(nèi)進(jìn)行優(yōu)化布排的過程[1-5]，在船舶/航天器艙室布局設(shè)計(jì)、集裝箱裝運(yùn)、激光燒結(jié)等領(lǐng)域有廣泛應(yīng)用。排樣問題作為一類典型的優(yōu)化問題，其 “設(shè)計(jì)變量”為零件排樣次序；“目標(biāo)函數(shù)”為零件在容器內(nèi)的排布密度；“約束條件”為零件之間以及零件與容器之間不重疊/沖突。將零件依次排入容器并計(jì)算排布密度的算法稱為排樣“構(gòu)造算法”(constructive algorithm)，因此構(gòu)造算法也可看作目標(biāo)函數(shù)的“求解器”。規(guī)則三維排樣算法已較成熟[5]，不規(guī)則排樣算法則處于前沿階段[1-4]。三維不規(guī)則零件幾何要素和運(yùn)動(dòng)自由度較多，相應(yīng)的構(gòu)造算法計(jì)算效率很低，已經(jīng)成為三維不規(guī)則排樣的瓶頸，有必要對(duì)其進(jìn)行更廣泛和深入的研究。

構(gòu)造算法的核心包括零件可行域構(gòu)建和零件重疊檢測(cè)兩個(gè)。臨界多邊形(No Fit Polygon, NFP)是構(gòu)建二維排樣[6]可行域和避免零件重疊的通行工具[1]，但NFP的生成算法比較耗時(shí)，如果將NFP推廣到三維，所謂“臨界多面體”的生成算法將更加復(fù)雜。此外，NFP在考慮零件旋轉(zhuǎn)時(shí)會(huì)進(jìn)一步增加算法耗時(shí)。因此，很多學(xué)者另辟蹊徑，提出兩類方法：①“像素”方法，Stoyan等[7]將零件分解成多個(gè)長(zhǎng)方體，將兩個(gè)零件之間的距離計(jì)算在兩組長(zhǎng)方體之間展開；②“矢量”方法，基于最小勢(shì)能原理的三維排樣啟發(fā)式算法(Heuristic Algorithm based on the principle of minimum total Potential Energy for 3D packing problems, HAPE3D)[8-9]采用多面體表達(dá)零件，將重疊檢測(cè)歸結(jié)于“點(diǎn)與線”以及“線與線”的幾何關(guān)系判斷。HAPE3D的優(yōu)點(diǎn)是：零件定位精確、旋轉(zhuǎn)方便;缺點(diǎn)是：①零件頂點(diǎn)數(shù)較多時(shí)，算法開銷大；②零件只能繞3個(gè)坐標(biāo)軸旋轉(zhuǎn)，實(shí)際上對(duì)零件的可行域進(jìn)行了不必要的限制。

SAT等[10]在二維排樣問題中，嘗試將零件像素化表達(dá)，提高了零件重疊檢測(cè)的效率。本文則在三維排樣問題中將“像素化”和“矢量化”方法進(jìn)行混合，揚(yáng)長(zhǎng)避短，很好地解決了HAPE3D的缺點(diǎn)①。全姿態(tài)(all attitude)主要用來描述航空、航天領(lǐng)域?qū)ο笤诳臻g中的方位姿態(tài)[11-12]。方位姿態(tài)的描述包含兩組要素：①航向角、俯仰角和橫滾角；②機(jī)體坐標(biāo)系與地理坐標(biāo)系之間的關(guān)系。HAPE3D沒有考慮第二組要素，這是產(chǎn)生缺點(diǎn)②的根本原因。本文將“全姿態(tài)”概念引入三維排樣，擺脫了零件只能繞坐標(biāo)軸旋轉(zhuǎn)的束縛，實(shí)現(xiàn)了全方向、多角度的“自由”旋轉(zhuǎn)。

1 概念和預(yù)備知識(shí)

1.1 零件微粒

采用多面體“矢量化”表達(dá)的零件(如圖1a)使用邊長(zhǎng)為PSL(particle side length)的方塊微粒(particle)進(jìn)行填充，即變?yōu)?“像素化”表達(dá)(如圖1b)。如圖1b中的黑色方塊所示，可任選一個(gè)微粒作為參考微粒 (Reference Particle，RP)，零件的平移和旋轉(zhuǎn)均基于RP。

1.2 排樣塊

與零件“像素化”類似，也可用方塊填充容器(如圖2a)，該方塊稱為排樣塊 (Packing Block, PB)，其邊長(zhǎng)BSL (packing block side length)=PSL。為方便觀察，圖2a只繪制了容器上端一隅6個(gè)排樣塊。為了重疊檢測(cè)，設(shè)置布爾變量BlockOccupied作為排樣塊的占用標(biāo)志，其初始值為“空”：BlockOccupied[j]=false，其中j=0,1,…,BN-1(BN為排樣塊個(gè)數(shù))。排入零件后，部分排樣塊被零件微粒“占據(jù)”：BlockOccupied[j]=true。

1.3 “分離”判斷

如零件在容器內(nèi)，且與其他零件“分離”，則其排樣姿態(tài)“可行(Feasible)”。文獻(xiàn)[9]基于矢量圖將零件的分離判斷歸結(jié)于點(diǎn)與多面體的包含關(guān)系以及線段與面的相交關(guān)系，隨著零件幾何要素(點(diǎn)、線、面)的增多，該分離判斷變得非常耗時(shí)。本文提出基于最小勢(shì)能原理和混合圖形的三維排樣啟發(fā)式算法(HAPE3D_Hybrid Representation Graphics, HAPE3D_HRG),將零件重疊檢測(cè)歸結(jié)于零件微粒和排樣塊之間是否重疊的布爾運(yùn)算。顯然，基于布爾運(yùn)算的重疊檢測(cè)更為簡(jiǎn)單、高效，大大提高了構(gòu)造算法的執(zhí)行效率。

1.4 “靠接”算法

零件和容器“像素化”之后，有可能在排入零件之間產(chǎn)生空隙(如圖2b)，可以通過“靠接”算法消除之。

兩個(gè)零件A、B分離，A固定，B向A靠攏直至接觸(但不重疊)，該過程稱為零件的靠接[9]，如圖3所示。為保證足夠的精度，靠接算法需要零件為“矢量化”表達(dá)。

1.5 全姿態(tài)(all-attitude)

全姿態(tài)(all-attitude)在航空航天領(lǐng)域用來描述飛機(jī)、導(dǎo)彈和衛(wèi)星的姿態(tài)。本文將其加以改造并用于三維排樣。

如圖4所示，零件姿態(tài)包含兩個(gè)要素：①零件局部坐標(biāo)系z(mì)L軸的指向；②零件繞zL軸的旋轉(zhuǎn)角。

(1)zL指向的確定方法

如圖5所示，以地球中心為起點(diǎn)，球面某點(diǎn)為終點(diǎn)，即可確定zL指向。設(shè)定正整數(shù)RN(Rotation Number)，就可在球面布置多個(gè)點(diǎn)作為zL的終點(diǎn)，步驟如下：

步驟1沿經(jīng)線從南極到北極經(jīng)過180°，分為RN等份，可確定RN+1個(gè)等分點(diǎn)。

步驟2沿緯線從本初子午線向東出發(fā)，直至回到原點(diǎn)，經(jīng)過360°，共分為2RN等份，可確定2RN個(gè)等分點(diǎn)。

步驟3綜上共有2RN(RN+1)個(gè)分布點(diǎn)，另考慮到南北極各有2RN個(gè)點(diǎn)是重復(fù)的，故分布點(diǎn)個(gè)數(shù)為：

2(RN2-RN+1)。

(1)

當(dāng)RN=3時(shí)，球面上有14個(gè)分布點(diǎn)(如圖5)。

(2)零件繞zL軸的旋轉(zhuǎn)角

如零件繞zL軸旋轉(zhuǎn)2RN個(gè)角度，即每隔180°/RN旋轉(zhuǎn)一個(gè)角度，則每個(gè)分布點(diǎn)對(duì)應(yīng)2RN個(gè)姿態(tài)。如圖5所示，假設(shè)RN=3，從球心到東經(jīng)60°、北緯30°分布點(diǎn)可以確定某個(gè)zL軸，零件繞其旋轉(zhuǎn)可以確定6個(gè)姿態(tài)，如圖6所示。

考慮到式(1)，零件姿態(tài)個(gè)數(shù)AN為：

AN=4RN(RN2-RN+1)。

(2)

三向姿態(tài)[9]下，零件繞x、y、z軸旋轉(zhuǎn)RN個(gè)角度。當(dāng)RN=3時(shí)，三向姿態(tài)只具備9個(gè)姿態(tài),如圖7所示。

“全姿態(tài)”下，零件在14個(gè)方向上共有84個(gè)姿態(tài)(如圖8)。理論上，只要RN足夠大，“全姿態(tài)”可以充分考慮零件姿態(tài)的各種可能，從而令構(gòu)造算法更有可能在容器空間找到更為優(yōu)化的姿態(tài)。

2 算法描述

零件在容器內(nèi)的運(yùn)動(dòng)遵循“最小勢(shì)能原理”：零件總是試圖通過平移和旋轉(zhuǎn)降低其重心高度，從而得到更加緊密的排列[9]。本文在HAPE3D基礎(chǔ)上利用混合表達(dá)圖形(Hybrid Representation Graphics, HRG)提出了一種改進(jìn)三維排樣構(gòu)造算法(HAPE3D_HRG)，算法流程如下：

(1)為所有零件指定某種排樣次序(比如按照零件體積大小排序)。

(2)多個(gè)排樣塊PB完全充滿容器(PB邊長(zhǎng)為BSL)，令所有排樣塊處于“空置”狀態(tài)。

(3)按照既定排樣次序選擇某個(gè)零件作為當(dāng)前待排零件。

(4)確定當(dāng)前零件AN個(gè)姿態(tài)：Attitude[i] (i=0,1,…,AN-1)。

(5)某個(gè)姿態(tài)下，當(dāng)前零件分解為多個(gè)微粒(微粒邊長(zhǎng)PSL=BSL)，任選一個(gè)作為參考微粒RP。

(6)零件訪問BN個(gè)排樣塊PB[j](j=0,1,…,BN-1)，即零件平移直至RP與PB[j]重合。

(7)找到最優(yōu)可行排樣姿態(tài)(在此姿態(tài)下，零件重心高度最低，且零件微粒與排樣塊不沖突)。

(8)因?yàn)榱慵腿萜鞣謩e被微粒和排樣塊“離散”，當(dāng)前零件有可能與“已排”零件之間存在空隙(如圖2b)，可用 “靠接”法[9](如圖3)消除之(靠接之前零件恢復(fù)為“矢量化”表達(dá))。

(9)與當(dāng)前零件沖突的排樣塊置為“被占據(jù)”。

(10)如果還有待排零件,則返回步驟(3)。當(dāng)所有零件完成步驟(3)～步驟(9)，則HAPE3D_HRG結(jié)束。

步驟(3)～步驟(9)為單個(gè)零件的排樣，具體實(shí)現(xiàn)如圖9所示。

在步驟(1)～步驟(4)之間，所有零件采用“矢量化”表達(dá);步驟(5)～步驟(7)之間， “待排”零件采用“像素化”表達(dá)(如圖9虛線右側(cè))，零件重疊檢測(cè)由過去復(fù)雜的幾何關(guān)系計(jì)算[9]轉(zhuǎn)化為零件微粒和排樣塊之間是否沖突的邏輯判斷，這正是算法速度提升的關(guān)鍵所在; 從步驟(8)開始，待排零件恢復(fù)為“矢量化”表達(dá)，以方便零件的靠接[9]，也保證了構(gòu)造算法在后期能夠輸出精確的排樣圖并計(jì)算排樣密度。

3 算例

為了對(duì)HAPE3D_HRG進(jìn)行算法驗(yàn)證和對(duì)比，本文編寫了程序(http://www.huagongchuanhai.cn/packing/)，進(jìn)行了兩組算例研究。算例1研究零件表達(dá)對(duì)于計(jì)算速度的影響，由于零件的旋轉(zhuǎn)方式也會(huì)影響算法速度，算例1限制了零件的旋轉(zhuǎn);算例2則用來測(cè)試HAPE3D_HRG的綜合表現(xiàn)，并與國(guó)外同類算法進(jìn)行比較。

3.1 算例1

文獻(xiàn)[7]中多面體算例有10種零件類型(如圖10)，每種零件的數(shù)目為n。令n從2～5取值，共進(jìn)行4組實(shí)驗(yàn)(零件不允許旋轉(zhuǎn))。表1中，零件總數(shù)N=10n：第1組n=2，零件總數(shù)N=20；第2組n=3,零件總數(shù)N=30，…，依此類推。文獻(xiàn)[9] (PC主頻3.1 GHz，排樣點(diǎn)距PPD=1.0 mm)使用HAPE3D基于矢量圖得到的排樣密度和時(shí)間分別列于表1第3、4列。本文(PC主頻3.0 GHz， BSL=1.0 mm)編程實(shí)現(xiàn)HAPE3D_HRG算法，進(jìn)行了同樣的實(shí)驗(yàn)(如圖11)，排樣密度和時(shí)間分別列于表1第5、6列。圖11中：l、w和h分別為容器的長(zhǎng)、寬和零件排樣高度(單位：mm); 排樣密度=所有零件體積/(l×w×h)。

表1 HAPE3D[9] (主頻3.10 GHz)與HAPE3D_HRG(主頻3.0 GHz)排樣密度和時(shí)間對(duì)比(零件不旋轉(zhuǎn))

如圖11所示，HAPE3D_HRG可處理不規(guī)則三維零件，并具備孔洞填充功能。如表1第3列、第5列所示， 在零件不允許旋轉(zhuǎn)的情況下,新老算法的排樣效果基本相當(dāng)，但后者的計(jì)算效率有了顯著的提升。如表1最后一列所示，HAPE3D_HRG對(duì)老算法的加速比最低為4.24，最高為10.64，平均加速比為8.43(已考慮PC主頻差異)。

3.2 算例2

為了進(jìn)一步測(cè)試HAPE3D_HRG的綜合性能，令零件全姿態(tài)旋轉(zhuǎn)(RN=4)，利用HAPE3D_HRG作為目標(biāo)函數(shù)(排樣密度)的求解器，以零件排樣次序?yàn)樵O(shè)計(jì)變量，以模擬退火算法SA為迭代優(yōu)化方法，最終得到的排樣圖如圖12所示。作為參照，同樣將HAPE3D與SA進(jìn)行搭配，得到排樣圖如圖13所示；另外還將Romanova等[3](主頻2.7 GHz)的排樣結(jié)果列于圖14中。3組對(duì)照實(shí)驗(yàn)的排樣密度和時(shí)間如表2所示。

表2 HAPE3D_HRG+SA(主頻3.0GHz)、HAPE3D+SA(主頻3.0GHz)、COMPOLY[3] (主頻2.7GHz)排樣密度和時(shí)間對(duì)比

由表2可得以下3點(diǎn)結(jié)論：

(1)在前3個(gè)算例的比較中，本文算法所得排樣密度最好。

(2)HAPE3D+SA的計(jì)算時(shí)間比本文算法要短很多，這是因?yàn)樵赗N=4的前提下，前者只考慮零件繞x,y,z三個(gè)坐標(biāo)軸的旋轉(zhuǎn)，即一共考慮4×3=12個(gè)姿態(tài)；而根據(jù)式(2)，本文算法在全姿態(tài)條件下，要考慮208個(gè)姿態(tài)。

(3)在排樣密度相當(dāng)?shù)那疤嵯?，本文算法的迭代時(shí)間比COMPOLY要短得多(已考慮PC主頻差異)。

4 結(jié)束語

本文提出一種改進(jìn)的三維不規(guī)則排樣構(gòu)造算法HAPE3D_HRG，并做了兩個(gè)方面的工作：

(1)在重疊檢測(cè)階段，零件由矢量表達(dá)變?yōu)橄袼乇磉_(dá)，從而將復(fù)雜的幾何算法轉(zhuǎn)為簡(jiǎn)單的布爾運(yùn)算。整體算法效率提升顯著。

(2)零件以“全姿態(tài)”旋轉(zhuǎn)，大大擴(kuò)展了零件姿態(tài)的尋優(yōu)空間。實(shí)驗(yàn)證明HAPE3D_HRG是一個(gè)性能優(yōu)良的構(gòu)造算法，將其作為目標(biāo)函數(shù)的“求解器”，可令優(yōu)化迭代在更短的時(shí)間內(nèi)搜索更大的可行空間，從而有可能得到更優(yōu)的排樣結(jié)果。

目前本文只將HAPE3D_HRG與模擬退火算法結(jié)合進(jìn)行了初步的研究，與別的優(yōu)化算法(遺傳算法、人工神經(jīng)網(wǎng)絡(luò)等)將會(huì)擦出怎樣的“火花”？這是未來值得研究的課題。此外，零件由矢量表達(dá)轉(zhuǎn)為像素表達(dá)后，像素越精細(xì)，排樣效果越好，但同時(shí)也會(huì)增加存儲(chǔ)和計(jì)算的負(fù)擔(dān)。如何在排樣效果、存儲(chǔ)空間以及計(jì)算效率之間進(jìn)行平衡，也需要在未來繼續(xù)展開研究。