饒運清,彭 燈,杜 冰+,羅 強,林信海

(1.華中科技大學 機械科學與工程學院,湖北 武漢 430074;2.中國艦船研究設計中心,湖北 武漢 430064)

0 引言

異形件排樣問題是典型的離散組合優(yōu)化問題,屬于NPC(non-deterministic polynomial complete)問題,這類問題廣泛存在于金屬切割、船舶制造、服裝裁剪等行業(yè)中,因此其研究成果具有重要的經(jīng)濟價值。迄今為止的研究幾乎都是滿足零件輪廓不超出板材邊界約束條件的常規(guī)排樣問題[1],但是在某些實際應用中,還存在著零件超邊界約束這類特殊的排樣問題,即允許零件有條件地超出板材邊界,稱為“超邊界約束排樣問題”。文獻[2]研究了艦載機在航空母艦上的布列優(yōu)化問題,其中艦載機在飛行甲板上布列時允許其部分超出甲板邊界線,只要艦載機的支撐輪全部位于甲板邊界以內(nèi)即可;文獻[3]提出一種基于外圍收縮順序的混合啟發(fā)式定位算法,即先采用基于BL(bottom-left)策略的啟發(fā)式靠邊定位算法對板材邊界處的零件進行超邊界排放,然后采用改進的多邊形掃描定位算法對完全位于板材邊界以內(nèi)的零件進行排放,并使用粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法對零件的排樣順序進行優(yōu)化。目前關于超邊界約束排樣問題的研究在公開發(fā)表的文獻中鮮有報道,而這一問題又恰恰具有非常實際的用途,尤其是在航空母艦的艦載機布列優(yōu)化問題上,自動布列系統(tǒng)能迅速地完成艦載機的布列,在充分利用甲板面積的同時提高布列效率,不僅可以節(jié)省大量的人工操作,更重要的是可以更好地為航空母艦架次出動率的計算提供有力的理論依據(jù)。因此對這類問題的研究具有一定的創(chuàng)新性。

求解異形件排樣問題可分為零件定位與定序兩部分實現(xiàn),常用的零件定位算法有BL[4]、BLF(bottom left fill)[5]、最低重心臨界邊形(Non-Fit Polygon,NFP)算法[6]等,目前主要采用元啟發(fā)式算法來優(yōu)化零件的排樣順序,如遺傳算法(Genetic Algorithm,GA)[7]、模擬退火算法(Simulated Annealing,SA)[8]、蟻群算法(Ant Colony Optimization,ACO)[9]等。上述算法仍存在材料利用率不高的問題,而且超邊界約束條件使得現(xiàn)有零件定位算法無法直接應用,因此需要進一步研究適用于求解超邊界約束排樣問題且能獲得高利用率的排樣算法。

本文針對超邊界約束條件,采用一種板材動態(tài)邊界搜索的處理策略,以臨界多邊形為基礎,同時引入無碰撞區(qū)域(Collision Free Region,CFR)的概念,以保證排樣方案的可行性,在綜合考慮重合率和BL策略,以及CFR可能退化為點或線段的情況之后,提出一種基于動態(tài)邊界搜索的混合啟發(fā)式定位算法,并采用遺傳算法優(yōu)化排樣方案。最后,通過實例測試驗證了本文所提排樣算法的有效性。

1 超邊界約束排樣問題描述

本文研究的是在超邊界約束條件下,異形件在帶缺陷不規(guī)則板材上的裝箱排樣問題,具體描述為:將n個二維不規(guī)則零件{P1,P2,…,Pn}合理地放置到板材S上,其中每個零件上具有若干個關鍵點{K1,K2,…,Kt},優(yōu)化目標是使板材S的利用率最大化,需要滿足以下約束條件:①所有零件之間不發(fā)生重疊;②零件與板材上的缺陷區(qū)域不發(fā)生干涉;③零件上的所有關鍵點必須全部位于板材邊界以內(nèi);④零件能以任意角度旋轉。如圖1所示為超邊界約束排樣問題的示意圖,在排樣過程中零件有完全位于板材邊界內(nèi)和部分超出板材邊界兩種狀態(tài)。

