碰靠定位算法在不規(guī)則件排樣優(yōu)化中的應(yīng)用研究

梁利東 鐘相強(qiáng)

安徽工程大學(xué)，蕪湖，241000

0 引言

排樣是指將原材料分割成不同形狀的零件毛坯，因此排樣問(wèn)題可抽象為在給定規(guī)格的原材料(如板材)中，尋找零件排放最優(yōu)布局的優(yōu)化問(wèn)題。不規(guī)則件排樣屬于最復(fù)雜的組合優(yōu)化問(wèn)題之一，不僅表現(xiàn)在對(duì)不規(guī)則零件圖形的幾何形狀描述，還表現(xiàn)在零件形狀不規(guī)則性將導(dǎo)致零件之間的靠接、判交、控制和評(píng)價(jià)等處理比較復(fù)雜且計(jì)算量大。

對(duì)于不規(guī)則零件排樣問(wèn)題，無(wú)論是采用矩形化包絡(luò)法［1］，還是對(duì)不規(guī)則零件直接排樣如臨界多邊形法［2-3］等，都需要對(duì)零件圖形進(jìn)行判交和碰靠定位處理，以實(shí)現(xiàn)零件之間的緊密靠接來(lái)提高原材料的利用率。文獻(xiàn)［1］中提出了一種典型的不規(guī)則排樣算法，即將不規(guī)則件以矩形件排樣結(jié)束后，對(duì)每個(gè)零件進(jìn)行試探性的移動(dòng)碰靠測(cè)試，通過(guò)壓縮或擠壓過(guò)程來(lái)減少未利用空間。Hopper等［4］指出了該算法的局限性，因?yàn)閱蝹€(gè)零件的移動(dòng)可能會(huì)導(dǎo)致其他零件的排樣位置發(fā)生變化，從而難以確定零件的移動(dòng)方向并影響了計(jì)算效率。文獻(xiàn)［5］提出的柵格表示法是將板材劃分為大小相同的矩形柵格或網(wǎng)格，用它來(lái)近似地表示零件的輪廓特征，同時(shí)通過(guò)判斷兩個(gè)零件圖形所占的柵格狀態(tài)來(lái)判斷零件間的位置關(guān)系，算法實(shí)現(xiàn)簡(jiǎn)單。但這種離散化的表示方法受零件圖形的特征或精度要求的局限，對(duì)于那些帶有復(fù)雜弧度或曲線的零件，當(dāng)需要得到較高的排樣精度時(shí)，會(huì)使得柵格數(shù)量劇增，計(jì)算量也相應(yīng)增加，降低了算法的效率。文獻(xiàn)［6］在臨界多邊形(NFP)算法的基礎(chǔ)上，提出了重心NFP的概念，通過(guò)零件的旋轉(zhuǎn)和移動(dòng)選擇重心NFP中最低重心位置來(lái)確定零件的排放定位。這種方法在求解過(guò)程中基本上實(shí)現(xiàn)了零件最低的定位原則，但需要考慮已排零件與邊界形成的輪廓以用來(lái)求解NFP的移動(dòng)碰靠軌跡，計(jì)算量較大。

針對(duì)以上方法的優(yōu)劣分析，本文在對(duì)每個(gè)入排零件進(jìn)行矩形化預(yù)處理來(lái)確定其初始位置的基礎(chǔ)上，根據(jù)最小靜矩原理對(duì)零件圖形進(jìn)行旋轉(zhuǎn)和移動(dòng)碰靠來(lái)搜索當(dāng)前零件的最佳排放位置，并以其排樣高度和碰靠距離來(lái)評(píng)價(jià)最佳吻合定位，從而實(shí)現(xiàn)即時(shí)多角度碰靠?jī)?yōu)化。

1 碰靠定位算法原理

1.1 最低形心碰靠定位方法

零件的排放姿態(tài)涉及入排角度的確定，本文采用的最小靜矩碰靠定位方法是在保證整體排樣高度不增加的基礎(chǔ)上，盡可能通過(guò)對(duì)零件多邊形的旋轉(zhuǎn)和平移碰靠處理，使零件多邊形的靜矩最小。靜矩的物理意義表示零件圖形相對(duì)于板材邊界的遠(yuǎn)近程度或零件之間距離的大小，對(duì)于排樣問(wèn)題，選擇其最小靜矩的入排角度進(jìn)行排放，從理論上可增加零件與板材邊界及零件與零件的接觸面，以減少排樣過(guò)程形成的無(wú)效區(qū)域，從而增加板材的利用率。圖1表示了不同零件在排放中的一般定位(上兩個(gè)示圖)和最小靜矩定位(下兩個(gè)示圖)的對(duì)比示意。圖中的兩組示圖分別以矩形件和不規(guī)則零件為例說(shuō)明，可見(jiàn)零件在入排過(guò)程中以最小靜矩碰靠進(jìn)行定位能有效提高排樣區(qū)域的有效利用率。特別指出，最小靜矩碰靠定位方法是:通過(guò)對(duì)每個(gè)入排零件圖形相對(duì)于形心的多次旋轉(zhuǎn)及定位碰靠試算，從中選擇出靜矩最小的排放角度作為該零件的最優(yōu)入排方案。

