劉虓 葉家瑋 胡金鵬

(華南理工大學(xué)土木與交通學(xué)院，廣東廣州510640)

排樣在造船、布匹和皮革加工業(yè)中有著廣泛應(yīng)用.排樣效率的微小提升可帶來(lái)巨大的經(jīng)濟(jì)效益，而排樣算法屬于組合優(yōu)化問(wèn)題，具有極高的計(jì)算復(fù)雜度，國(guó)內(nèi)外對(duì)此進(jìn)行了幾十年持續(xù)不斷的研究.大多數(shù)零件具有不規(guī)則的幾何外形，因此其排樣問(wèn)題具有重大的現(xiàn)實(shí)意義.

目前不規(guī)則零件排樣的求解策略主要基于兩點(diǎn):“靠左向下”原則(BL)和臨界多邊形(NFP).BL最初由Baker等［1］提出，由于其簡(jiǎn)便性和良好表現(xiàn)被廣泛采用，同時(shí)一些改進(jìn)算法也相繼出現(xiàn)［2］.由于BL會(huì)在母板上形成孔洞，造成浪費(fèi)，于是有學(xué)者提出“靠左向下并填充孔洞”求解策略(BLF)，其計(jì)算復(fù)雜度為 O(N3)(N 為零件數(shù)).Chazelle［3］則提出了一種改進(jìn)的 BLF算法，其算法復(fù)雜度為O(N2).

由Art［4］首次提出的NFP是一種功能強(qiáng)大的幾何工具，它與BL結(jié)合產(chǎn)生了各種排樣算法［5］.不少學(xué)者對(duì)NFP進(jìn)行了專(zhuān)門(mén)研究［6-7］.NFP的求解非常耗時(shí)，求解時(shí)間與零件數(shù)量N及零件的旋轉(zhuǎn)角個(gè)數(shù)(RN)成平方關(guān)系.以歐洲排樣研究組織(ESICUP)提供的標(biāo)準(zhǔn)問(wèn)題SWIM(N=10，RN=2)為例，Burke等［7］聲稱(chēng)每個(gè)NFP耗時(shí)1/66s，所有NFP計(jì)算時(shí)間為1/66×(10×2)2=6.08 s.但如果 RN=32，則計(jì)算時(shí)間將高達(dá)1/66×(10×32)2=1551.52s.

Burke等［8］在母材上布置一排垂線，零件沿線移動(dòng)尋找最優(yōu)旋轉(zhuǎn)角使零件“包圍盒”寬度最小.Dowsland等［9］指出:如將零件看作砂礫，母材看作玻璃瓶，不斷搖晃“玻璃瓶”可使“砂礫”排列更緊密.這說(shuō)明重力在排樣中起到了重要作用.Lee等［10］在母材上布置多個(gè)排樣點(diǎn)，在各點(diǎn)對(duì)零件進(jìn)行旋轉(zhuǎn)以找到最優(yōu)排樣姿態(tài)使零件形心坐標(biāo)x，y最小.該算法本質(zhì)上還是BL.

受Burke、Dowsland和Lee的啟發(fā)，運(yùn)用最小勢(shì)能原理對(duì)排樣問(wèn)題的物理意義進(jìn)行了解釋?zhuān)岢隽瞬灰?guī)則零件排樣新算法HAPE，該算法不需要計(jì)算NFP.

1 排樣問(wèn)題的最小勢(shì)能原理

結(jié)構(gòu)力學(xué)最小勢(shì)能原理:結(jié)構(gòu)體系在受力和變形過(guò)程中總是盡量使總勢(shì)能取得更小的值.

結(jié)構(gòu)體系總勢(shì)能Π表達(dá)形式如下

式中:Π為結(jié)構(gòu)體系總勢(shì)能;U為結(jié)構(gòu)體系變形勢(shì)能;V為結(jié)構(gòu)體系位置勢(shì)能.

排樣問(wèn)題中零件沒(méi)有彈性變形(U=0).另外V=Gyc(G、yc分別為零件重力和形心高度).故

下面給出排樣問(wèn)題最小勢(shì)能原理:零件在排樣過(guò)程中總是盡可能地通過(guò)平移或旋轉(zhuǎn)使其形心高度降低.

如圖1所示，假設(shè)零件由多邊形表達(dá)，含n個(gè)頂點(diǎn)和 n 條邊(lq，q=1，2，…，n)，其面積和形心坐標(biāo)可由格林公式導(dǎo)得:

令式(3)中的P=－y，Q=0，則零件面積為

