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

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

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

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

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

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

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

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

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

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

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

1 問(wèn)題提出

1.1問(wèn)題的描述

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

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

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

1.2非凸多邊形的NFP處理

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

圖1 NFP生成過(guò)程示意圖Fig.1 The illustration of creating NFP

圖2 相鄰凹點(diǎn)分割過(guò)程Fig.2 Splitting process of the polygon with nearby concave points

1.3基于NFP的堆場(chǎng)布局描述

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

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

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

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

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

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

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

(1)

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

2.3選擇算子

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

(2)

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

2.4交叉與變異算子

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

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

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

2.5堆場(chǎng)布局優(yōu)化過(guò)程

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

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

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

3 試驗(yàn)與分析

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

圖5 中間產(chǎn)品放入堆場(chǎng)示意圖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é)果對(duì)比

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

4 結(jié) 語(yǔ)

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

[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ī)則零件自動(dòng)優(yōu)化排樣算法的研究[D].哈爾濱：哈爾濱理工大學(xué)計(jì)算機(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] 張志英，楊克開(kāi)，于瑾維.面向船體分段建造的二維不規(guī)則空間調(diào)度方法[J].上海交通大學(xué)學(xué)報(bào)，2012，46(4)：651-656.

[8] 王蕾，張志英.基于規(guī)則的船體曲面分段空間調(diào)度方法[J].上海交通大學(xué)學(xué)報(bào)，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] 張志英，楊克開(kāi)，于瑾維，等.改進(jìn)粒子群算法的動(dòng)態(tài)空間調(diào)度方法[J].哈爾濱工程大學(xué)學(xué)報(bào)，2009，30(12)：1344-1350.

[12] 馬少輝，王景秋，陸春霞，等.動(dòng)態(tài)空間調(diào)度的混合遺傳算法[J].運(yùn)籌與管理，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

國(guó)家自然科學(xué)基金資助項(xiàng)目(51475301)

申興旺(1992—)，男，河南林州人，碩士研究生，研究方向?yàn)橹悄苤圃炫c測(cè)控.E-mail：814457915@qq.com

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