基于臨界多邊形的不規(guī)則件啟發(fā)式排樣算法

湯德佑　周子琳

摘要：

為提高不規(guī)則件啟發(fā)式排樣的材料利用率，提出一種基于重心臨界多邊形和邊適應(yīng)度的不規(guī)則件啟發(fā)式排樣算法GEFHNA。首先，定義了邊適應(yīng)度以衡量排樣過(guò)程中原材料與不規(guī)則件間貼合程度，在此基礎(chǔ)上給出了將邊適應(yīng)度與重心NFP（GNFP）相結(jié)合的排放策略以減少排樣過(guò)程中可能產(chǎn)生的空隙面積；其次，給出了基于WeilerAtherton多邊形裁剪算法的剩余原材料求解方法，重用排樣過(guò)程中產(chǎn)生的孔洞，減少孔洞面積；最后，給出了基于上述排樣策略和材料重用策略的啟發(fā)式排樣算法GEFHNA，給出了與智能算法和同類軟件的實(shí)驗(yàn)比較。對(duì)歐洲排樣問(wèn)題興趣小組提供的基準(zhǔn)測(cè)試用例的實(shí)驗(yàn)結(jié)果表明，GEFHNA的耗時(shí)約為基于智能算法的排樣方法的千分之一，同時(shí)在與兩款商業(yè)軟件NestLib和SigmaNest的11個(gè)基準(zhǔn)測(cè)試的對(duì)比中，GEFHNA獲得了7 / 11個(gè)相對(duì)最優(yōu)的排樣面積利用率。

關(guān)鍵詞：

二維不規(guī)則件；排樣；臨界多邊形；啟發(fā)式方法

中圖分類號(hào)：

TP301.6

文獻(xiàn)標(biāo)志碼：A

Abstract：

To raise the material utilization ratio of heuristic nesting for irregular shapes， a Gravity NoFitPolygon （NFP） and Edge Fitnessbased Heuristic Nesting Algorithm （GEFHNA） was proposed. Firstly， the definition of Edge Fitness （EF） to measure the fitness between the material and irregular shape produced in the process of packing was defined， and a packing strategy combining Gravity NFP （GNFP） with edge fitness was proposed to reduce the area of gap generated in packing. Secondly，a WeilerAthertonbased algorithm was presented to compute remained materials and add holes produced in each round of packing to the list of materials. The heuristic packing algorithm prefered the holes in next rounds of packing to reduce proportion of holes in released layout. Finally， a heuristic algorithm based on the previous packing strategy and reuse strategy was put forward and the comparison experiments of GEFHNA with intelligent algorithm and similar softwares were presented. Experimental results on the heuristic packing algorithm with benchmarks provided by ESICUP （EURO Special Interest Group on Cutting and Packing） show that GEFHNA only has about 1/1000 time consumption of intelligent algorithmbased nesting scheme and achieves 7/11 relatively optimal utilization rate in contrast with two commercial softwares NestLib and SigmaNest.

英文關(guān)鍵詞Key words：

twodimensional irregular； packing； NoFitPolygon （NFP）； heuristic method

0引言

排樣（Nesting/Packing/Stock Cutting Problem）是組合優(yōu)化過(guò)程，已被證明為NP（Nondeterministic Polynomial）完全問(wèn)題[1]。二維不規(guī)則件排樣需要旋轉(zhuǎn)樣件以找到最佳擺放位置，解空間巨大，求解復(fù)雜度高。啟發(fā)式排樣算法設(shè)定樣件選擇策略與排放策略的規(guī)則集合，根據(jù)規(guī)則完成樣件的排樣，速度快，是解決二維不規(guī)則件排樣問(wèn)題的常用方法。