式中:xq、yq為頂點(diǎn)q的坐標(biāo);當(dāng)q=n時(shí)，q+1=1.

由式(4)、(5)可得到零件形心高度坐標(biāo) yc，yc=Mx/A.

圖1 多邊形Fig.1 A polygon

如圖2所示，某零件在不同的姿態(tài)下的形心高度是不同的.姿態(tài)2對(duì)應(yīng)的形心最高，也最不穩(wěn)定，零件在這種姿態(tài)下極易翻轉(zhuǎn);姿態(tài)4對(duì)應(yīng)的形心高度最低，零件在這種姿態(tài)下是最穩(wěn)定的.

圖2 不同姿態(tài)下的形心高度Fig.2 Different height of center with different attitude yc1－yc4為零件在不同姿態(tài)1－4下的形心高度

如圖3(a)所示，4個(gè)矩形零件以“倒金字塔”方式置于母材底部.該排樣姿態(tài)很不穩(wěn)定，如受外界干擾，“倒金字塔”極易“傾覆”，如圖3(b)所示.各零件將散落在母材底部，如受到圖3(c)所示更“強(qiáng)烈”的外界干擾，零件將排列得更加緊密.

圖3 倒金字塔零件的排樣Fig.3 Layout of upside-down pyramid composed of shapes

2 定義

定義1 零件參考點(diǎn)(RP).

RP可以在任意位置選取.如圖4所示，零件的平移和旋轉(zhuǎn)均基于RP.

定義2 零件排樣姿態(tài)(Att).

如圖4所示，Att包含兩個(gè)要素:RP和旋轉(zhuǎn)角α.

圖4 參考點(diǎn)和排樣姿態(tài)Fig.4 Reference point and nesting attitude

使用C語(yǔ)言定義Att:

定義3 排樣點(diǎn)和排樣點(diǎn)間距(PPD).

如圖5所示，在母材上以一定的水平和垂直間距(PPD)布置的離散點(diǎn)被稱(chēng)為排樣點(diǎn).

圖5 排樣點(diǎn)和排樣姿態(tài)Fig.5 Nesting point and nesting attitude

定義4 可行排樣姿態(tài).

假設(shè)零件平移至某個(gè)排樣點(diǎn)(參考點(diǎn)和排樣點(diǎn)重合)，然后旋轉(zhuǎn)某一個(gè)角度.如在此排樣姿態(tài)下，該零件在母材內(nèi)部且與其它零件不重疊，則稱(chēng)其為“可行”排樣姿態(tài).

如圖4所示，零件旋轉(zhuǎn)角定義如下:

式中:j=0，1，…，RN －1.

在每個(gè)排樣點(diǎn)，零件有RN個(gè)排樣姿態(tài).如圖5所示，虛線排樣姿態(tài)為“不可行”排樣姿態(tài);實(shí)線的則為“可行”排樣姿態(tài).

3 基于最小勢(shì)能原理的排樣算法HAPE

HAPE的算法流程如圖6所示.

圖6 HAPE流程圖Fig.6 Flow chart of HAPE

流程圖中有幾個(gè)地方需要注意:

(a)PPN為排樣點(diǎn)個(gè)數(shù)，xi，yi為第i個(gè)排樣點(diǎn)的坐標(biāo)(i=1，2，…，PPN);

(b)算法流程圖中的零件旋轉(zhuǎn)，實(shí)際上是將圖1中的多邊形頂點(diǎn)基于參考點(diǎn)進(jìn)行旋轉(zhuǎn):

式中:xk，yk為零件頂點(diǎn) k的坐標(biāo)(k=1，2，…，n，n為零件頂點(diǎn)個(gè)數(shù));xr，yr為零件參考點(diǎn)坐標(biāo);

(c)Center_Y(part)表示計(jì)算零件part形心坐標(biāo)yc的函數(shù)，計(jì)算參考式(4)、(5).

4 算例

圖7 母板和零件Fig.7 Stock sheet and part

圖8 HAPE排樣圖Fig.8 Layout by HAPE