圖1 入排零件的最小靜矩碰靠定位的排樣布局優(yōu)化

形心及靜矩的求解采用正負(fù)梯形分割法，即將多邊形通過(guò)各頂點(diǎn)分割成多個(gè)梯形的組合，規(guī)定多邊形逆時(shí)針?lè)较蛎娣e為正，順時(shí)針?lè)较蛎娣e為負(fù)，其中需要注意多邊形各邊的次序和方向。如圖2所示，以五邊形為例，多邊形面積可表示為

圖2 多邊形面積計(jì)算

在實(shí)際下料中，板材一般為均質(zhì)體(即密度相同)且厚度統(tǒng)一，因此排樣零件的形心計(jì)算可簡(jiǎn)化為求解平面多邊形的形心，如圖3所示，多邊形形心求解公式為

圖3 零件多邊形的形心坐標(biāo)

對(duì)水平方向的靜矩為

式中，Ai為零件圖形劃分的單元面積;∑Ai為零件多邊形的面積;(xi，yi)分別為各單元的形心坐標(biāo);Sx為圖形對(duì)于x軸的靜矩或稱對(duì)于x軸面積的一次矩。

多邊形繞其形心進(jìn)行旋轉(zhuǎn)變換以矩陣表示為

從而得到旋轉(zhuǎn)后的位置坐標(biāo)為

式中，(x0，y0)為初始坐標(biāo);(x，y)為旋轉(zhuǎn)后的坐標(biāo);θ為旋轉(zhuǎn)角度。

通?？筛鶕?jù)實(shí)際情況設(shè)置旋轉(zhuǎn)角度間隔Δθ，每個(gè)零件以不同入排角度定位后對(duì)其靜矩值進(jìn)行比較，取靜矩最小實(shí)現(xiàn)入排角度的優(yōu)化。

零件多邊形的數(shù)據(jù)結(jié)構(gòu)定義如下:

1.2 碰靠距離計(jì)算

零件碰靠處理的關(guān)鍵步驟是計(jì)算兩個(gè)零件的碰靠距離即零件按照指定的方向與另一個(gè)零件發(fā)生碰撞時(shí)的移動(dòng)量。一般定義下的零件幾何外形輪廓是由若干基本實(shí)體或圖元(如直線、圓弧、曲線等)組成，碰靠距離可通過(guò)計(jì)算基本實(shí)體間的最短距離來(lái)獲得。文獻(xiàn)［7］論述了各種基本圖元間(如線與線、線段與圓弧、圓弧與圓弧)碰靠距離的計(jì)算方法，從而實(shí)現(xiàn)零件的平移和靠接操作。研究表明，不規(guī)則零件中各實(shí)體(尤其是弧等曲線)的碰靠計(jì)算復(fù)雜度較高，影響排樣系統(tǒng)的執(zhí)行效率。本文采用了一種簡(jiǎn)單而有效的方法來(lái)計(jì)算碰靠距離，即對(duì)零件圖形中各圖元外輪廓進(jìn)行離散化處理，用若干個(gè)離散點(diǎn)形成的連續(xù)的直線段構(gòu)建多邊形來(lái)近似描述零件圖形，這樣將碰靠運(yùn)算轉(zhuǎn)化為各離散點(diǎn)與離散點(diǎn)構(gòu)成的直線段沿碰靠方向的求交和求距的計(jì)算，最終取其最小值作為碰靠距離。圖元離散化過(guò)程簡(jiǎn)化了圖形的表示方法，如直線段只需提取其起始點(diǎn)和終止點(diǎn);圓弧則因規(guī)則性以其起始點(diǎn)和終止點(diǎn)(包含之)來(lái)均分得到各離散點(diǎn);對(duì)于復(fù)雜曲線則根據(jù)其曲率變化適當(dāng)選擇離散點(diǎn)。