啟發(fā)式排樣重點(diǎn)需要解決碰撞檢測(cè)、選件策略（樣件被排放的順序）和樣件排放策略（確定樣件的旋轉(zhuǎn)角度和排放位置）等問(wèn)題。零件選擇策略常采用First Fit（FF）、Best Fit（BF）和DJD（Djang and Finch heuristic）方法[2]。FF和BF應(yīng)用了貪心的思想，DJD則在排序的基礎(chǔ)上增加了組合小樣件以求最大化利用未排空間。排放策略中最常用的是BL（BottomLeft，BL）策略[3]，該策略采用“靠左靠下”的原則，在保證零件不重疊的情況下，向下向左移動(dòng)，直至不能再移動(dòng)為止，到達(dá)“BL穩(wěn)定位置”。BL算法在排樣過(guò)程中容易出現(xiàn)排樣結(jié)果左側(cè)偏高的現(xiàn)象，且排放過(guò)程中會(huì)產(chǎn)生一些面積較大的空白區(qū)域，常對(duì)其改進(jìn)再應(yīng)用[4]，如下臺(tái)階策略[5]、BLF（BottomLeft Filling）策略[6]等。CA（Constructive Approach）系列策略[7]根據(jù)當(dāng)前原材料上零件排放的位置情況，給定幾個(gè)排放位點(diǎn)，待排零件從給定位點(diǎn)中選擇最優(yōu)的一個(gè)位點(diǎn)進(jìn)行排放。

臨界多邊形（NoFitPolygon，NFP）[8]是研究不規(guī)則件排樣算法的重要分支，可用于碰撞檢測(cè)或確定排放位置。Dowsland等[9]給出了基于NFP的不規(guī)則件BL排樣算法，在排放當(dāng)前零件時(shí)，采用當(dāng)前零件相對(duì)于原材料中所有已排零件的NFP進(jìn)行“BL穩(wěn)定位置”的判斷和選擇?；谥匦腘FP的排放策略[10]以零件的重心作為生成NFP的參考點(diǎn)，對(duì)樣件的每一個(gè)旋轉(zhuǎn)角度生成一個(gè)內(nèi)部NFP，對(duì)比所有角度下生成的NFP的頂點(diǎn)，選擇其中的最低點(diǎn)進(jìn)行排放。

研究表明，對(duì)啟發(fā)式排樣，樣件形狀與原材料的特征吻合度直接影響排樣效果[2]。本文提出“邊適應(yīng)度（Edge Fitness，EF）”的概念來(lái)衡量排樣過(guò)程中不規(guī)則樣件與原材料的貼合程度，并結(jié)合重心NFP[10]的思想，提出了基于重心NFP與邊適應(yīng)度的排樣策略。給出了基于WeilerAtherton多邊形裁剪算法[11]的剩余原材料求解方法以減少原材料浪費(fèi)，將排樣中產(chǎn)生的孔洞加入原材料列表并在后續(xù)排樣中優(yōu)先使用。在此基礎(chǔ)上結(jié)合FFD選件算法，給出了一種基于重心NFP與邊適應(yīng)度的啟發(fā)式排樣算法GEFHNA（GravityNFP and Edge Fitnessbased Heuristic Nesting Algorithm）。測(cè)試表明，GEFHNA耗時(shí)是基于智能算法的排樣算法的千分之一，并在與商業(yè)軟件NestLib和SigmaNest的11個(gè)基準(zhǔn)測(cè)試對(duì)比中獲得了7/11個(gè)相對(duì)最優(yōu)的排樣面積利用率，排樣效果較好。

通過(guò)生成臨界多邊形，能夠根據(jù)參考點(diǎn)與臨界多邊形間的位置關(guān)系快速地對(duì)不規(guī)則零件進(jìn)行碰撞檢測(cè)：

1）當(dāng)B的參考點(diǎn)位于NFPAB上時(shí)，B和A剛好接觸；

2）當(dāng)B的參考點(diǎn)位于NFPAB內(nèi)部時(shí)，B和A重疊；

3）當(dāng)B的參考點(diǎn)位于NFPAB外部時(shí)，B和A分離。

臨界多邊形的碰撞檢測(cè)的時(shí)間復(fù)雜度為O（n），其中n為臨界多邊形的邊數(shù)，且給出了多邊形A和B之間的所有剛好接觸的位置集合。在此情況下，只需要對(duì)全部可能的接觸位置作出優(yōu)化選擇，即可確定零件合理的排放位置。