對(duì)4種不同形狀的船體零件(N=66)進(jìn)行排樣(圖7中交叉點(diǎn)為參考點(diǎn))，母材尺寸:5 000 mm×3050mm，PPD=100 mm，RN=8.零件1－4按照面積大小依次進(jìn)行排樣.在Visual C++6.0環(huán)境下編程，電腦處理器為2.66 GHz Celeron? CPU.如圖8(a)所示，HAPE可以處理凹多邊形零件以及具有鋸齒邊緣的零件，并可以利用孔洞進(jìn)行排樣.由于排樣點(diǎn)是離散的，母材上仍然留下了很多的縫隙，縫隙大小與PPD成正比.如圖8(b)所示，這種“天然”的縫隙可通過(guò)靠接算法消除之［11-12］，具體算法見(jiàn)參考文獻(xiàn)［12］.如圖9(a)所示，零件1、2之間以及零件1與母材底部之間存在空隙.如圖9(b)所示，零件1通過(guò)垂向靠接消除了與母材底部之間的空隙;如圖9(c)所示，零件2通過(guò)水平靠接消除了與零件1之間的空隙.

圖9 通過(guò)垂向和水平移動(dòng)消除空隙Fig.9 Elimination of gaps by vertical/horizontal moving

如果將PPD減至25 mm，排樣效果如圖10所示.使用軟件Nestlib排樣效果如圖11所示.可以發(fā)現(xiàn)HAPE已經(jīng)接近商業(yè)排樣軟件水平.

圖10 HAPE排樣圖Fig.10 Layout by HAPE

圖11 Nestlib排樣圖Fig.11 Layout by Nestlib

5 結(jié)論

綜上所述，HAPE具有如下特點(diǎn):(1)物理意義明確，算法簡(jiǎn)便，排樣效果接近商業(yè)軟件水平;(2)不需要計(jì)算NFP;(3)可以處理不規(guī)則零件，并利用孔洞進(jìn)行排樣;(4)HAPE的計(jì)算時(shí)間與排樣點(diǎn)密度(1/PPD2)成正比，在計(jì)算速度上雖然與商業(yè)軟件存在較大差距，但絕對(duì)的計(jì)算時(shí)間尚在可接受范圍內(nèi).

需要特別指出的是:除了不需要計(jì)算 NFP，HAPE也不需要考慮“盡量向左”的準(zhǔn)則.這兩點(diǎn)正是HAPE與普通BL算法的最大區(qū)別.

［1］Baker B S，Coffman J E G，Rivest R L.Orthogonal packings in two dimensions［J］.SIAM Journal on Computing，1980，9(4):846-855.

［2］Liu De-quan，Teng Hong-fei.An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles［J］.European Journal of Operational Research，1999，112(2):413-420.

［3］Chazelle B.The bottom-left bin-packing heuristic:an efficient implementation ［J］.IEEE Transactions on Computers，1983，C32(8):697-707.

［4］Art R C.An approach to the two-dimensional irregular cutting stock problem ［R］.Cambridge:IBM Cambridge Centre，1966.

［5］Dowsland K A，Vaid S，Dowsland W B.An algorithm for polygon placement using a bottom-left strategy［J］.European Journal of Operational Research，2002，141(2):371-381.

［6］Bennell J A，Dowsland K A，Dowsland W B.The irregular cutting-stock problem—a new procedure for deriving the no-fit polygon［J］.Computers ＆ Operations Research，2001，28(3):271-287.

［7］Burke E K，Hellier R S R，Kendall G，et al.Complete and robust no-fit polygon generation for the irregular stock cutting problem ［J］.European Journal of Operational Research，2007，179(1):27-49.

［8］Burke Edmund，Robert Hellier，Graham Kendall，et al.A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem ［J］.Operations Research，2006，54(3):587-601.

［9］Dowsland K A，Dowsland W B，Bennell J A.Jostling for position:local improvement for irregular cutting patterns［J］.The Journal of the Operational Research Society，1998，49(6):647-658.

［10］Lee Wenchen，Ma Heng，Cheng Borwen.A heuristic for nesting problems of irregular shapes［J］.Computer-Aided Design，2008，40(5):625-633.

［11］宋亞男，葉家瑋，鄧飛其，等.不規(guī)則圖形排樣系統(tǒng)中靠接算法比較研究［J］.計(jì)算機(jī)工程，2004，30(19):8-10.Song Ya-nan，Ye Jia-wei，Deng Fei-qi，et al.Analysis and comparison of collision algorithm in packing(nesting)［J］.Computer Engineering，2004，30(19):8-10.

［12］劉虓，葉家瑋.基于多邊形重疊檢測(cè)的沖裁件優(yōu)化排樣［J］.鍛壓技術(shù)，2010，35(5):155-158.Liu Xiao，Ye Jia-wei.Optimal stamping blank layout based on algorithm of polygon intersection detecting［J］.Forging ＆ Stamping Technology，2010，35(5):155-158.