申興旺， 鮑勁松， 王 越， 殷士勇

(東華大學(xué) 機(jī)械工程學(xué)院， 上海 201620)

一種基于NFP非凸幾何的船舶中間產(chǎn)品堆場布局優(yōu)化方法

申興旺， 鮑勁松， 王 越， 殷士勇

(東華大學(xué) 機(jī)械工程學(xué)院， 上海 201620)

針對現(xiàn)代船舶制造過程中堆場空間資源浪費和布局不合理的現(xiàn)狀，提出了一種基于NFP(no-fit polygon)非凸幾何的船舶中間產(chǎn)品堆場布局優(yōu)化方法.該方法以不規(guī)則多邊形來表示結(jié)構(gòu)件輪廓，將非凸多邊形分割處理為簡單凸多邊形，用遺傳算法對結(jié)構(gòu)件在堆場中的排序進(jìn)行優(yōu)化.通過計算NFP實現(xiàn)船舶中間產(chǎn)品堆場的布局優(yōu)化，解決非凸幾何結(jié)構(gòu)件在堆場中的布局問題. 試驗結(jié)果表明，該方法可以有效提高船舶中間產(chǎn)品堆場的空間資源利用率.

船舶中間產(chǎn)品； 堆場布局優(yōu)化； 非凸幾何； NFP； 遺傳算法

在當(dāng)前船舶制造的模式結(jié)構(gòu)中，大多數(shù)船舶建造是將中間產(chǎn)品作為生產(chǎn)的基本單元.由于結(jié)構(gòu)件數(shù)量眾多、形狀不一且尺寸較大，通常在建造車間將中間產(chǎn)品建造成型后，經(jīng)過各種制造工藝在船臺將其合攏為整船，再對整船進(jìn)行一系列整修工作，才算完成整個建造流程. 由于船體較為龐大，中間產(chǎn)品的體積和質(zhì)量也較大，超過了一般車間生產(chǎn)的工件，而且在建造和存放的過程中不能疊放中間產(chǎn)品，故而這些中間產(chǎn)品在成型和合攏這兩步中要占用很大的場地空間，這種劃分出來臨時放置中間產(chǎn)品的區(qū)域即稱為“堆場”.

隨著造船工藝水平的不斷提高和建造規(guī)模的不斷擴(kuò)大，中間產(chǎn)品的堆場空間資源緊缺和堆場布局不合理已成為影響船舶建造生產(chǎn)效率的重要因素. 針對實際生產(chǎn)過程中存在的這一問題，研究船舶堆場布局的優(yōu)化方法是非常必要的.但這一問題較為復(fù)雜，不同生產(chǎn)過程的約束條件也大不相同，導(dǎo)致堆場結(jié)構(gòu)件在布局中無法達(dá)到最優(yōu). 堆場的布局問題可以簡化為排樣問題，以結(jié)構(gòu)件的形狀作為切入點，通過不規(guī)則多邊形解出其臨界多邊形(no-fit polygon， NFP)來解決排樣這一類問題. 目前，所采用的大多數(shù)NFP方法只能計算兩個凸多邊形的NFP，而非凸幾何形狀的NFP問題尚未得到解決. 在實際的船舶建造過程中，中間產(chǎn)品堆場中的結(jié)構(gòu)件形狀不規(guī)則，存在一些非凸幾何形狀的結(jié)構(gòu)件，增加了堆場布局的難度. 假如能對這些非凸結(jié)構(gòu)件進(jìn)行更為合理的擺放，這對提高船舶中間產(chǎn)品的堆場空間資源利用率以及減少資源浪費將是十分有利的.