重心NFP[10]是將多邊形B的重心設(shè)為參考點(diǎn)，以此求得的多邊形B相對(duì)于多邊形A的NFP，記為GNFP。二維不規(guī)則樣件的重心位置是樣件的大部分面積所在的位置，可使評(píng)價(jià)函數(shù)對(duì)實(shí)際的排放效果反映更準(zhǔn)確，提高材料使用率。不規(guī)則樣件的重心可采用多邊形分割法求解。設(shè)不規(guī)則樣件p分解為n個(gè)子部分，則使用多邊形分割后樣件p的重心計(jì)算公式如下：

x=∑Aixi/∑Ai

y=∑Aiyi/∑Ai； 1≤i≤n（1）

其中：Ai為第i個(gè)子部分的面積，xi和yi分別為第i個(gè)子部分的重心的X坐標(biāo)與Y坐標(biāo)位置。對(duì)任意多邊形，面積可采用梯形法求解，在給定旋轉(zhuǎn)角度下的重心可以利用多邊形分割法及式（1）進(jìn)行求解。求得樣件p的重心后，將該重心設(shè)為樣件p的參考點(diǎn)并進(jìn)行NFP的求解，即可求得樣件p相對(duì)于給定多邊形在當(dāng)前旋轉(zhuǎn)角度oi下的GNFP，計(jì)算方法見文獻(xiàn)[10]。

2基于GNFP與邊適應(yīng)度的排放策略

給定待排原材料和樣件，排樣策略給出樣件的擺放位置及擺放角度，本節(jié)首先定義邊適應(yīng)度（Edge Fitness， EF）值及計(jì)算方法，最后給出基于GNFP和EF值的排放策略。

2.1邊適應(yīng)度

對(duì)二維排樣而言，最佳效果的排樣是排樣后零件間處于貼合狀態(tài)，零件間無(wú)孔洞，此時(shí)材料利用率將最高。因此，排樣中邊的貼合情況可作為啟發(fā)式排樣的重要規(guī)則。

定義EF值：給定邊集為E的不規(guī)則樣件p，輪廓邊集為e的原材料A，對(duì)任意Ei∈E，ej∈e，若排放后Ei和ej貼合，記貼合長(zhǎng)度為f（ej，Ei），稱p所有和原材料輪廓邊界重合的長(zhǎng)度之和為邊適應(yīng)度，簡(jiǎn)稱EF值，即：

EF（A，p）=∑1≤i≤m，1≤j≤nf（ej，Ei）（2）

EF值反映了樣件與原材料或已排樣件的貼合程度，EF值越大說(shuō)明邊貼合得越多，排樣密度更大。如圖2中，在零件重心Y坐標(biāo)值相同的情況下，圖2（b）擁有比圖2（a）更大的EF值，選擇圖2（b）排放可能產(chǎn)生更好的排樣效果。

計(jì)算邊適應(yīng)度需要將待排樣件p進(jìn)行“預(yù)排放”，即將樣件p擺放到按照GNFP求得的候選點(diǎn)，然后計(jì)算在候選點(diǎn)的EF值。在實(shí)際計(jì)算EF值時(shí)，樣件的邊與原材料的內(nèi)部輪廓邊均按順時(shí)針或逆時(shí)針存放，只需比較其中的部分邊對(duì)，計(jì)算時(shí)間為O（m+n）。

2.2排放策略

基于GNFP和邊適應(yīng)度的排放策略的主要思想是：對(duì)當(dāng)前待排樣件p，求出其在所有可旋轉(zhuǎn)角度oi（測(cè)試數(shù)據(jù)集包含了所有可能的旋轉(zhuǎn)角度）下的相對(duì)于原材料內(nèi)部輪廓邊界的內(nèi)部GNFP，記為GNFPi。對(duì)比所有GNFPi的左下點(diǎn)和右下點(diǎn)，篩選出最下最左點(diǎn)和最下最右點(diǎn)，記為BestBL和BestBR，設(shè)所對(duì)應(yīng)的旋轉(zhuǎn)角度為OBL和OBR。根據(jù)OBL和OBR以及位置點(diǎn)BestBL和BestBR，對(duì)樣件p進(jìn)行預(yù)排放并求出在這兩種排放狀態(tài)下的EF值，保留EF值最大的排放狀態(tài)作為樣件p排放時(shí)的旋轉(zhuǎn)角度和排放位置，完成對(duì)樣件p的排放。單個(gè)樣件的排放算法如下：