超邊界約束排樣問題的數(shù)學描述如下:

(1)

s.t.

Pi∩Pj=?;
Kr?S;
Pi∩Qk=?;
i≠j,i,j=1,2,…,n;
k=1,2,…,m;
r=1,2,…,t。

(2)

其中:m表示板材S上缺陷區(qū)域的總個數(shù),Qk表示板材S上的第k個缺陷區(qū)域,Kr表示零件Pi上的第r個關鍵點。

對于n個零件參與排樣的問題,其解空間大小為:

T(n)=(360°/Δθ)n×n!。

(3)

式中Δθ為零件的旋轉步角。由式(3)可以看出,問題的時間復雜度會隨著排樣規(guī)模的增大呈階乘級增長,同時旋轉步角Δθ選取的較小時,問題的解空間將呈指數(shù)式增長。有研究表明,零件旋轉步角Δθ≤7°時,原材料利用率提升的幅度很小[10],本文取Δθ=5°,即零件在周角范圍內(nèi)有72種旋轉姿態(tài),零件在定位過程中會根據(jù)評價標準選擇一個最佳的旋轉角度。

2 算法描述

求解異形件排樣問題主要分為零件定位和定序兩部分。在零件定位方面,先采用板材擴邊界策略處理超邊界約束條件,從而可以直接應用現(xiàn)有的幾何工具與定位策略,接著利用臨界多邊形提取待排樣零件的可行定位點,最后根據(jù)定位評價標準確定最終的定位點。在零件定序方面,采用十進制編碼的方式,應用適合求解離散組合優(yōu)化問題的遺傳算法對零件排樣順序進行優(yōu)化。

2.1 相關定義

2.1.1 NFP

臨界多邊形(NFP)是求解異形件排樣問題的基礎幾何工具。相比于直接三角法,NFP能有效降低多邊形判交計算的時間復雜度,并且能給出兩多邊形之間的所有靠接位置,能較好地實現(xiàn)零件的精準定位。臨界多邊形的定義如下:對于平面內(nèi)的兩個多邊形A和B,固定多邊形A不動,將多邊形B繞著多邊形A移動一周,在移動過程中,多邊形B作平移不旋轉的剛體運動,且與多邊形A始終保持接觸不重疊的狀態(tài),則多邊形B上參考點Pref的移動軌跡所形成的封閉輪廓就是多邊形B相對于多邊形A的臨界多邊形,記為NFPAB。NFPAB的生成過程如圖2所示,取多邊形B上的最下最左(優(yōu)先最下)頂點作為參考點Pref。

NFP的幾何意義在于將多邊形之間的重疊判斷簡化為點與多邊形的位置關系判斷,具體為:①若參考點Pref位于NFPAB內(nèi)部,則多邊形A與B重疊;②若參考點Pref位于NFPAB的邊界上,則多邊形A與B接觸但不重疊;③若參考點Pref位于NFPAB外部,則多邊形A與B相離。

2.1.2 IFP

IFP的定義與NFP相似,具體為:對于平面內(nèi)給定的板材多邊形A和零件多邊形B,固定A不動,將B繞著A的內(nèi)側輪廓作平移不旋轉的剛體運動移動一周,在移動過程中,A與B始終保持接觸但不重疊的靠接狀態(tài),則B上參考點Pref的移動軌跡就是零件多邊形B相對板材多邊形A的內(nèi)靠接臨界多邊形,記為IFPAB。IFPAB的生成過程如圖3a所示。

IFP的幾何意義在于將多邊形之間的包含關系判斷簡化為點與多邊形的位置關系判斷,具體為:①若參考點Pref位于IFPAB的內(nèi)部,則零件B完全在板材A的內(nèi)部;②若參考點Pref恰好位于IFPAB的邊界上,則零件B恰好與板材A的內(nèi)側邊界接觸;③若參考點Pref位于IFPAB的外部,則零件B部分或完全超出板材A的邊界。