文獻(xiàn)[1-2]針對二維不規(guī)則形狀的排樣問題做出了大量說明，同時指出對于此類問題的解決，NFP方法和遺傳算法是一個非常重要的研究方向. Song等[3]對建造過程進(jìn)行了分塊，將場地布局放在了重要位置，并提出一種在初級階段進(jìn)行場地布局的綜合方法，但這種方法的場地利用率不高.Caprace等[4]將三維布局問題簡化為三維裝箱問題，運用啟發(fā)式算法對空間進(jìn)行分配與調(diào)度優(yōu)化.為了對不規(guī)則排樣進(jìn)行簡化，將不規(guī)則多邊形轉(zhuǎn)化為矩形，使用最小包絡(luò)矩形算法進(jìn)行排樣[5]，但該算法在包絡(luò)時會產(chǎn)生大量空白區(qū)域.文獻(xiàn)[6]在最小矩形包絡(luò)算法的基礎(chǔ)上研究了多邊形兩兩組合的算法，該方法能有效提高板材利用率，但比較復(fù)雜，計算量較大.張志英等[7]通過最小包絡(luò)多邊形的方法，將復(fù)雜的分段形狀進(jìn)行最小包絡(luò)處理.王蕾等[8]運用了網(wǎng)格劃分法，將中間產(chǎn)品和堆場場地進(jìn)行網(wǎng)格劃分，并使用0-1矩陣來描述分段所占的場地空間，從而完成優(yōu)化過程.文獻(xiàn)[9-10]提出了基于遺傳算法的排樣方法，此方法的質(zhì)量不高，效率尚待提高. 張志英等[11]對粒子群算法進(jìn)行了改進(jìn)，優(yōu)化了中間產(chǎn)品調(diào)度序列，效果良好.馬少輝等[12]從遺傳算法出發(fā)，對調(diào)度序列進(jìn)一步優(yōu)化，并進(jìn)行了算法驗證，其利用率尚有提升空間. 縱觀國內(nèi)外研究現(xiàn)狀，NFP方法在解決排樣問題方面的應(yīng)用很多，但將其結(jié)合遺傳算法應(yīng)用于中間產(chǎn)品堆場布局優(yōu)化中的研究很少，將這種方法加以改進(jìn)和優(yōu)化，可以有效解決船舶中間產(chǎn)品堆場空間資源利用率低下的問題.

1 問題提出

1.1問題的描述

目前，針對堆場布局優(yōu)化的研究還比較少，主要是由于船舶堆場中的約束條件眾多，優(yōu)化過程相對復(fù)雜，且效果不明顯. 對中間產(chǎn)品堆場中存放的不規(guī)則結(jié)構(gòu)件進(jìn)行合理布局設(shè)計，首先可以忽略三維結(jié)構(gòu)件的高度信息，投影到二維平面中，簡化為二維排樣問題，從而降低研究難度. 對于形狀較為規(guī)則的結(jié)構(gòu)件的優(yōu)化已達(dá)到一定程度，而對于形狀不規(guī)則尤其是非凸幾何的結(jié)構(gòu)件，由于布局過程較為復(fù)雜，優(yōu)化效果不太理想，還存在一定的提升空間，因此具有較大的研究價值. 對于此類結(jié)構(gòu)件，可以采用求解其NFP方法來進(jìn)行處理.

NFP的研究已有幾十年了，其對于解決不規(guī)則的幾何多邊形的碰撞重疊問題而言是一個很有效的方法. NFP的概念最先是由Albano和Sapuppo[13]提出的，它很好地確定了兩個多邊形的相對位置關(guān)系，而且對兩個不規(guī)則的多邊形提供了一系列的可能位置，這些位置之間正好接觸而不會重疊. NFP方法在許多圖形處理的相關(guān)領(lǐng)域都得到了很好的應(yīng)用，也可用于堆場布局優(yōu)化，以解決不規(guī)則形狀結(jié)構(gòu)件的擺放問題.

對于兩個不同的多邊形A和B，它們之間的NFP(簡寫為NFPAB)可以作如下定義：多邊形A是固定住的，然后在多邊形B上選擇出一個參考點P，確定一個初始位置，將多邊形B沿著多邊形A做環(huán)繞一周的運動. 在環(huán)繞過程中，多邊形B上至少需要有一點和A的邊保持一個正好接觸的狀態(tài)，在此過程中多邊形B不能進(jìn)行旋轉(zhuǎn)操作. 其中，在多邊形B上選擇的參考點P環(huán)繞一圈的運行軌跡就稱為NFPAB，即多邊形B相對于A位置的臨界多邊形. NFP的生成過程如圖1所示，兩個多邊形始終保持恰好接觸但不重疊.

1.2非凸多邊形的NFP處理