Algorithm PackingI（int indx， Panel * pPanel， Part * p）

//描述：根據(jù)樣件序號(hào)可查樣件類型、樣件類型對(duì)應(yīng)可旋轉(zhuǎn)數(shù)、在旋轉(zhuǎn)角度o下的樣件形狀，旋轉(zhuǎn)角度o按從小到大保存，為零表示未旋轉(zhuǎn)，本算法根據(jù)待排樣件序號(hào)在原材料上完成排樣，輸出排樣完畢后的樣件圖形數(shù)據(jù)。

//輸入：待排樣件序號(hào)indx，當(dāng)前原材料圖形數(shù)據(jù)pPanel；

//輸出：排放完畢后的樣件圖形數(shù)據(jù)p；若樣件能夠排放在pPanel返回1，否則-1。

1）初始化BestBL和BestBR為pPanel左上和右上點(diǎn)，取得p的類型、旋轉(zhuǎn)角度等數(shù)據(jù)，取一個(gè)旋轉(zhuǎn)角度下的圖形數(shù)據(jù)。

2）計(jì)算在當(dāng)前旋轉(zhuǎn)角度下樣件圖形相對(duì)于pPanel內(nèi)部輪廓邊界的GNFP，若成功計(jì)算則轉(zhuǎn)3）；否則取下一個(gè)旋轉(zhuǎn)角度下的圖形，繼續(xù)2）；若所有角度均已計(jì)算則轉(zhuǎn)5）。

3）判定當(dāng)前計(jì)算出的GNFP的左下點(diǎn)/右下點(diǎn)是否優(yōu)于已記錄的BestBL和BestBR，若優(yōu)則更新BestBL和BestBR，并記錄對(duì)應(yīng)的旋轉(zhuǎn)角度。

4）取下一個(gè)旋轉(zhuǎn)角度，轉(zhuǎn)2）。

5）若BestBL和BestBR更新過(guò)，取出產(chǎn)生對(duì)應(yīng)點(diǎn)的旋轉(zhuǎn)角度和圖形數(shù)據(jù)，預(yù)排放到pPanel，分別計(jì)算其EF值；否則返回-1。

6）比較BestBL和BestBR處排放所產(chǎn)生的EF值，保留EF值較大的預(yù)排放，輸出p，返回1。

設(shè)兩多邊形分別有m和n條邊，樣件具有k個(gè)旋轉(zhuǎn)角度，步驟2）的執(zhí)行時(shí)間為k*T（G），其中T（G）為計(jì)算GNFP的時(shí)間漸近復(fù)雜度，其下界為Ω（mn）；而計(jì)算EF值的時(shí)間復(fù)雜度為O（m+n），對(duì)算法性能影響小。

3啟發(fā)式排樣算法

3.1二維排樣問(wèn)題的歸一化

工業(yè)應(yīng)用中二維不規(guī)則件排樣問(wèn)題可分為二維裝箱排樣問(wèn)題（TwoDimensional Bin Packing Problem， 2DBPP）和二維條帶排樣問(wèn)題（TwoDimensional Strip Packing Problem， 2DSPP）。裝箱問(wèn)題中原材料的橫向?qū)挾群涂v向高度都是限定的，且原材料的數(shù)量可能大于1；條帶排樣問(wèn)題中，原材料的縱向高度是不限的，只限定橫向的寬度。為使原材料具備封閉形狀的特性，方便剩余原材料的求解，對(duì)二維條帶排樣，本文在排樣初始化階段對(duì)其初始原材料設(shè)定一個(gè)安全的初始高度H，使其具有封閉形狀。安全初始高度H的設(shè)定方法為：求出所有待排樣件的包絡(luò)矩形，對(duì)第i個(gè)樣件的包絡(luò)矩形，設(shè)其高為hi，寬為wi，則安全高度H為：

H=∑1≤i≤nmax（hi，wj）（3）

3.2剩余原材料的求解

