基于二維不規(guī)則圖形的實(shí)用排樣算法研究*

楊傳華,吳錦文,李殿國(guó),楊海

(1.佳木斯大學(xué) 機(jī)械工程學(xué)院,黑龍江 佳木斯 154007;2.奇瑞汽車(chē)股份有限公司,安徽 蕪湖241009;3.東芝大連有限公司,遼寧大連 116600)

0 引言

隨著社會(huì)的發(fā)展、科技的進(jìn)步,二維圖形排樣廣泛存在于許多工業(yè)中,如：機(jī)械廠中金屬板材的排樣,玻璃廠中玻璃的排樣,服裝廠中布料的排樣。長(zhǎng)期以來(lái),人們不斷地研究各種排樣算法,對(duì)于一維排樣和二維規(guī)則圖形排樣已經(jīng)有了比較成熟的排樣算法,而對(duì)于不規(guī)則的圖形[1],現(xiàn)在采用比較多是矩形包絡(luò)法、遺傳算法和模擬退火算法。本文先采用矩形包絡(luò)法對(duì)不規(guī)則圖形進(jìn)行預(yù)處理,在此基礎(chǔ)上采用基于最低水平線的搜索算法和平移靠接算法[2]對(duì)預(yù)處理圖形進(jìn)行排樣。

1 最小矩形包絡(luò)法、基于最低水平線的搜索算法

1.1 最小矩形包絡(luò)法[3]

最小矩形包絡(luò)法就是用矩形將不規(guī)則的圖形包絡(luò)在矩形內(nèi),并使包絡(luò)矩形的面積最小。如圖 1,2所示：

1.2 基于最低水平線的搜索算法[4]

分析 BL算法[5]和“下臺(tái)階算法”可以發(fā)現(xiàn)：前者經(jīng)常會(huì)出現(xiàn)排樣左側(cè)偏高的情況,而后者經(jīng)常會(huì)出現(xiàn)右側(cè)偏高現(xiàn)象。最低水平線算法解決了此問(wèn)題,具體步驟如下：

Step 1：設(shè)置初始最高輪廓線為板材最下面的邊;

Step 2：每當(dāng)要排入一個(gè)零件 Pi時(shí),就在最高輪廓線集中選取最低的一段水平線,如有數(shù)段,則選取最左邊的一段,測(cè)試該段線的寬度是否大于或等于待排零件的寬度：

(1)如果該段線的寬度大于或等于要排入零件的寬度,則將該零件在此位置排放,同時(shí)更新零件最高輪廓線;

(2)否則,查詢(xún)與最低水平線段相鄰的左、右兩段水平線,將最低水平線提升至相鄰且高度較低的一段平齊,同時(shí)更新零件最高輪廓線;

Step 3：重復(fù) Step 2過(guò)程,直至能排入該零件,并求出此時(shí)的最大高度;

Step 4：重復(fù) Step 2和 Step 3過(guò)程,直至所有零件排放完畢,最后所得的最大高度即為所需板材的高度。

基于最低水平線的搜索算法是在最低水平線算法排樣中出現(xiàn)了要排入的零件的寬度大于最高輪廓線集中最低的一段(或多段)水平線時(shí),而不去更新零件的最高輪廓線,而是從未排樣的零件中挑選寬度小于最低水平線寬度的零件[6]。將此兩個(gè)零件交換順序,而后重新生成新的排列順序。

2 平移靠接算法原理[9-11]

平移靠接算法是將兩個(gè)不規(guī)則圖形在水平或豎直發(fā)方向上進(jìn)行靠接,直至兩個(gè)圖形剛好相接(但不交叉,即無(wú)重疊區(qū)域)。以圖 3在水平方向平移靠接為例進(jìn)行說(shuō)明：

圖 3 平移靠接前

(1)首先掃描靠接區(qū)域和確定靠接輪廓線

通過(guò)掃描可以確定靠接區(qū)域?yàn)閳D形 1的右側(cè)和圖形 2的左側(cè),從而可以判斷出圖形 1的靠接輪廓線為ABCDE,圖形 2的靠接輪廓線為 FGHIJK[7-8]。

(2)選取兩個(gè)圖形靠接輪廓線上的折點(diǎn)(即凸凹點(diǎn))

對(duì)于圖形 1輪廓線上的折點(diǎn)有：A、B、C、D、E,圖形2輪廓線上的折點(diǎn)有 ：F、G、H、I、J、K。

(3)確定各個(gè)折點(diǎn)的水平靠接距離

先確定圖形 1上折點(diǎn)的水平靠接距離,過(guò) A點(diǎn)向右作水平線與圖形 2的輪廓線相交(如圖 3所示),并標(biāo)記此線段的長(zhǎng)度為 L1,用此方法可以求得過(guò) B、C、D、E四點(diǎn)與圖形 2輪廓線相交的水平線的長(zhǎng)度,分別標(biāo)記為 L3、L6、L8、L9。

同理可以確定圖形 2上折點(diǎn)的水平靠接距離,分別標(biāo)記為 L2、L4、L5、L7、L9。由于過(guò) F點(diǎn)作水平線不與圖形1的輪廓線相交,所以不作記錄。各個(gè)水平靠接距離形成了數(shù)集 W={L1,L2,L3,L4,…,L9}。