對于非凸幾何多邊形NFP處理，目前多采用分割法，即將非凸多邊形做凸化處理，簡單來說就是將其分割為凸多邊形. 在進(jìn)行分割處理后，多邊形的個數(shù)越少，復(fù)雜度將會越低，計算效率會越高. 本文所采用的凸化處理方法如下所述：從非凸多邊形的一個頂點開始，沿著一個方向依次判斷這個頂點是否為凹點，并進(jìn)行記錄，直到把所有頂點判斷完畢；然后將第一個凹點和第二個凹點相連接之后做分割，第三個凹點和第四個相連，依次進(jìn)行分割直到最后一個凹點. 若此非凸多邊形只存在唯一的凹點，則取此凹點較近的一個對角線進(jìn)行分割，最終使其凸化. 如果凹點的數(shù)目為大于1的奇數(shù)，則將最后一個凹點與第一個凹點相連接進(jìn)行分割. 然而，經(jīng)過第一次的凹點處理分割之后，特殊情況下可能仍存在凹點(例如圖2，連接P2和P5進(jìn)行分割之后明顯還有凹點P2).對于這種情況，需要做進(jìn)一步的處理，即需要重新查看每個分割后的多邊形是否還有凹點，然后重復(fù)之前的步驟，從而可將非凸多邊形完全分割為凸多邊形.

圖1 NFP生成過程示意圖Fig.1 The illustration of creating NFP

圖2 相鄰凹點分割過程Fig.2 Splitting process of the polygon with nearby concave points

1.3基于NFP的堆場布局描述

在排樣問題當(dāng)中，NFP可以給出接觸但不重疊的可能位置，這已成為一種處理二維不規(guī)則多邊形的基本方法. 同樣地，NFP方法也可以應(yīng)用于堆場布局問題. 對于堆場中形狀不規(guī)則的結(jié)構(gòu)件，尤其是非凸幾何形狀的多邊形，其給堆場布局優(yōu)化帶來了很大難度，非凸的部分空間不能被利用，從而造成空間資源浪費，若能對這些空間合理布局，則利用率將得到提升. 具體處理過程是：首先判斷是否為非凸幾何形狀，若是，則進(jìn)行上文的凸化處理，分割為凸多邊形；其次計算兩個結(jié)構(gòu)件的NFP，以保證兩個結(jié)構(gòu)件在堆場中不重疊，依次計算隨后放入的結(jié)構(gòu)件與之前多邊形的NFP，直到所有結(jié)構(gòu)件放入為止. 對于計算出的NFP，確定其所占面積足夠小，這樣布局出來的結(jié)構(gòu)件就可以占用更小的空間，相當(dāng)于提高了堆場空間的利用率. 將NFP方法運用于堆場布局過程，這種處理方法是十分有效的，也有利于提高船舶建造的生產(chǎn)效率.

2 基于GA的NFP堆場布局優(yōu)化方法

2.1結(jié)構(gòu)件編碼方法

我曾經(jīng)也為生在偏僻的農(nóng)村而感到命運不公，力不從心，總是在困境中苦苦掙扎。在讀書的時候，當(dāng)我看到班上城市同學(xué)身上那種優(yōu)越感，也曾失落過。

一條染色體代表一種布局方案，在進(jìn)行染色體編碼設(shè)計時，采用十進(jìn)制編碼，將待布局結(jié)構(gòu)件的順序號作為染色體的編碼. 假設(shè)待布局結(jié)構(gòu)件有9個，則隨機(jī)選擇的其中一條染色體編碼可為<6， 2， 3， 9， 5， 1， 8， 4， 7>.

2.2適應(yīng)度函數(shù)

設(shè)計適應(yīng)度函數(shù)時采用以結(jié)構(gòu)件的布局順序進(jìn)行堆場布局，將布局后的總面積利用率作為評價染色體的適應(yīng)度，即適應(yīng)度函數(shù)如式(1)所示.

(1)

式中:Ai為第i個已布局結(jié)構(gòu)件的面積；Ay為需要進(jìn)行布局的堆場面積；n為已布局結(jié)構(gòu)件的個數(shù).

2.3選擇算子

設(shè)種群規(guī)模為M，在某一代種群中，它的第i條染色體的適應(yīng)度值為fi，則該種群中所有個體的適應(yīng)度如式(2)所示.

(2)

將fi所占F的比例組成一個輪盤，隨機(jī)轉(zhuǎn)動來進(jìn)行輪盤區(qū)域的選擇，輪盤的指針落在fi所占的區(qū)域，則選中此染色體i.

2.4交叉與變異算子

交叉算子采用線性順序交叉方法(linear-order crossover， LOX)來實現(xiàn)交叉過程，該方法的優(yōu)點是對染色體片段間的相對位置可較好保留. 兩條染色體的交叉過程如圖3所示.

圖3 兩條染色體的交叉過程Fig.3 The crossover process of two chromosomes

變異的操作：隨機(jī)選取染色體中的兩個互不相同的位置，對這兩個位置的數(shù)字進(jìn)行交換完成變異操作.對于<6， 2， 3， 9， 5， 1， 8， 4， 7>這條染色體，互換第二個和最后一個位置，則變異之后的染色體變?yōu)?6， 7， 3， 9， 5， 1， 8， 4， 2>.