應(yīng)用臨界多邊形完成二維不規(guī)則排樣時(shí)，在排放完一個(gè)待排樣件后，需求解出當(dāng)前剩余原材料的內(nèi)部邊界輪廓，以排放下一個(gè)樣件。目前，多數(shù)研究人員采用將已排多邊形的外部輪廓與原材料的內(nèi)部輪廓邊界融合，形成剩余原材料的輪廓邊界的方式[12]，忽略了新排樣件與原材料輪廓之間的間隙，容易造成原材料的浪費(fèi)。

為提高材料利用率，本文基于WeilerAtherton多邊形裁剪算法實(shí)現(xiàn)了一個(gè)剩余原材料求解算法。待排原材料或剩余原材料以列表存儲(chǔ)，將排樣過(guò)程中新排樣件與原材料之間可能產(chǎn)生的空洞作為新的原材料加入到原材料列表中，并優(yōu)先使用這些原材料。算法將排樣過(guò)程中待排視作裁剪多邊形B，將當(dāng)前排入的原材料視作被裁剪多邊形A，且兩多邊形均為順時(shí)針?lè)较颍蠼獾玫降亩噙呅蜛不在多邊形B中的部分（外裁剪部分）即為排樣后產(chǎn)生的原材料列表。

剩余原材料的求解算法具體如下：

Algorithm WACompute（Part * p， Panel * pPanel）；

//描述：計(jì)算樣件p排樣后的剩余原材料，運(yùn)算過(guò)程中數(shù)組Q用于保存裁剪產(chǎn)生的孔洞。

//輸入：原材料pPanel和樣件p及對(duì)應(yīng)頂點(diǎn)數(shù)組aArray和bArray；

//輸出：排樣完后的原材料列表result。

1）將原材料pPanel與樣件p設(shè)為順時(shí)針?lè)较颉?/p>

2）求出兩多邊形的交點(diǎn)，更新aArray和bArray，同時(shí)將aArray中與原p重疊的點(diǎn)替換為bArray中的點(diǎn)。

3）順時(shí)針掃描aArray，若在交點(diǎn)處進(jìn)入B則標(biāo)記為“入”點(diǎn)，離開B則標(biāo)記為“出”點(diǎn)，更新aArray。

4）從aArray中任取一個(gè)“出”點(diǎn)，記為R，令S=R，并初始化點(diǎn)集Q為{S}。

5）順時(shí)針遍歷aArray數(shù)組，在遍歷過(guò)程中，若點(diǎn)未標(biāo)記，則存入結(jié)果數(shù)組Q中，重復(fù)5）；若點(diǎn)標(biāo)記為“入”，記為T，并轉(zhuǎn)6）。

6）找到T在bArray數(shù)組中的位置，開始逆時(shí)針遍歷bArray數(shù)組，設(shè)遍歷到的點(diǎn)為X，若X未標(biāo)記，則加入Q，重復(fù)6）；若X=S，轉(zhuǎn)7）。

7）停止遍歷數(shù)組bArray，結(jié)果數(shù)組Q中的點(diǎn)即組成一個(gè)外裁剪多邊形區(qū)域，計(jì)算點(diǎn)集構(gòu)成的多邊形cShape，將其加入到result。

8）令S=T在aArray中的后繼，若S=R，返回result；否則轉(zhuǎn)令Q={S}，轉(zhuǎn)5）。

步驟2）、3）中，為求得外裁剪部分，首先需要求得A和B的交接關(guān)系。根據(jù)排放的特點(diǎn)，排放后A和B交接關(guān)系有6種，下文對(duì)照?qǐng)D3予以說(shuō)明：

1）B邊與A邊重疊，交點(diǎn)為B的端點(diǎn)，如b10、b11、b13、b14等，其中含兩種特殊情況：

①A和B有連續(xù)多條邊重疊，此時(shí)重疊范圍內(nèi)A和B的端點(diǎn)均不計(jì)入交點(diǎn)，并將這些重復(fù)點(diǎn)從A和B原點(diǎn)集中消除，如a5或b5；

②兩邊有一個(gè)端點(diǎn)重疊，如b14與a9或b13同記為交點(diǎn)。