假設(shè)給定兩個(gè)零件圖形P和Q，碰靠方向?yàn)樗椒较?其中任意方向都可以通過(guò)圖形變換將其轉(zhuǎn)化為所需碰靠方向，這樣便于描述計(jì)算)，其碰靠距離求解算法的主要步驟如下。

(1)離散化圖形P和Q，分別產(chǎn)生各自的離散頂點(diǎn)序列:P={p1，p2，…，pn}和 Q={q1，q2，…，qm}。其中各頂點(diǎn)的坐標(biāo)可表示為(X(pi)，Y(pi))或(X(qj)，Y(qj))。

(2)計(jì)算圖形P上各頂點(diǎn)到Q的距離。對(duì)于點(diǎn) pi(i=1，2，…，n)，遍歷 Q 上所有頂點(diǎn) qj(j=1，2，…，m)，如果滿足條件:Y(qj+1)≤ Y(pi)≤Y(qj)或Y(qj)≤Y(pi)≤Y(qj+1)，則計(jì)算pi點(diǎn)沿水平方向的直線與線段qjqj+1的交點(diǎn)并求出pi與交點(diǎn)的距離記為dij;否則計(jì)算下一個(gè)點(diǎn)pi+1直到完成P上所有頂點(diǎn)的計(jì)算。從所得距離中取最小距離值min dij。

(3)同樣方法計(jì)算圖形Q上各頂點(diǎn)到P的距離，得到最小距離min d'ij。

(4)比較min dij和min d'ij，取其最小者為零件P和Q的碰靠距離，將零件Q或P以此值作為移動(dòng)量進(jìn)行平移操作，實(shí)現(xiàn)兩個(gè)零件的靠接，如圖4所示。

圖4 零件的碰靠計(jì)算

2 基于最佳吻合碰靠的排樣算法

在零件以一定的次序排入過(guò)程中，首先在給定的排放區(qū)域內(nèi)通過(guò)計(jì)算當(dāng)前零件不同排放角度的靜矩，選擇最小靜矩的入排角度。然后根據(jù)設(shè)定的碰靠方向，對(duì)當(dāng)前零件進(jìn)行碰靠操作，為減小計(jì)算量，通常以水平和垂直方向作為碰靠方向，使零件盡可能緊密靠接，并以當(dāng)前排樣高度最低作為最佳碰靠定位方案。因此，最佳吻合碰靠過(guò)程從某種意義上說(shuō)是使零件在最小靜矩的排放規(guī)則基礎(chǔ)上再進(jìn)行碰靠處理從而搜索到排放高度最低的位置。圖5給出了零件通過(guò)旋轉(zhuǎn)碰靠實(shí)現(xiàn)較好的定位排樣效果。

圖5 最佳吻合碰靠定位示意

此外對(duì)于形狀較復(fù)雜零件，本文設(shè)計(jì)的排樣系統(tǒng)增加了交互式點(diǎn)對(duì)點(diǎn)碰靠方法作為輔助碰靠定位，即依靠人類的先驗(yàn)知識(shí)和感官判斷，對(duì)入排零件可以人為調(diào)整選擇最佳的碰靠方向使零件沿著規(guī)定的靠接定位位置移動(dòng)，如圖6所示。

圖6 交互點(diǎn)對(duì)點(diǎn)碰靠

無(wú)論是自動(dòng)碰靠還是交互碰靠，評(píng)價(jià)最佳吻合碰靠定位的目標(biāo)函數(shù)是零件向下向左移動(dòng)的最大距離或零件實(shí)現(xiàn)靠接后的最低排樣高度，對(duì)于相同排樣高度的情況，優(yōu)先最左靠接位置。目標(biāo)函數(shù)表示為

其中，max(dy)表示高度方向最大碰靠距離，max(dx)表示水平方向最大碰靠距離;α和β為參數(shù)因子，α?β，以保證當(dāng)前面的函數(shù)值不同時(shí)，后面的函數(shù)值不會(huì)對(duì)結(jié)果的判斷造成影響。

碰靠排樣算法流程如圖7所示，圖中虛框中所表示的外循環(huán)表示對(duì)于排樣零件入排次序的優(yōu)化，優(yōu)化方法可采用遺傳算法、粒子群算法等，可參閱文獻(xiàn)［8-9］，本文著重討論定序情況下的定位碰靠方法，故對(duì)其不作詳細(xì)闡述。

圖7 最佳吻合碰靠流程圖

3 應(yīng)用實(shí)例