2.1.3 CFR

求解待排樣零件相對板材上已排樣零件(包括缺陷區(qū)域)的NFP,可保證零件之間以及零件與缺陷區(qū)域之間不發(fā)生干涉,求解待排樣零件相對板材的IFP,能保證零件完全位于板材的內(nèi)部,結合NFP與IFP就能滿足一般排樣問題的基本約束條件。

待排樣零件所有可行定位點的集合可稱為無碰撞區(qū)域(Collision Free Region,CFR),CFR這一概念最早由MARTINS等[11]于2006年提出,是指IFP的內(nèi)部和所有NFP的外部構成的可行排樣區(qū)域,包括IFP與NFP的邊界。本文引入CFR概念的目的是為了保證排樣方案的可行性,對于當前待排樣零件Pi的CFR求解過程如下:

(1)求解零件Pi相對板材的IFP;

(2)求解零件Pi相對板材上的缺陷區(qū)域以及已排樣零件的NFP,并對這些NFP進行多邊形的二維布爾并運算,得到的結果記為∪NFP;

(3)對IFP和∪NFP進行多邊形的二維布爾差運算,所得的結果即為零件Pi的CFR。

給定一塊有q個缺陷區(qū)域Q={Q1,…,Qq}的板材S,且板材S上已經(jīng)放置了n個零件P={P1,…,Pn},下一步需要將零件Pm放置到板材S中,其中m=n+1,則零件Pm的CFR定義如下:

(4)

由式(4)可知,第一個排樣零件的CFR為零件相對板材的IFP。如圖4所示,板材S中有一個缺陷區(qū)域Q,P1、P2、P3為已排樣零件,P4為待排樣零件,圖中的深灰色區(qū)域為零件P4的CFR,零件P4的參考點Pref定位于CFR的邊界和內(nèi)部都是可行的。

2.2 動態(tài)邊界搜索策略

2.2.1 板材擴邊界排樣策略

為了能應用現(xiàn)有且成熟的幾何工具和定位策略,本文采用一種板材“擴邊界”策略來處理超邊界約束條件,如圖5所示,將板材邊界向外等距擴展,為方便描述,稱擴展后得到的邊界為軟邊界,板材的原邊界為硬邊界。

在排樣過程中,用板材的軟邊界對零件進行定位,使得零件完全位于軟邊界以內(nèi),可稱為軟邊界約束。用板材的硬邊界判斷零件的擺放位置是否滿足超邊界約束條件,即判斷零件上的關鍵點是否全部位于硬邊界以內(nèi),可稱為硬邊界約束。利用CFR對零件進行定位,排樣一定會滿足軟邊界約束條件,不需要進行額外的判斷,對于硬邊界約束條件,只需判斷點與多邊形的位置關系即可。

2.2.2 確定板材邊界擴展距離

確定板材邊界的擴展距離是首先需要解決的一個難點問題,如果擴展距離選取過大,會導致零件的定位過程存在很多冗余計算,降低排樣算法的效率;如果擴展距離選取過小,會導致零件超出板材邊界的部分很少,降低板材的利用率。為了使板材利用率最大化,則希望零件盡可能多地超出板材邊界,因此擴展距離應在合理的范圍內(nèi)盡可能取的大些。

在研究的項目中,參與排樣的零件以及零件上的關鍵點均具有軸對稱性質(zhì),于是可根據(jù)零件與板材邊界的幾種典型位置關系來確定擴展距離,如圖6所示,零件的對稱軸與板材邊界的一條邊垂直或平行,且零件上至少有一個關鍵點與板材的硬邊界接觸,分別求得零件在這些特殊擺放姿態(tài)下滿足硬邊界約束條件的板材邊界最小擴展距離,取其中的最大值作為板材邊界擴展距離值。對于非軸對稱零件,首先以零件上的關鍵點構造出包絡關鍵點的軸對稱形狀,再以此軸對稱形狀對非軸對稱零件進行包絡,最后按照軸對稱零件的規(guī)則獲取板材邊界擴展距離值。