2）A邊交B端點(diǎn)，如交點(diǎn)b1。

3）A端點(diǎn)交B邊，如交點(diǎn)a7。

4）A和B端點(diǎn)內(nèi)交，如交點(diǎn)a6或b8。

5）A和B端點(diǎn)外交，如交點(diǎn)a3或b3。

圖3對(duì)應(yīng)排放在步驟2）結(jié)束后aArray為{a1，a2，b3，a4，b4，b6，b8，a7，a8，b10，b11，b13，b14，b1}，bArray為{b1，b2，b3，b4，b6，b7，b8，b9，a7，b10，b11，b12，b13，b14}。

步驟3）中，對(duì)情形1和2，每個(gè)交點(diǎn)將標(biāo)記為“入”或“出”，對(duì)情形3～5，交點(diǎn)需先標(biāo)記為“入”，再標(biāo)記為“出”。如圖3中對(duì)應(yīng)aArray中b1～a5間端點(diǎn)集更新后：{b1（入），b1（出），a1，a2，b3（入），b3（出），a4，b4（入）}。

設(shè)取出多邊形A頂點(diǎn)集的第一個(gè)出點(diǎn)為b1，在上述結(jié)果集上應(yīng)用算法的步驟4）～8）后可得到{b1，a1，a2，b3，b2}和{b3，a4，b4}兩個(gè)孔洞。aArray中選擇b1（出）后依次取未標(biāo)記頂點(diǎn)a1和a2，遇到b3（入）后轉(zhuǎn)bArray中逆時(shí)針查找得到b2，繼續(xù)查找時(shí)遇到本輪起點(diǎn)b1，產(chǎn)生了第一個(gè)孔洞。下一次查找從b3（出）開始，產(chǎn)生孔洞{b3，a4，b4}。

給定分別具有m和n條邊的被裁和待裁多邊形，算法中的頂點(diǎn)數(shù)組aArray和bArray的長(zhǎng)度為m+2～m+2n或n+2～2m+n。設(shè)待裁多邊形頂點(diǎn)與被裁多邊形接觸的個(gè)數(shù)是等概率事件，即pi=1/n，則aArray的平均長(zhǎng)度為：

la=1n∑ni=1（m+2i）=m+（n+1）/2（4）

同理可求bArray的平均長(zhǎng)度為lb=n+（m+1）/2，因此掃描頂點(diǎn)數(shù)組的平均時(shí)間復(fù)雜度為O（m+n）。算法為保持完整性將求交點(diǎn)置于步驟2），實(shí)際上，在計(jì)算EF值時(shí)可同步求出交點(diǎn)，復(fù)雜度為O（m+n），因此WACompute算法復(fù)雜度為O（m+n）。

3.3啟發(fā)式排樣算法

排樣過(guò)程劃分為四個(gè)階段：1）初始原材料的前處理，將任意二維的排樣問(wèn)題歸一化為二維裝箱問(wèn)題；2）利用FFD策略選擇一個(gè)樣件，利用排樣策略排放該樣件；3）對(duì)剩余原材料進(jìn)行后處理，得到可應(yīng)用下一次排樣策略的原材料列表；4）重復(fù)2）～4）步，直到剩余原材料列表不能排放任何樣件或樣件已經(jīng)排放結(jié)束?；贕NFP和EF值的啟發(fā)式排樣算法GEFHNA）如下：

Algorithm GEFHNA（Part * pPart， Panel * pPanel）

//描述：采用FFD選件策略，優(yōu)先排放面積小的原材料。

//輸入：待排樣件列表pPart，原材料列表pPanel；

//輸出：排樣完后的原材料列表pPanel，剩余樣件列表pPart。

1）初始化原材料列表數(shù)據(jù)、樣件數(shù)據(jù)等。

2）對(duì)pPart中的樣件按面積大小降序排序。

3）將pPanel中的原材料歸一化，并按照面積大小升序排序。

4）取當(dāng)前最大的未試排樣件。

5）取pPanel中的第一個(gè)原材料p。

6）若樣件面積不小于原材料面積，轉(zhuǎn)9）；否則調(diào)用PackingI，若返回1則轉(zhuǎn)7），否則轉(zhuǎn)9）。

