一種基于NFP非凸幾何的船舶中間產品堆場布局優化方法

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

(東華大學 機械工程學院， 上海 201620)

一種基于NFP非凸幾何的船舶中間產品堆場布局優化方法

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

(東華大學 機械工程學院， 上海 201620)

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

船舶中間產品； 堆場布局優化； 非凸幾何； NFP； 遺傳算法

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

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

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

1 問題提出

1.1問題的描述

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

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

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

1.2非凸多邊形的NFP處理

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

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

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

1.3基于NFP的堆場布局描述

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

2 基于GA的NFP堆場布局優化方法

2.1結構件編碼方法

我曾經也為生在偏僻的農村而感到命運不公，力不從心，總是在困境中苦苦掙扎。在讀書的時候，當我看到班上城市同學身上那種優越感，也曾失落過。

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

2.2適應度函數

設計適應度函數時采用以結構件的布局順序進行堆場布局，將布局后的總面積利用率作為評價染色體的適應度，即適應度函數如式(1)所示.

(1)

式中:Ai為第i個已布局結構件的面積；Ay為需要進行布局的堆場面積；n為已布局結構件的個數.

2.3選擇算子

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

(2)

將fi所占F的比例組成一個輪盤，隨機轉動來進行輪盤區域的選擇，輪盤的指針落在fi所占的區域，則選中此染色體i.

2.4交叉與變異算子

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

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

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

2.5堆場布局優化過程

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

本文所用的NFP方法進行堆場布局優化過程如圖4所示.

圖4 堆場布局優化過程Fig.4 The process of yard layout optimization

3 試驗與分析

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

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

方法1：采用最小包絡矩形法，布局優化結果如圖6所示.

圖6 最小包絡矩形法布局優化結果Fig.6 The improved layout result by minimum envelope rectangle

方法2：采用只考慮凸多邊形的方法，布局優化結果如圖7所示.

圖7 只考慮凸多邊形的布局優化結果Fig.7 The improved layout result only concerning convex polygons

方法3：采用考慮非凸多邊形的方法，布局優化結果如圖8所示.

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

表1 布局結果對比

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

4 結 語

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

[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] 陳小雨.二維不規則零件自動優化排樣算法的研究[D].哈爾濱：哈爾濱理工大學計算機科學與技術學院，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] 張志英，楊克開，于瑾維.面向船體分段建造的二維不規則空間調度方法[J].上海交通大學學報，2012，46(4)：651-656.

[8] 王蕾，張志英.基于規則的船體曲面分段空間調度方法[J].上海交通大學學報，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].哈爾濱工程大學學報，2009，30(12)：1344-1350.

[12] 馬少輝，王景秋，陸春霞，等.動態空間調度的混合遺傳算法[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.

(責任編輯：杜佳)

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

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

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

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