2.5堆場布局優(yōu)化過程

對船舶的中間產(chǎn)品堆場進(jìn)行布局優(yōu)化，將結(jié)構(gòu)件放入堆場中進(jìn)行擺放，使得堆場的空間資源利用率達(dá)到最優(yōu). 在堆場布局優(yōu)化過程中，可按照如下步驟來完成.(1)對結(jié)構(gòu)件進(jìn)行預(yù)處理，將不規(guī)則的幾何形狀(包括非凸幾何多邊形)轉(zhuǎn)化為簡單多邊形；(2)通過使用遺傳算法，對堆場布局進(jìn)行優(yōu)化，產(chǎn)生一個接近最優(yōu)的結(jié)構(gòu)件擺放順序，這一步非常重要，擺放次序的合理與否對堆場的空間利用率產(chǎn)生直接影響；(3)將擺放順序中的第一個結(jié)構(gòu)件擺放于堆場中，并根據(jù)左下原則置于堆場的左下角，然后按順序取第二個結(jié)構(gòu)件，并計算出這兩個結(jié)構(gòu)件之間的NFP；(4)對NFP上的位置是否最優(yōu)進(jìn)行評估，計算上步得到的NFP面積，使其盡量小，確定最優(yōu)的布局?jǐn)[放方法；(5)對前兩個結(jié)構(gòu)件進(jìn)行整理優(yōu)化，合成一個新的多邊形，再計算第三個結(jié)構(gòu)件與新的多邊形之間的NFP；(6)繼續(xù)按順序取下一個結(jié)構(gòu)件，重復(fù)上述過程直到在堆場中將所有結(jié)構(gòu)件擺放完畢.

本文所用的NFP方法進(jìn)行堆場布局優(yōu)化過程如圖4所示.

圖4 堆場布局優(yōu)化過程Fig.4 The process of yard layout optimization

3 試驗與分析

為證明本文所述堆場布局優(yōu)化方法的有效性，通過以下實例進(jìn)行驗證. 選取一個矩形堆場空間，將實際生產(chǎn)過程中的幾個船舶中間產(chǎn)品放入堆場中，進(jìn)行堆場布局，首要保證所有中間產(chǎn)品均能放入堆場中，如圖5所示，有9個中間產(chǎn)品將要放入堆場中.

圖5 中間產(chǎn)品放入堆場示意圖Fig.5 The illustration of allocating intermediate products into a yard

方法1：采用最小包絡(luò)矩形法，布局優(yōu)化結(jié)果如圖6所示.

圖6 最小包絡(luò)矩形法布局優(yōu)化結(jié)果Fig.6 The improved layout result by minimum envelope rectangle

方法2：采用只考慮凸多邊形的方法，布局優(yōu)化結(jié)果如圖7所示.

圖7 只考慮凸多邊形的布局優(yōu)化結(jié)果Fig.7 The improved layout result only concerning convex polygons

方法3：采用考慮非凸多邊形的方法，布局優(yōu)化結(jié)果如圖8所示.

上述3種方法的布局結(jié)果分析如表1所示.

表1 布局結(jié)果對比

從表1可以看出，方法3在堆場空間利用率上得到了大幅提升. 相對于方法1，最小包絡(luò)矩形處理過程簡單，但對于大尺寸不規(guī)則結(jié)構(gòu)件，包絡(luò)矩形中的邊角空間有很大浪費，空間利用率不高. 方法2的空間利用率要稍好一些，處理過程相對方法3簡單，但未能對非凸多邊形合理利用. 方法3將非凸多邊形凸化處理，用遺傳算法對布局的結(jié)構(gòu)件序列進(jìn)行優(yōu)化，得到了合理的堆場布局，空間利用率大大提升. 由案例分析發(fā)現(xiàn)，基于NFP的非凸幾何將對堆場布局優(yōu)化過程產(chǎn)生重大影響，合理解決會對空間資源緊缺的船舶堆場提供幫助.

4 結(jié) 語

本文對非凸幾何形狀的結(jié)構(gòu)件在船舶中間產(chǎn)品堆場中的布局優(yōu)化提供了一種解決方法，通過計算不規(guī)則多邊形的NFP，在保證不重疊的基礎(chǔ)上將結(jié)構(gòu)件在堆場中進(jìn)行合理放置.通過遺傳算法對結(jié)構(gòu)件的放置順序進(jìn)行優(yōu)化，從而達(dá)到在滿足布局要求的情況下提高場地利用率的目的. 采用實例進(jìn)行分析驗證，通過與其他方法比較可以發(fā)現(xiàn)，本方法的堆場空間利用率比最小包絡(luò)矩形法和僅考慮凸多邊形的高，且可以在堆場中放入更多的結(jié)構(gòu)件. 合理利用非凸幾何，對進(jìn)一步提高堆場空間利用率和布局的最優(yōu)化具有顯著影響. 但該方法的計算效率尚待加強(qiáng)，暫不能應(yīng)對大規(guī)模的場景，否則會顯著影響效率.同時本文提出的方法在驗證過程中缺少約束，情景環(huán)境較為理想，實際上這些約束因素會對真實的堆場布局過程造成影響，后續(xù)研究將從這方面著手，進(jìn)一步提高本方法的實用性和計算效率.

[1] HOPPER E，TURTON H. A review of the application of meta-heuristic algorithms to 2D strip packing problems[J]. Artificial Intelligence Review， 2001，16(4)： 257-300.

[2] KATHRYN A D， WILLIAM B D. Solution approaches to irregular nesting problems [J]. European Journal of Operational Research， 1995，84(3)：506-521.

[3] SONG Y J， WOO J H. New shipyard layout design for the preliminary phase & case study for the green field project[J]. International Journal of Naval Architecture and Ocean Engineering， 2013， 5(1)： 132-146.

[4] CAPRACE J D， PETCU C， VELARDE M G. Optimization of shipyard space allocation and scheduling using a heuristic algorithm [J]. Journal of Marine Science and Technology， 2013，18(3)：404-417.

[5] 陳小雨.二維不規(guī)則零件自動優(yōu)化排樣算法的研究[D].哈爾濱：哈爾濱理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，2012.

[6] ELKERAN A. A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering[J]. European Journal of Operational Research， 2013，231(3)：757-769.

[7] 張志英，楊克開，于瑾維.面向船體分段建造的二維不規(guī)則空間調(diào)度方法[J].上海交通大學(xué)學(xué)報，2012，46(4)：651-656.

[8] 王蕾，張志英.基于規(guī)則的船體曲面分段空間調(diào)度方法[J].上海交通大學(xué)學(xué)報，2009，43(11)：1709-1714.

[9] FISCHER A D， DAG L H. Employing subgroup evolution for irregular-shape nesting[J]. Journal of Intelligent Manufacturing， 2004，15(2)：187-199.

[10] FRANCIS E， TAY H， CHONG T Y. Pattern nesting on irregular-shaped stock using genetic algorithms[J]. Engineering Applications of Artificial Intelligence，2002， 15(6)：551-558.

[11] 張志英，楊克開，于瑾維，等.改進(jìn)粒子群算法的動態(tài)空間調(diào)度方法[J].哈爾濱工程大學(xué)學(xué)報，2009，30(12)：1344-1350.

[12] 馬少輝，王景秋，陸春霞，等.動態(tài)空間調(diào)度的混合遺傳算法[J].運籌與管理，2013，22(2)：99-104.

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

(責(zé)任編輯：杜佳)

AMethodforImprovingtheYardLayoutofNon-convexGeometryShipbuildingIntermediateProductsBasedonNFP

SHENXingwang，BAOJinsong，WANGYue，YINShiyong

(College of Mechanical Engineering， Donghua University， Shanghai 201620， China)

Aiming at the situation of the waste of yard space and unreasonable layout problems during modern shipbuilding process， an optimized method based on NFP(no-fit polygon) is proposed to improve the layout yard of concave intermediate shipbuilding products. This method represents the outlines of parts with irregular polygons， divides concave polygon into several simple convex polygons， uses genetic algorithm to improve the order of the parts， and optimizes the layout by calculating the NFP to resolve the layout problems of non-convex parts in a yard. The experimental results show that this method can efficiently elevate the utilization ratio of the space resources of the shipbuilding intermediate products yard.

shipbuilding intermediate products； yard layout optimization； non-convex geometry； NFP； genetic algorithm

TH 181

A

1671-0444 (2017)04-0478-06

2016-12-28

國家自然科學(xué)基金資助項目(51475301)

申興旺(1992—)，男，河南林州人，碩士研究生，研究方向為智能制造與測控.E-mail：814457915@qq.com

鮑勁松(聯(lián)系人)，男，副教授，E-mail：bao@dhu.edu.cn