(4)確定最終的水平靠接距離 Wmin

通過(guò)數(shù)值比較從 W數(shù)集中選出數(shù)值最小的 L值作為水平靠接距離 Wmin。(對(duì)于此例,L8的值最小,所以Wmin=L8)。

(5)進(jìn)行水平靠接

以 L8為水平靠接距離進(jìn)行水平靠接,靠接后的圖形如圖 4所示。

圖 4 平移靠接后

3 基于 PRO/E平臺(tái)的排樣實(shí)例及說(shuō)明

3.1 參與排樣的鈑金件的原始數(shù)據(jù)

參與排樣的鈑金件共有 8個(gè),用 PRO/E軟件繪出后如下圖所示(單位為：mm),其中鈑金件外的紅線框?yàn)殁k金件的最小包絡(luò)矩形。

3.2 用 PRO/E軟件中的排樣系統(tǒng)的排樣結(jié)果

將這8個(gè)鈑金件放在寬 100mm,足夠長(zhǎng)的鈑金件上排樣,排樣的順序?yàn)榱慵?1、零件 7、零件 2、零件 6、零件4、零件 3、零件 8、零件 5。如果用的長(zhǎng)度越小,則排樣的效果就越好。PRO/E軟件中的排樣系統(tǒng)的排樣結(jié)果如圖 5所示,此時(shí),鈑金件所用的板材長(zhǎng)度是 49mm。

3.3 用本論文的排樣算法的排樣結(jié)果

用上述同樣的排樣方式和排樣順序,鈑金件所用的長(zhǎng)度是 40mm。對(duì)上述的 8個(gè)鈑金件進(jìn)行排樣,排樣結(jié)果如圖 6所示,此排樣算法的排樣過(guò)程說(shuō)明：①?gòu)陌宀牡淖钭笙露伺赔k金件 1;②排鈑金件 7并進(jìn)行向左水平靠接;③排鈑金件 2;④排鈑金件 6并進(jìn)行向左水平靠接;⑤排鈑金件 4發(fā)現(xiàn)鈑金件 6的右側(cè)寬度不夠,此時(shí)運(yùn)用基于最低水平線的搜索算法從未排樣的鈑金件中搜索到能在此處排樣的鈑金件 8,交換鈑金件 4和鈑金件 8的排樣順序,(即未排鈑金件的排樣順序?yàn)椋衡k金件 3、鈑金件 4、鈑金件 5),此時(shí)更新最低水平線為鈑金件 6最小包絡(luò)矩形的上端線段;⑥在更新后的最低水平線上排鈑金件 3并進(jìn)行向下靠接,此時(shí)更新最低水平線為鈑金件 7最小包絡(luò)矩形的上端線段;⑦在更新后的最低水平線上排鈑金件 4并進(jìn)行向左水平靠接;⑧排鈑金件 5并進(jìn)行向下靠接。經(jīng)過(guò)此算法所得排樣圖如圖 7所示。

4 結(jié)束語(yǔ)

[1]黃紅兵,蔣望東.二維不規(guī)則零件排樣問(wèn)題的研究[J].廣西科學(xué)院學(xué)報(bào),2004,20(4)：225-227.

[2]Song Yanan,Ye Jiawei,Wei Liangliang,etal.The Analysis,New Development and of Packing(Nesting),Symposium on the Development of Ship-building＆Ship-repairing Industry 2003,Guangzhou China,2003(3)：21-22.

[3]曹新明,蔣瑞斌.不規(guī)則零件最小包絡(luò)矩形的求解研究[J].科技通報(bào),2007,1(23)：102-105.

[4]朱冠華.矩形件排樣中基于最低水平線的改進(jìn)算法[J].茂名學(xué)院報(bào),2006,1(16)：28-32.

[5]Jokobs S.On genetic algorithms for the packing of polygons.European Journal of Operational Reseaech,1996,88：165-181.

[6]AdamowiczM,Albano A.A solution of the rectangular cutting-stock problem[J].IEEE Transactions on Systems,Man,and Cybernetics,1976,SMC-6(4)：302-310.

[7]覃中平,張煥國(guó).確定凸多邊形平移時(shí)最初碰撞部位的最優(yōu)算法[J].計(jì)算機(jī)學(xué)報(bào),1992,15(3)：171-177.

[8]汪嘉業(yè).平面上簡(jiǎn)單多邊形平移時(shí)確定碰撞部位的最優(yōu)算法[J].計(jì)算機(jī)學(xué)報(bào),1992,15(8)：582-588.

[9]Cheng S K,Rao K P.Large-Scale nesting of irregu lar patterns using compact neighborhood algorithm.Journal of Materials Processing Technology,2000,(103)：135-140.

[10]宋亞男,葉家瑋,鄧飛其,等.不規(guī)則圖形排樣系統(tǒng)中靠接算法比較研究[J].計(jì)算機(jī)工程,2004,19(30)：8-10.

[11]宋亞男,葉家瑋,鄧飛其,等.排樣系統(tǒng)中基于位圖的三種靠接算法比較[J].武漢科技大學(xué)學(xué)報(bào),2004,1(27)：54-57.