7）調(diào)用WACompute計(jì)算排樣后的剩余原材料R，更新pPanel，刪除p，并將R中面積大于當(dāng)前最小未排樣件面積的原材料加入到pPanel。

8）取下一個(gè)未試排樣件，若存在轉(zhuǎn)5），否則轉(zhuǎn)10）。

9）從pPanel中取下一個(gè)原材料，若成功轉(zhuǎn)6），否則轉(zhuǎn)4）。

10）計(jì)算材料利用率，返回。

設(shè)原材料數(shù)為m，待排樣件數(shù)為n，原材料和樣件最多邊數(shù)為t條。上述算法中步驟1）需O（m+n）步操作，步驟2）和3）需O（m log m+ n log n）步操作，與PackingI算法相比這些操作對(duì)排樣算法性能影響較小。設(shè)每次排樣后產(chǎn)生的孔洞個(gè)數(shù)是等概率的，則每次排樣后增加的平均孔洞數(shù)為（t+1）/2個(gè)，在不考慮步驟6）的優(yōu)化條件下，GEFHNA對(duì)i個(gè)樣件排樣時(shí)調(diào)用PackingI的最多次數(shù)為：

cpanel=m-（i-1）+（i-1）（t+1）/2=

m+（i-1）（t-1）/2（5）

設(shè)樣件成功與失敗排放和成功排放在某各原材料上均是等概率的，則對(duì)i個(gè)樣件排樣時(shí)調(diào)用PackingI的平均次數(shù)為：

acpanel=12cpanel∑cpanelj=1（j+cpanel）=（3cpanel+1）/4（6）

排放n個(gè)樣件共需調(diào)用PackingI的平均次數(shù)為：

∑ni=1acpanel=3mn+n4+3n（n-1）（t-1）16（7）

由式（7），綜合PackingI和WACompute算法的復(fù)雜度，GEFHNA算法的平均時(shí)間復(fù)雜度為O（mntk） *T（G），其中k為樣件最大旋轉(zhuǎn)角度數(shù)，T（G）為計(jì)算GNFP的時(shí)間漸近復(fù)雜度。由于步驟6）的優(yōu)化，算法實(shí)際效率可以得到大幅提高。

4測(cè)試結(jié)果與分析

本文以歐洲排樣問(wèn)題興趣小組ESICUP[13]提供的基準(zhǔn)問(wèn)題作為測(cè)試算例，對(duì)本文提出的GEF啟發(fā)式排樣算法的排樣效果和性能進(jìn)行測(cè)試。

測(cè)試環(huán)境：Intel Core2 Duo CPU T6570 @2.10GHz，2GB RAM，Windows 7旗艦版。

測(cè)試方法：每個(gè)基準(zhǔn)問(wèn)題均運(yùn)行10次，排樣時(shí)間取10次運(yùn)行的平均排樣時(shí)間。

針對(duì)時(shí)間性能的GEF啟發(fā)式排樣算法的測(cè)試結(jié)果如表1所示。因合理結(jié)合遺傳算法和禁忌搜索算法可有效抑制早熟，同時(shí)提高收斂速度，與單一算法比較效果更好[15]，本文將啟發(fā)式算法與之對(duì)比。表中混合智能算法為作者結(jié)合遺傳算法和禁忌搜索算法實(shí)現(xiàn)的智能排樣算法的排樣密度和排樣時(shí)間。從表1可以看出，雖然啟發(fā)式算法排樣密度較智能算法有較大差距，但用時(shí)僅為智能算法的千分之一左右。在排樣密度方面，當(dāng)排樣長(zhǎng)度較小時(shí)（100單位以內(nèi)），通過(guò)計(jì)算可得啟發(fā)式算法與智能算法的排樣密度相比平均高5%左右，說(shuō)明在排樣局面較為簡(jiǎn)單的情況，啟發(fā)式排樣不但速度快，排樣密度也較高。

5結(jié)語(yǔ)