通過(guò)對(duì)上述算法的描述和分析，本文設(shè)計(jì)排樣系統(tǒng)平臺(tái)，以剩余矩形法作為解碼算法結(jié)合自動(dòng)碰靠算法實(shí)現(xiàn)零件定位和排樣布局。選擇板材長(zhǎng)度為8000mm，寬為2000mm。輸入兩組待排零件，其中以已排零件的面積之和與板長(zhǎng)方向的零件包絡(luò)矩的最高輪廓線以下區(qū)域面積S的比率作為材料利用率的評(píng)價(jià)函數(shù)，其目標(biāo)評(píng)價(jià)函數(shù)表示為

式中，ni為排樣零件個(gè)體;li為零件包絡(luò)矩長(zhǎng)度;wi為零件包絡(luò)矩寬度;N為入排零件個(gè)數(shù);S為整體排樣結(jié)構(gòu)的包絡(luò)面積。

圖8為69個(gè)零件的排樣圖，板材利用率為86.87%;圖9為43個(gè)零件的排樣圖，板材利用率為85.63%。

圖8 排樣布局一

圖9 排樣布局二

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

本文在借鑒矩形化策略基礎(chǔ)上，將零件以最小靜矩(或最低重心)為定位準(zhǔn)則選擇最佳入排角度進(jìn)行正交靠接排放和定位，并設(shè)計(jì)了交互排樣中的點(diǎn)對(duì)點(diǎn)交互碰靠算法，實(shí)現(xiàn)零件以任意碰靠方向進(jìn)行最優(yōu)布局調(diào)整。碰靠距離的計(jì)算采用零件圖形離散化處理，實(shí)現(xiàn)離散點(diǎn)沿碰靠方向的求交和求距，求解方便簡(jiǎn)單。利用該算法設(shè)計(jì)的排樣系統(tǒng)在對(duì)不規(guī)則零件的排樣優(yōu)化中具有較好的穩(wěn)定性和有效性。

［1］Jakobs S.On Genetic Algorithms for the Packing of Polygons［J］.Eurpean Journal of Operational Research，1996，88:165-181.

［2］Bennell J A，Kathryn A，Dowsland W B.The Irregular Cutting－stock Problem－A New Procedure for Deriving the No－fit Polygon［J］.Computers and Operations Research，2001，28:271-287.

［3］劉嘉敏，佟德剛，黃有群.臨界多邊形生成算法的改進(jìn)［J］.沈陽(yáng)工業(yè)大學(xué)學(xué)報(bào)，2005，27(5):567-570.Liu Jiamin，Tong Degang，Huang Youqun.An Improved Approach for No－fit Polygon Creation［J］.Journal of Shenyang University of Technology，2005，27(5):567-570.

［4］Hopper E，Turton B C H.A Genetic Algorithm for 2D Industrial Packing Problem［J］.Computers and Industrial Engineering，1996，37:375-378.

［5］Ismail H S，Hon K K B.The Nesting of Two－dimensional Shapes Using Genetic Algorithms［J］.Proceeding of the Institution of Mechanical Engineers，1995，209(2):115-124.

［6］劉胡瑤，何援軍.基于重心NFP的二維不規(guī)則形狀排樣算法［J］.中國(guó)機(jī)械工程，2007，18(6):723-726.Liu Huyao，He Yuanjun.2D Irregular Nesting Algorithm Based on Gravity Center NFP［J］.China Mechanical Engineering，2007，18(6):723-726.

［7］陳文亮，崔英，李磊.基于自動(dòng)碰撞技術(shù)的最優(yōu)排樣算法［J］.計(jì)算機(jī)應(yīng)用研究，2000，17(7):37-39.Chen Wenliang，Cui Ying，Li Lei.The Optimized Nest Algorithm Based on Automatic Touching Technology［J］.Application Research of Computers，2000，17(7):37-39.

［8］梁利東，葉家瑋.基于遺傳算法的不規(guī)則件優(yōu)化排樣的研究［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(2):223-224，228.Liang Lidong，Ye Jiawei.Research of Irregular Parts with Genetic Algorithm［J］.Computer Engineering and Application，2009，45(2):223-224，228.

［9］梁利東，鐘相強(qiáng).基于粒子群優(yōu)化算法在不規(guī)則件排樣中的應(yīng)用［J］.中國(guó)機(jī)械工程，2010，21(17):2050-2052，2069.Liang Lidong，Zhong Xiangqiang.Application of Particle Swarm Optimization for Solving Irregular Parts Nesting Problem［J］.China Mechanical Engineering，2010，21(17):2050-2052，2069.