1、基于重心N FP 的二維不規(guī)則形狀排樣算法劉胡瑤何援軍上海交通大學(xué),上海,200030摘要:提出了一種基于重心N FP 的二維不規(guī)則多邊形排樣算法,算法主要包括臨界多邊形計(jì)算和排樣定位選優(yōu)等內(nèi)容。該算法以多邊形來(lái)表示板材和待排零件,通過(guò)求解臨界多邊形N FP 來(lái)得到多邊形之間的所有靠接(排放位置。為了在N FP 中進(jìn)一步得到優(yōu)化的靠接位置,在N FP 的基礎(chǔ)上提出了重心N FP 的概念,通過(guò)選擇重心N FP 中的最低重心位置來(lái)確定零件的排放位置。在零件的排樣次序算法上,提出了順序遞歸排樣算法和遺傳算法,以降低排樣過(guò)程中形成的空腔所造成的浪費(fèi)。該算法可處理板材和零件均為不規(guī)則形狀的排樣問(wèn)題,允許

2、零件在全角度范圍內(nèi)進(jìn)行旋轉(zhuǎn),并可處理板材內(nèi)部帶孔洞或者邊界形成空腔等特殊情況。關(guān)鍵詞:不規(guī)則排樣;臨界多邊形;重心N FP ;遞歸排樣;遺傳算法中圖分類(lèi)號(hào):TP391文章編號(hào):1004132X (2007060723042D Irregular N esting Algorithm B ased on G ravity Center NFPLiu Huyao He YuanjunShanghai Jiaotong U niversity ,Shanghai ,200030Abstract :This paper p roposed 2D irregular shaped nesting alg

3、orit hm based on gravity center N FP.The p roblems of polygons touching detection and optimum nesting position selection were re 2solved here in.All container region and pieces were rep resented as polygons ,and t he touching posi 2tions can be found by calculation of N FP.In order to get t he optim

4、al nesting position ,t his paper pro 2posed t he co ncept of gravity center N FP.The lowest vertex o n gravity center N FP was selected to nest t he pieces.For t he p roblem of calculation nesting sequence ,t his paper presented a recursive nest 2ing algorit hm and a genetic algorit hm to reduce t h

5、e wasted area.The proposed algorit hm can deal wit h irregular shaped pieces and container ,it can also deal wit h arbit rary rotation of part s and holes on con 2tainer region.K ey w ords :irregular nesting ;no fit polygon (N FP ;gravity center N FP ;recursive nesting ;genetic algorit hm收稿日期:200512

6、12基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(605731460引言二維不規(guī)則形狀排樣問(wèn)題是一個(gè)平面布局優(yōu)化問(wèn)題,即在平面板材上布置多個(gè)不規(guī)則形狀的零件,并滿(mǎn)足以下約束條件:零件排放在板材內(nèi)部;各零件之間互不重疊;同時(shí)滿(mǎn)足一定的工藝要求。其優(yōu)化目標(biāo)是,尋求一個(gè)零件布局方案,使得浪費(fèi)的板材面積為最小,亦即材料的利用率為最大。排樣問(wèn)題對(duì)造船、服裝、模具等材料加工行業(yè)有重要意義,材料利用率的提高可直接降低材料浪費(fèi),提高經(jīng)濟(jì)效益,也符合當(dāng)今創(chuàng)建節(jié)約型社會(huì)的需求。與矩形排樣相比,不規(guī)則排樣增加了排樣角度和排樣位置的任意性,且板材和零件均有可能為任意多邊形,板材還可能包含內(nèi)部孔洞,所以不規(guī)則排樣問(wèn)題在幾何計(jì)算方

7、面具有較高的復(fù)雜度。與二維矩形排樣相比,不規(guī)則排樣具有以下特點(diǎn):板材和零件形狀上的任意性。該特點(diǎn)涉及對(duì)多邊形圖形處理的多種算法,如多邊形靠接算法(臨界多邊形N FP 、多邊形布爾運(yùn)算、外包多邊形求解等。零件放置規(guī)則的任意性。在滿(mǎn)足約束條件的情況下,零件可以任意角度在任意位置擺放,矩形排樣的最低最左原則或最低水平線(xiàn)原則在不規(guī)則排樣的情況下已不能滿(mǎn)足需要,最低最左等傳統(tǒng)放置方法將導(dǎo)致較大的空白區(qū)域無(wú)法利用。上述特點(diǎn)增加了不規(guī)則排樣問(wèn)題的復(fù)雜度,尤其是任意角度和位置的排放使得搜索空間變得非常龐大,對(duì)于實(shí)際排樣問(wèn)題,已不可能找到一種可實(shí)用的精確排樣算法。因此研究人員提出了多種啟發(fā)式或內(nèi)啟發(fā)式算法來(lái)求得

8、近似解。文獻(xiàn)1,2詳細(xì)闡述了二維不規(guī)則排樣問(wèn)題的研究現(xiàn)狀,指出臨界多邊形算法和遺傳算法將對(duì)不規(guī)則排樣的研究有重要影響。Fujita 等3提出了一種基于排樣順序的遺傳算法和局部?jī)?yōu)化相結(jié)合的排327基于重心N FP 的二維不規(guī)則形狀排樣算法劉胡瑤何援軍樣算法,但是該算法只能處理凸多邊形。J a 2kobs 4提出了一種典型的不規(guī)則排樣算法,即首先找到多邊形的最小外包矩形,然后用基于遺傳算法的矩形排樣方法進(jìn)行排樣,最后對(duì)排樣結(jié)果進(jìn)行“擠壓”運(yùn)算來(lái)得到最終排樣結(jié)果,Hopper 等1指出該方法無(wú)法保證“擠壓”算法的有效性。文獻(xiàn)5,6也提出了一些基于遺傳算法的不規(guī)則排樣算法,但其排樣質(zhì)量和排樣速度還無(wú)法

9、滿(mǎn)足實(shí)際需要。此外,根據(jù)圖形表示的方法來(lái)區(qū)分,還存在另一類(lèi)基于圖像像素的圖形表示和排樣方法7,這種算法的優(yōu)點(diǎn)是算法簡(jiǎn)單且適用面廣,但該算法存在以下兩個(gè)主要問(wèn)題:算法的精度受像素劃分的分辨率限制;算法復(fù)雜度與圖形分辨率的平方O (n 2成正比,當(dāng)精度要求較高或圖形大小相差較大時(shí),過(guò)高的時(shí)間復(fù)雜度限制了該算法的應(yīng)用。從目前的發(fā)展現(xiàn)狀來(lái)看,現(xiàn)有不規(guī)則排樣算法的排樣質(zhì)量和速度還有待于進(jìn)一步提高,因此,本文從不規(guī)則排樣的三個(gè)主要關(guān)鍵技術(shù)(臨界多邊形算法、零件放置規(guī)則及排樣順序出發(fā),首先闡述了臨界多邊形N FP 算法,然后提出了基于N FP 的重心N FP 零件放置規(guī)則,最后提出了遞歸形式的排樣算法以及基

10、于次序的遺傳算法,并提供了算法實(shí)驗(yàn)數(shù)據(jù)。1臨界多邊形算法在不規(guī)則排樣過(guò)程中,臨界多邊形(no fit polygon ,N FP 已被公認(rèn)為是二維不規(guī)則排樣問(wèn)題的基礎(chǔ)性幾何計(jì)算工具。N FP 的意義在于它給出了兩個(gè)多邊形之間所有相互接觸的靠接位置,求出所有可能的靠接位置后,排樣過(guò)程就成為了在靠接位置集合中尋求零件排放位置的優(yōu)化定位過(guò)程。臨界多邊形的定義如下:給定板材和零件的多邊形,先將板材多邊形固定,然后用零件多邊形做不旋轉(zhuǎn)的剛體運(yùn)動(dòng)繞板材多邊形內(nèi)部環(huán)形運(yùn)動(dòng)一周,運(yùn)動(dòng)過(guò)程中零件保持在板材內(nèi)部并和板材內(nèi)邊界接觸,則零件上的某個(gè)參考點(diǎn)(可取為最低點(diǎn)在運(yùn)動(dòng)過(guò)程中所形成的軌跡就構(gòu)成了零件相對(duì)于板材的臨

11、界多邊形(圖1。由于臨界多邊形給出了所有靠接位置的信息,因此在求取臨界多邊形之后,不規(guī)則排樣問(wèn)題就可以簡(jiǎn)化為基于臨界多邊形的定位選優(yōu)過(guò)程?，F(xiàn)有臨界多邊形算法主要包括三種:移動(dòng)碰撞法8。移動(dòng)碰撞法通過(guò)不斷求取下一步的碰撞位置來(lái)得到臨界多邊形。 明可夫斯基矢量和法圖1臨界多邊形的形成過(guò)程示意圖(minkowski sum 9。該方法將N FP 表示為多邊形矢量邊之和。多邊形凸化分割法。該方法將多邊形劃分為若干個(gè)子凸多邊形,然后求得子凸多邊形的N FP 之和即為最終N FP 。2零件放置規(guī)則零件放置規(guī)則的含義是指按照一定原則將待排零件排布到板材上,例如在二維矩形排樣中,可以按照最低最左原則將待排零件

12、放置到板材的空白處,即將零件不停地往下和往左移動(dòng),直到碰到板材邊界或已排零件的邊界而無(wú)法再移動(dòng)為止。對(duì)于不規(guī)則形狀排樣問(wèn)題,由于幾何形狀的特殊性,需要尋找一種更合適的零件排樣規(guī)則。已有研究人員提出了不規(guī)則排樣的零件放置規(guī)則,例如最小外包凸多邊形面積原則10、邊界重合度原則等,但仍存在復(fù)雜度過(guò)高和排樣質(zhì)量較低等問(wèn)題,因此需要研究更合適的放置規(guī)則。由于N FP 給出了多邊形之間所有靠接位置,因此在求得N FP 之后,零件排樣問(wèn)題就轉(zhuǎn)化為在N FP 上尋找一個(gè)合適排布位置的問(wèn)題,如圖2所示 。圖2根據(jù)NFP 確定靠接位置的示意圖在大部分不規(guī)則排樣過(guò)程中,往往將已排零件的總高度作為排樣質(zhì)量的標(biāo)準(zhǔn),零件

13、占用的總高度越低,說(shuō)明排樣的效果越好。從這個(gè)評(píng)價(jià)指標(biāo)出發(fā),本文提出了最低重心N FP 原則的排樣規(guī)則,該排樣規(guī)則將零件放置到具有最低重心的位置。最低重心N FP 排樣規(guī)則的出發(fā)點(diǎn)是在不發(fā)427中國(guó)機(jī)械工程第18卷第6期2007年3月下半月生多邊形干涉的情況下,將排樣零件的重心盡量定位于底部,并使得排樣后的邊界盡量保持水平,以助于后面的排樣。為了得到零件可排放的最低重心位置,首先需要計(jì)算出零件的重心(正負(fù)三角形分割法,然后以重心為參考點(diǎn)求解N FP ,即可得到重心N FP ,通過(guò)重心N FP 可得到最低重心位置。由于N FP 的形狀會(huì)隨著零件的旋轉(zhuǎn)角度而變化,為了得到在不同旋轉(zhuǎn)角度下的最低重心位

14、置,可以通過(guò)角度搜索來(lái)得到旋轉(zhuǎn)情況下的最低重心位置。得到最低重心位置和對(duì)應(yīng)的旋轉(zhuǎn)角度之后,即可確定零件的排樣位置,如圖3所示 。圖3根據(jù)重心NFP 的最低點(diǎn)確定零件排樣位置的示意圖為了較快查找到最低重心位置,可以先旋轉(zhuǎn)較大的角度間隔,例如先以10°為旋轉(zhuǎn)間隔,得到360/10=36個(gè)重心N FP ,并從中得到一個(gè)具有最低重心位置的旋轉(zhuǎn)角度,然后在該旋轉(zhuǎn)角度的附近范圍內(nèi)進(jìn)一步細(xì)化,以得到更精確的最低重心位置以及對(duì)應(yīng)的旋轉(zhuǎn)角度。3確定零件的排樣順序通過(guò)多角度重心N FP ,可以得到單個(gè)零件的最低排布重心位置和相應(yīng)角度,從而可以確定零件的排樣位置。然而對(duì)于多個(gè)零件來(lái)說(shuō),排樣順序是決定最終排

15、樣質(zhì)量的另外一個(gè)主要影響因素,因此需要研究合適的排樣順序算法。常用的排樣順序算法包括啟發(fā)式算法和內(nèi)啟發(fā)式算法。啟發(fā)式算法通常是根據(jù)當(dāng)前排樣條件和先驗(yàn)知識(shí)來(lái)決定下一個(gè)排樣零件的序號(hào),例如選擇排樣后凸包面積最小的零件為下一個(gè)排樣零件,啟發(fā)式算法速度較快,但是排樣質(zhì)量受先驗(yàn)知識(shí)和排樣規(guī)則的影響很大,適用于計(jì)算時(shí)間短而對(duì)排樣質(zhì)量要求一般的情況。而內(nèi)啟發(fā)式算法包括遺傳算法、模擬退火算法、禁忌搜索算法以及蟻群算法等,該類(lèi)算法可以在給定初始條件的情況下自動(dòng)搜索到較優(yōu)解,內(nèi)啟發(fā)式算法收斂速度較慢,但容易搜索到較優(yōu)解和最優(yōu)解,適用于對(duì)計(jì)算時(shí)間要求不高而對(duì)排樣結(jié)果要求較高的場(chǎng)合。3.1利用遞歸算法求解排樣次序本文

16、從減小排樣孔洞面積出發(fā),提出了一種遞歸式的排樣順序算法,該算法結(jié)合了遞歸算法和啟發(fā)式算法的特點(diǎn),總體上采用啟發(fā)式算法,而在局部范圍內(nèi)應(yīng)用遞歸排樣,具有啟發(fā)式算法速度快的優(yōu)點(diǎn),同時(shí)可得到較好的排樣效果。該算法的原理是:首先根據(jù)零件面積從大到小排序決定初始的排樣順序,然后在排樣過(guò)程中,如果發(fā)現(xiàn)當(dāng)前排樣零件排樣后形成了較大的孔洞面積,且該面積足以容納其他較小的零件,則在此情況下調(diào)整排樣順序,將其他能放入該孔洞的較小零件調(diào)整到當(dāng)前零件之前進(jìn)行排樣,以減小排樣過(guò)程中所形成排樣孔洞面積,該算法的示意圖如圖4所示。首先根據(jù)面積從大到小的次序進(jìn)行排樣,當(dāng)排完零件1后,發(fā)現(xiàn)形成了較大空腔面積,且該空腔面積足以容

17、納其他較小的零件,首先可容納的是零件2,因此將零件2的排放次序移到零件1之前,從而排樣順序從321變?yōu)?31。同理,按照新的排樣次序231繼續(xù)排樣,發(fā)現(xiàn)零件2排放后形成的空腔仍可排放零件1,因此將零件1的排放次序移動(dòng)到零件2之前。最終排放次序變?yōu)?23。按該次序排放,可以盡量減少排放后形成的空腔所浪費(fèi)的面積 。圖4遞歸排樣順序算法示意圖3.2利用遺傳算法求解排樣次序第一代種群對(duì)遺傳算法的最終結(jié)果有較大影527基于重心N FP 的二維不規(guī)則形狀排樣算法劉胡瑤何援軍f =f +式中,f 為初始適應(yīng)度;f 為變換后的適應(yīng)度。同時(shí)有=f avgf avg -f min =-f min f avgf a

18、vg -f min=f avgK式中,K 為常數(shù);f avg 為平均適應(yīng)度;f min 為最小適應(yīng)度。該遺傳算法采用了輪盤(pán)賭比例選擇方法來(lái)選取父?jìng)€(gè)體進(jìn)行交叉產(chǎn)生下一代,比例選擇方法可能會(huì)導(dǎo)致某些含有較好基因但是適應(yīng)度較低的個(gè)體被過(guò)早丟棄,因此在上式中增加來(lái)對(duì)適應(yīng)度進(jìn)行調(diào)節(jié),以避免個(gè)體的過(guò)早淘汰。本文采用OX (order -crossover 順序交叉算子。將2個(gè)父?jìng)€(gè)體的某些染色體進(jìn)行交叉,最終得新一代個(gè)體產(chǎn)生之后,根據(jù)變異概率選擇一定量的個(gè)體進(jìn)行變異操作。本文隨機(jī)選擇某個(gè)序號(hào)插入到其他位置來(lái)實(shí)現(xiàn)變異操作。變異概率可取為011012。染色體中的某2段序號(hào)(而不是2個(gè)單獨(dú)序號(hào)也可以進(jìn)行交換,但在

19、此情況下由于變異較大,因此變異概率要相應(yīng)降低。4算法實(shí)驗(yàn)結(jié)果4.1測(cè)試數(shù)據(jù)1此測(cè)試樣例來(lái)自于文獻(xiàn)4,首先將多邊形擬合為矩形,然后利用基于順序遺傳算法的矩形排樣算法進(jìn)行排樣,最后用最低最左原則的“擠壓”算法對(duì)排樣后的零件進(jìn)行進(jìn)一步擠壓。本文采用了相同測(cè)試樣例,并用本文算法進(jìn)行了計(jì)算,和文獻(xiàn)4算法的結(jié)果進(jìn)行了比較(計(jì)算機(jī)硬件配置:P4115G ,640M 內(nèi)存,如表1所示 。4.2測(cè)試數(shù)據(jù)2該測(cè)試樣例數(shù)據(jù)來(lái)自于ESICU P (EU RO special interest group on cutting and packing ,現(xiàn)有文獻(xiàn)中未發(fā)現(xiàn)有相同樣例的排樣結(jié)果。為了測(cè)試不規(guī)則板材以及板材內(nèi)

20、部帶孔洞的情況,本文在測(cè)試樣例中將板材設(shè)置為不規(guī)則形狀并加入了不規(guī)則多邊形孔洞,如圖5所示。5結(jié)論針對(duì)目前二維不規(guī)則形狀排樣中的N FP 計(jì)算、零件放置規(guī)則及排樣順序問(wèn)題,本文分別提出了對(duì)應(yīng)的解決方案:首先給出了N FP 在排樣問(wèn)題中的定義,并綜合闡述了N FP 的計(jì)算方法;其次,提出了基于重心N FP 的最低重心零件放置原則,使零件在排放時(shí)達(dá)到當(dāng)前最低重心位置, 并為后圖5板材帶孔洞的排樣結(jié)果(排樣高度為55.06mm ,板材利用率為81.4%,計(jì)算時(shí)間為93.9s 續(xù)零件的排放形成一個(gè)較為平滑的邊界。第三,在排樣順序算法上,提出了遞歸排樣順序算法和遺傳算法,遞歸算法在排樣過(guò)程中發(fā)現(xiàn)較大面積

21、浪費(fèi)時(shí),可及時(shí)調(diào)整排樣順序,以提高材料利用率?？傮w來(lái)看,本文算法適用于二維不規(guī)則形狀(下轉(zhuǎn)第731頁(yè)627中國(guó)機(jī)械工程第18卷第6期2007年3月下半月6.4篩選率8k=2|A(k|=66,篩選率P=5617%。7結(jié)論本文系統(tǒng)研究了基于拆卸圖模型的拆卸過(guò)程規(guī)劃中的可拆卸性篩子。用多色集理論的可能位移模型描繪零件拆卸過(guò)程中的干涉阻擋關(guān)系,用可能位移方程組作為可拆卸性篩子,有效篩選掉不合理零件單元,使圖模型獲得較大的精簡(jiǎn),為最終獲得準(zhǔn)確和完備的拆卸圖模型做出了一定的貢獻(xiàn)。將子拆卸單元用遞階結(jié)構(gòu)圖的形式表示,這種表示方式簡(jiǎn)潔、直觀。用多色集理論的可能位移方程組作為可拆卸性篩子,具有形式化水平高、算法

22、簡(jiǎn)單、易于編程等方面的優(yōu)點(diǎn)。參考文獻(xiàn):1李劍鋒,陳建,李方義,等.機(jī)電產(chǎn)品拆卸回收模型及其拆卸序列生成J.山東大學(xué)學(xué)報(bào)(工學(xué)版,2004,34(5:913.2郭茂,蔡建國(guó),童勁松.基于Petri網(wǎng)的產(chǎn)品拆卸模型研究J.中國(guó)機(jī)械工程,2000,11(9:10071009.3李宗斌.先進(jìn)制造中多色集合理論的研究及應(yīng)用M.北京:中國(guó)水利水電出版社,2005.4Pavlov V V,李宗斌,戴文娣,等.基于多色集合的產(chǎn)品裝配序列仿真J.西安交通大學(xué)學(xué)報(bào),2001,35(11:12081210.5Pavlov V V.Theoretical Base of Assembly for Air2plane

23、and WhirlybirdM.Moscow:MA I Press,1993.6高建剛,向東,陳海,等.拆卸與或圖模型中的連通性篩子J.清華大學(xué)學(xué)報(bào),2003,43(8:10461048. 7張博,張洪濤,趙珊珊,等.基于多色集合理論的產(chǎn)品裝配規(guī)劃建模及算法研究J.西安交通大學(xué)學(xué)報(bào),2005,39(11:12541258.8高建剛,段廣洪,汪勁松.面向回收設(shè)計(jì)拆卸與或圖方法的研究J.計(jì)算機(jī)集成制造系統(tǒng)-CIMS,2002,8(7:575579.(編輯馬堯發(fā)作者簡(jiǎn)介:閆利軍,男,1980年生。西安交通大學(xué)機(jī)械制造系統(tǒng)工程國(guó)家重點(diǎn)實(shí)驗(yàn)室博士研究生。研究方向?yàn)楫a(chǎn)品信息建模、仿真和優(yōu)化。發(fā)表論文5篇。

24、李宗斌,男,1946年生。西安交通大學(xué)機(jī)械制造系統(tǒng)工程國(guó)家重點(diǎn)實(shí)驗(yàn)室教授、博士研究生導(dǎo)師。趙姍姍,女,1979年生。西安交通大學(xué)機(jī)械制造系統(tǒng)工程國(guó)家重點(diǎn)實(shí)驗(yàn)室博士研究生。(上接第726頁(yè)的排樣問(wèn)題,允許零件在全角度范圍內(nèi)進(jìn)行旋轉(zhuǎn),并可統(tǒng)一處理內(nèi)部帶孔洞或者邊界形成空腔等特殊情況。實(shí)驗(yàn)結(jié)果表明本文不規(guī)則排樣算法的材料利用率普遍可達(dá)80%以上,顯示出良好的應(yīng)用前景。參考文獻(xiàn):1Hopper E,Turton H.A Review of the Applicationof Meta-heuristic Algorithms to2D Strip PackingProblemsJ.Artificial

25、 Intelligence Review,2001,16:257300.2Kathryn A D,William B D.Solution Approaches toIrregular Nesting ProblemsJ.European Journal ofOperational Research,1995,84:506521.3Fujita K,Akagji S,K irokawa N.Hybrid Approachfor Optimal Nesting using A G enetic Algorithm andA Local Minimization AlgorithmC/In Proceed2ings of the19th Annual ASM E Design AutomationConference.Albuquerque,NM,USA,1993:477484.4J akobs S.On Genetic Algorithms for the Packing ofPolygonsJ.European Journal of Operational Re2search,1996,88:165181.5Fischer A D,Dagli