本文提出了一種基于GNFP與邊適應(yīng)度的啟發(fā)式排樣算法——GEFHNA。利用ESICUP提供的基準(zhǔn)測(cè)試算例，GEFHNA算法在與智能算法及商業(yè)軟件的對(duì)比中均取得了較為滿意的結(jié)果。限于啟發(fā)式算法對(duì)規(guī)則的依賴，面對(duì)較為復(fù)雜的排樣局面，GEFHNA在排樣密度方面與智能算法相比效果有待提高。另外，雖然增加了剩余原材料的處理，但從測(cè)試結(jié)果看個(gè)別案例提升效果不明顯，下一步將結(jié)合A*算法的思想，考慮樣件的形狀特征，減小排放一個(gè)樣件后再排后續(xù)樣件可能產(chǎn)生縫隙的大小。

參考文獻(xiàn)：

[1]

DYCKHOFF H. A typology of cutting and packing problems [J]. European Journal of Operational Research， 1990， 44（2）： 145-159.

[2]

LPEZCAMACHO E， OCHOA G， TERASHIMAMARN H， et al. An effective heuristic for the twodimensional irregular bin packing problem [J]. Annals of Operations Research， 2013， 206（1）： 241-264.

[3]

BAKER B S， COFFMAN E G， RIVEST R L. Orthogonal packings in two dimensions [J]. SIAM Journal on Computing， 1980， 9（4）： 846-855.

[4]

ALLEN S D， BURKE E K， KENDALL G. A hybrid placement strategy for the threedimensional strip packing problem [J]. European Journal of Operational Research， 2011， 209（3）： 219-227.

[5]

LIU D Q， TENG H F. An improved BLalgorithm for genetic algorithm of the orthogonal packing of rectangles [J]. European Journal of Operational Research， 1999， 112（2）： 413-420.

[6]

HOPPER E， TURTON B C H. An empirical investigation of metaheuristic and heuristic algorithms for a 2D packing problem [J]. European Journal of Operational Research， 2001， 128（1）： 34-57.

[7]

UDAY A， GOODMAN E D， DEBNATH A A. Nesting of irregular shapes using feature matching and parallel genetic algorithms [C]// GECCO 2011： Proceedings of the 12th Annual Conference Companion on Genetic and Evolutionary Computation. New York： ACM， 2001： 429-434.

[8]

ALBANO A， SAPUPPO G. Optimal allocation of twodimensional irregular shapes using heuristic search methods [J]. IEEE Transactions on Systems， Man and Cybernetics， 1980， 10（5）： 242-248.

[9]

DOWSLAND K A， VAID S， DOWSLAND W B. An algorithm for polygon placement using a bottomleft strategy [J]. European Journal of Operational Research， 2002， 141（2）： 371-381.

[10]

劉胡瑤.基于臨界多邊形的二維排樣算法研究[D].上海：上海交通大學(xué)，2007：65-81.（LIU H Y， Research of two dimensional nesting algorithm based on no fit polygon [D]. Shanghai： Shanghai Jiao Tong University， 2007：65-81.）

[11]

LAMBERT M， MARIAM T， SUSAN F. Weiler—Atherton Clipping Algorithm [M]. Beau Bassin： Betascript Publishing， 2010：35-61.

[12]

OLIVEIRA J F， GOMES A M， FERREIRA J S. TOPOS–a new constructive algorithm for nesting problems [J]. ORSpektrum， 2000， 22（2）： 263-284.

[13]

ESICUP. EURO Special Interest Group on Cutting and Packing [EB/OL].[20151224]. http：//paginas.fe.up.pt/～esicup/tikiindex.php.打不開

[14]

劉虓.基于HAPE的二維不規(guī)則零件排樣算法及其性能研究[D].廣州：華南理工大學(xué)，2011：52-63.（LIU X. Twodimensional irregular packing algorithm based on HAPE and its performance study [D]. Guangzhou： South China University of Technology， 2011： 52-63.）

[15]

孫艷豐.基于遺傳算法和禁忌搜索算法的混合策略及其應(yīng)用[J].北京工業(yè)大學(xué)學(xué)報(bào)，2006，32（3）：258-262.（SUN Y F， A hybrid strategy based on genetic algorithm and tabu search[J]，Journal of Beijing University of Technology ， 2006， 32（3）： 258-262.）