2.2.3 動態(tài)邊界搜索策略

由于零件在定位過程中可以選擇多種不同的旋轉角度,選取的擴展距離并不能保證零件的所有擺放姿態(tài)都滿足硬邊界約束條件,可能會出現(xiàn)零件的外輪廓在軟邊界內(nèi),但有個別關鍵點在硬邊界外的情況,此時零件的定位點是不可行解。對于這種情況,本文提出了板材動態(tài)邊界搜索的解決策略,即將軟邊界向內(nèi)收縮以搜索可行解,如圖7所示。更具體的描述為將擴展距離n等分,生成n個軟邊界,按邊界擴展距離從大到小的順序?qū)@n個軟邊界進行搜索,采用定位算法求解待排樣零件滿足軟邊界約束條件的定位點,接著判斷該定位點是否滿足硬邊界約束條件,若滿足,則保存這個可行解,為了提高排樣方案的質(zhì)量,當找到一個可行解時,不會立即停止搜索,而是會繼續(xù)搜索余下的軟邊界,最后從所有可行解中選擇一個最左的定位點來擺放零件。

根據(jù)測試經(jīng)驗,將擴展距離10等分時,能較好地平衡解的質(zhì)量與計算時間成本之間的矛盾,具體的零件定位過程如下:

步驟1根據(jù)零件的幾何形狀、尺寸,以及參考點在零件上的位置信息,計算板材邊界的最大擴展距離d;

步驟2初始化板材邊界擴展距離d*=d,并將板材邊界向外等距擴展d*個單位長度,獲得最外側的軟邊界;

步驟3采用定位算法求解待排樣零件在當前軟邊界下的定位點;

步驟4判斷該定位點是否滿足硬邊界約束條件,如果滿足,則將該可行解保存到集合PositionSet中,并執(zhí)行下一步,否則,直接執(zhí)行下一步;

步驟5更新板材邊界的擴展距離為d*=d*-d/10;

步驟6判斷d*是否大于等于0,若是,則執(zhí)行下一步,否則就從集合PositionSet中選擇X坐標最小的定位點來擺放零件,單個零件的排樣過程結束;

步驟7將板材邊界向外等距擴展d*個單位長度,獲得新的軟邊界,并返回步驟3。

具體流程如圖8所示。

2.3 基于CFR的混合啟發(fā)式定位算法

利用CFR可將排樣問題轉化為零件的定位點選優(yōu)過程,有研究表明,將零件定位到CFR的頂點上既能獲得較高質(zhì)量的排樣方案,又能保證排樣效率[12]。由于在零件在定位過程中會對多個軟邊界進行搜索,定位點的搜索空間仍然很大,有必要進行再次篩選,根據(jù)NFP的基本性質(zhì),當多邊形B定位到NFPAB的凸點上時,多邊形A和B只會接觸于一點,多邊形之間的貼合度很低,由式(4)可知,NFP的凸點會導致CFR形成凹點,因此可將CFR上的凹點從候選定位點集合中剔除掉。

在確定了候選定位點的集合后,接下來需要考慮如何選擇一個評估值最優(yōu)的定位點來放置零件。常用的策略有BL,即總是選擇候選定位點中最左最下的點放置零件,但BL策略存在排樣利用率不高的缺點,因此還需要考慮其他的評價標準,如零件之間的契合度。參考文獻[13]中提出的零件定位評價標準,本文將待排樣零件的包絡矩形與已排樣零件的包絡矩形之間的重疊面積之和作為零件之間契合度的度量值。如圖9所示,板材S中已經(jīng)放置了零件A,B為待排樣零件,可以直觀地看出,相比于最左最下點P1或P5,零件B定位于CFR的凸點P8時,零件A和B之間的契合度更高,能得到更好的局部排樣方案,并且有利于后續(xù)排樣過程。

假設板材S上已經(jīng)放置了m-1個零件,則待排樣零件Pm的契合度計算公式如下:

(5)

式中SR表示兩個零件包絡矩形的重疊面積。

切合度是一個絕對量,在排樣時會傾向于優(yōu)先放置面積大的零件,為了消除零件自身幾何屬性對排樣順序的影響,引入重合率的概念,設契合度與零件包絡矩形面積的比值為重合率e,當重合率大于某個閾值時,就可認為以重合率作為評價標準能產(chǎn)生更優(yōu)的解。重合率的數(shù)學定義為:

(6)

式中w和h分別表示零件Pm包絡矩形的寬和高。當重合率大于設定的閾值e0時,以重合率作為評價標準來選擇候選定位點,否則以BL策略選取定位點,根據(jù)經(jīng)驗,e0取值0.5。

考慮到在排樣過程中,待排樣零件的CFR可能存在退化為點或線段的情況,這意味著零件之間能形成一種精確填充或滑動的配合關系,此時零件之間貼合的非常緊密,應該優(yōu)先考慮將零件定位于CFR退化的點或線段上。

綜合以上分析,在考慮了各個評價標準的優(yōu)先級之后,本文提出一種基于CFR的混合啟發(fā)式定位算法,待排樣零件的具體定位過程如下:

步驟1檢測CFR中是否有退化的點,若有,接著判斷退化點的個數(shù),若只有一個,則直接將零件定位于該點上,若有多個,則選擇其中最左最下(優(yōu)先最左)的點作為零件的定位點,若沒有退化的點,則執(zhí)行步驟2;

步驟2檢測CFR中是否有退化的線段,若有,則選擇線段上最左最下(優(yōu)先最左)的端點作為零件的定位點,否則執(zhí)行步驟3;

步驟3先剔除掉CFR上的凹點,接著計算每個候選定位點的重合率,若有定位點的重合率大于設定的閾值,則將重合率最大的點作為零件的定位點,否則執(zhí)行步驟4;

步驟4在候選定位點集合中選擇最左最下(優(yōu)先最左)的點作為零件的定位點。

具體的流程圖如圖10所示。

2.4 遺傳算法優(yōu)化排樣順序

在確定了零件的定位算法后,排樣方案的質(zhì)量就只與零件的排樣順序有關,可將排樣問題當作離散組合優(yōu)化問題求解。鑒于遺傳算法(GA)具有很好的全局搜索能力和自適應性,并且在求解組合優(yōu)化問題中有著廣泛的應用,因此本文采用遺傳算法優(yōu)化零件的排樣順序。GA的基本原理是通過選擇、交叉、變異算子改變?nèi)旧w的編碼,從而產(chǎn)生新的排樣順序,經(jīng)過多次循環(huán)迭代,直到滿足終止條件,并輸出最優(yōu)解。

2.4.1 個體的編碼與解碼

本文采用十進制整數(shù)編碼的方式對零件排樣順序進行編碼,即用1～n之間的整數(shù)作為排樣零件的唯一標識碼,n為排樣零件的總個數(shù)。采用上文提出的定位算法對零件序列進行解碼,從而生成排樣圖并計算板材利用率。

2.4.2 種群初始化

初始化種群在一定程度上會影響算法的收斂速度以及解的質(zhì)量,考慮到隨機方式存在收斂速度慢,解的質(zhì)量難以保證等缺點,本文采用隨機與啟發(fā)式規(guī)則(零件面積降序)相結合的方式生成初始種群。

2.4.3 適應度函數(shù)

適應度函數(shù)的作用是對種群中的個體進行評價,從而指導算法朝著適應度更優(yōu)的方向進行搜索。為了直觀地反映可行解的優(yōu)劣,本文以排樣圖中板材的利用率作為適應度函數(shù)的唯一度量標準,適應度函數(shù)定義如下:

(7)

2.4.4 種群的進化過程

(1)選擇操作

(2)交叉操作

交叉操作是為了產(chǎn)生新的個體,常用的方法有:次序交叉法、順序循環(huán)交叉法、單點交換和多點交換等。本文選用順序循環(huán)交叉法,具體示例如圖11所示。

(3)變異操作

變異操作是為了保證種群的多樣性,避免算法陷入局部最優(yōu),常用的方法有移位和交換兩種操作。本文選用交換操作作為變異算子,即隨機產(chǎn)生兩個[1,n]區(qū)間內(nèi)的整數(shù)p和q,通過交換p和q索引處的等位基因來產(chǎn)生新的變異個體,如圖12所示。通過設置的變異概率pm來決定是否對個體執(zhí)行變異操作,例如隨機生成一個[0,1]區(qū)間內(nèi)的隨機數(shù)r2,如果r2

2.5 整體算法流程

超邊界約束排樣算法的具體實現(xiàn)步驟如下:

步驟1讀取零件和板材數(shù)據(jù),計算板材邊界擴展距離,保存多個板材軟邊界信息;

步驟2初始化種群,調(diào)用基于CFR的混合啟發(fā)式定位算法生成排樣圖,并計算板材利用率,保存適應度值最高的個體作為當前最優(yōu)解;

步驟3執(zhí)行選擇、交叉、變異操作,更新種群個體的編碼序列;

步驟4重新調(diào)用定位算法對個體進行解碼,更新最優(yōu)解;

步驟5判斷是否滿足終止條件,是則輸出最優(yōu)解,結束算法,否則轉步驟3。

算法的基本流程圖如圖13所示。

3 算法實例

由于目前尚不存在超邊界約束排樣問題的基準算例,并且項目中的測試圖形屬于涉密文件,為驗證所提排樣算法的有效性,本文采用美軍公開的艦載機布列數(shù)據(jù)進行測試。本文提出的排樣算法同樣適用于求解不存在超邊界約束條件的一般排樣問題,只要不對板材進行擴邊界處理即可。算法在Visual Studio 2012開發(fā)平臺上使用C++語言編程實現(xiàn),程序的運行環(huán)境為:Intel(R)Core(TM)i5-4590 CPU@3.30 GHz,RAM為8 GB,Windows7操作系統(tǒng)。

以“尼米茲”號航空母艦為例,通過文獻[14]獲取航空母艦機庫甲板與飛行甲板的幾何輪廓與尺寸,如圖14所示,F/A-18C飛機在機庫甲板上布列了53架,在飛行甲板上布列了77架,總計130架,與美軍公布的130架F/A-18C飛機[15]一致。

美國海軍根據(jù)多年的研究經(jīng)驗,提出“布列因子”這一指標來評估艦載機在航空母艦機庫甲板和飛行甲板上的布列質(zhì)量,布列因子指的是航空母艦上機庫甲板和飛行甲板所能布列的基準機型最大數(shù)量與參考機型最大布列數(shù)量的比值[16]。以F/A-18C型飛機作為基準艦載機,其布列因子為1,美軍公布的F-35C飛機的布列因子[17]為1.11,如圖15所示,F-35C飛機在機庫甲板上布列了48架,在飛行甲板上布列了69架,總計117架,根據(jù)布列因子的定義,計算F-35C飛機的布列因子為1.11,該結果與美軍公布的數(shù)據(jù)相同。

4 結束語

在國家自然科學基金等項目的支持下,本文針對超邊界約束排樣問題開展了相關研究工作。針對超邊界約束條件,本文提出了板材動態(tài)邊界搜索的處理策略,在零件定位算法研究方面,以NFP幾何工具為基礎,同時引入CFR的概念,以保證排樣方案的可行性,隨后在綜合考慮了重合率和BL策略,以及CFR可能退化為點或線段的情況之后,提出了基于CFR的混合啟發(fā)式定位算法,并在上述零件定位算法的基礎上,采用遺傳算法對零件排樣順序進行優(yōu)化,最后通過實例驗證了算法的有效性。上述研究成果已經(jīng)在實際國防科研項目中得到成功應用,目前正在繼續(xù)研究更為高效智能的綜合求解算法。