基于兩階段算法的半潛維修船功能艙室布局*

趙瑞嘉，謝新連，趙家保

(1. 大連海事大學 綜合運輸研究所， 遼寧 大連 116026； 2. 大連海事大學 物流研究院， 遼寧 大連 116026)

隨著國家利益向遠海方向拓展，船舶或大型海洋工程設(shè)備在海上航行或作業(yè)頻繁，發(fā)生故障的風險也隨之增大。當船舶或大型海洋工程設(shè)備的故障發(fā)生于遠離岸基的水域且不適合長距離拖帶時，運用半潛船將其運至岸基維修逐漸成為主要手段，但該方法存在費時、費力、費用昂貴的缺點。為保障我國遠海權(quán)益，實現(xiàn)船舶與海洋工程設(shè)備的維修工作由岸基向遠海拓展，在一定程度上縮短其上岸維修的時間、降低費用和風險，提高運輸或生產(chǎn)作業(yè)效率，需加快發(fā)展遠海維修保障體系建設(shè)。自航式半潛維修船作為遠海維修保障體系建設(shè)的核心內(nèi)容之一，是基于集成創(chuàng)新理念設(shè)計的集高技術(shù)與多功能于一體的新型船[1-2]。該新型船主要應用于遠離岸基的海域，可為故障船舶或大型海洋工程設(shè)備提供技術(shù)支持、遠海獨立維修服務以及長距離運輸?shù)取Ｓ捎诎霛摯哂袑掗熂装?、重大件運輸?shù)忍攸c，提出以半潛船體為載體設(shè)計自航式半潛維修船?？紤]到維修以及備件庫存能力對這類新型船設(shè)計的重要程度[3]，合理布局維修艙、壓載艙等功能艙室是一個關(guān)鍵問題。

關(guān)于布局問題，Ahmadi等[4]通過設(shè)計框架分析并歸納了各領(lǐng)域的多層設(shè)施布局問題的特征及解決方法，主要有遺傳算法[5]、規(guī)劃求解與粒子群相結(jié)合算法[6]、多階段算法[7]、魯棒優(yōu)化[8]等。目前船舶艙室布局的研究大致從兩個方向出發(fā)：一是考慮艙室與全船的位置關(guān)系，建立全船各區(qū)域的位置評價模型，處理全船范圍內(nèi)的艙室分組與布局[9]；二是根據(jù)艙室之間的聯(lián)系，以相對位置關(guān)系為目標處理小范圍內(nèi)艙室布局[10]。也存在綜合考慮以上兩方面進行研究的方法[11-12]。本文針對自航式半潛維修船的維修艙、壓載艙等功能艙室布局問題，借鑒自航式半潛船船體特征，在保證船舶安全、技術(shù)可行的前提下，建立半潛維修船功能艙室布局優(yōu)化模型，設(shè)計貪婪取走算法與規(guī)劃求解相結(jié)合的方法解得半潛維修船功能艙室優(yōu)化布局方案。

1 半潛維修船功能艙室布局優(yōu)化模型

半潛維修船功能艙室布局問題研究是為了尋找最優(yōu)的功能艙室布局方案，其核心是選擇最優(yōu)的維修艙位置。優(yōu)化設(shè)計的目標是在設(shè)計規(guī)范及相關(guān)理論知識的基礎(chǔ)上，使維修艙具有最大的艙室空間、最高的艙室鄰接性、最近的維修作業(yè)區(qū)位置。為便于表示，建立船舶坐標系：以尾垂線與基平面的交點為坐標原點o；基平面與中線面的交線為x軸，指向船首為正；尾垂線為z軸，向上為正；過坐標原點且垂直于xoz面的直線為y軸，指向右舷為正。

1.1 設(shè)計變量

有待布局的艙室I個，設(shè)置維修艙m個，為準確表述涉及的參數(shù)與變量，做出如下定義。

定義1將維修艙內(nèi)維修設(shè)備的質(zhì)量與維修艙內(nèi)以壓載水計量的滿艙質(zhì)量的比值記為維修設(shè)備質(zhì)量系數(shù)。

定義2將壓載艙的壓載質(zhì)量與其最大壓載量的比值記為壓載系數(shù)。

每個艙室布局為維修艙或壓載艙的集合記為μ。為了統(tǒng)一表示維修艙內(nèi)的維修設(shè)備質(zhì)量或壓載艙內(nèi)的壓載量，引入集合θ。兩個集合的表達式見式(1)、式(2)。

μ={μi|i=1,2,…,I}

(1)

θ={θi|i=1,2,…,I}

(2)

其中：μ為表征待布局艙室布局為維修艙或壓載艙的集合；θ為表征維修艙的維修設(shè)備質(zhì)量系數(shù)或壓載艙的壓載系數(shù)的集合；I為待布局艙室的數(shù)量；μi為0或1的變量，當i艙布局為維修艙時μi=1；當i艙布局為壓載艙時μi=0。當μi=1時，θi=α，α為維修設(shè)備質(zhì)量系數(shù)；當μi=0時，θi=β，β∈[0,1]為壓載系數(shù)。

1.2 目標函數(shù)

1.2.1 艙室的空間大小

維修艙的空間大小是影響維修作業(yè)能力的重要因素。布局為維修艙的艙室空間大小按式(3)計算。

(3)

式中：Qm為m個維修艙的空間大小總和；Qi為i艙的空間大小。

1.2.2 艙室之間的鄰接

艙室之間的鄰接是各種修船機械、機加工設(shè)備之間相互聯(lián)系、共同開展維修作業(yè)的基礎(chǔ)。采用各艙室之間距離的平均值表示m個維修艙之間的鄰接關(guān)系，見式(4)。

(4)

式中：dr表示m個維修艙之間的平均距離；xi，yi，zi(xj，yj，zj)分別表示i(j)艙室重心的x坐標、y坐標、z坐標；φ為艙室垂向距離難度系數(shù)。

1.2.3 艙室的全局位置

維修艙在全船的位置是影響修船機械、機加工零件能否便捷快速地運送至主甲板維修作業(yè)區(qū)的重要因素。采用m個艙室與主甲板維修作業(yè)區(qū)中心的距離的平均值表示布局的維修艙的全局位置優(yōu)劣，見式(5)。

(5)

其中：dg表示m個維修艙距主甲板維修作業(yè)區(qū)中心的距離的平均值；xc，yc分別為主甲板維修作業(yè)區(qū)中心的x與z坐標。

1.3 約束條件

由于船舶本身艙室空間有限，布局m個維修艙可能會導致壓載艙容緊張，影響船舶的潛浮能力與安全。考慮到規(guī)范要求一般半潛船應在規(guī)定的風、浪外界環(huán)境條件下進行半潛作業(yè)，如基本無浪的平靜水域，或蒲氏風級、有義波高限制下的水域，此時船舶受風、浪影響產(chǎn)生的傾斜角度較?。灰虼嗽谶M行艙室的優(yōu)化布局時引入初穩(wěn)性高度值作為安全性的約束，按式(6)計算。

GM=KB+BM-KG-δ·GMf

(6)

式中：GM為經(jīng)自由液面修正后的初穩(wěn)性高度；KB為船舶浮心高度；BM為船舶橫穩(wěn)心半徑；KG為船舶重心高度；δ·GMf為自由液面對初穩(wěn)性高度的修正值。

通過Maxsurf軟件建立船體三維立體模型，KB、BM的值可由船體模型在相應吃水或排水量處的浮心與穩(wěn)心確定。KG的計算較為復雜，除空船、各種負載等質(zhì)量外，還需要重點計算維修艙與壓載艙的質(zhì)量，按式(7)計算。

(7)

δ·GMf只與自由液面的大小、船舶排水量有關(guān)。為便于計算，各艙室的自由液面大小取艙室不同水位下自由液面大小的平均值。故δ·GMf按式(8)計算。

(8)

1.4 模型建立

半潛維修船功能艙室布局優(yōu)化模型的目標是在滿足約束的條件下追求艙室空間最大、艙室之間的鄰接與艙室的全局位置最小。由于dr與dg屬于同一量級，因此引入權(quán)重因數(shù)ω1與ω2將兩個目標合并。若決策者強調(diào)維修艙的鄰接關(guān)系，則ω1>ω2；若決策者強調(diào)維修艙的全船位置，則ω1<ω2。因此目標函數(shù)可由式(9)表示。

maxF=Qm/(ω1dr+ω2dg)

(9)

約束條件為：

(10)

(11)

(12)

(13)

(14)

θi=μiα+(1-μi)β,?i=1,2,…,I

(15)

μi∈{0,1},?i=1,2,…,I

(16)

2 算法設(shè)計

上述模型類似于組合問題，當待布局艙室數(shù)I與布局的維修艙數(shù)量m較大時，會出現(xiàn)組合爆炸。如I=85，m=4時，可能的方案數(shù)多達2.02×106種。若將該問題按照0-1整數(shù)規(guī)劃問題求解，隨著待布局艙室數(shù)的增多，可選方案數(shù)2n將出現(xiàn)指數(shù)爆炸。因此參考貪婪取走啟發(fā)式算法的思想進行算法設(shè)計。貪婪取走啟發(fā)式算法的基本思想是依據(jù)貪婪準則從初始狀態(tài)一步一步向下搜索，直到找到滿足該問題的優(yōu)化解[13-14]。在半潛維修船功能艙室布局優(yōu)化模型中，設(shè)置初始解為全部待布局艙室，依據(jù)貪婪準則取走待布局艙室，貪婪準則的設(shè)定需考慮艙室的空間大小、艙室間的鄰接程度、艙室的全船位置等因素，按照目標函數(shù)值增量最大的規(guī)則設(shè)定。為保證求解方案的全局最優(yōu)，在該算法中加入局部搜索替代方法進行修正，即用已取走的待布局艙室代替保留的待布局艙室，通過比較目標函數(shù)值的變化決定是否替換。

為簡化計算，對模型進行分解，第一階段解決維修艙的布局問題，并將結(jié)果μ*傳遞至第二階段，第二階段解決壓載艙布局的合理性與安全性問題，通過GM值的計算返回第一階段判斷約束式(19)是否成立。

第一階段：

max{F(μ*)}

(17)

(18)

(19)

(20)

第二階段：

maxGM(μ*,θ*)

(21)

(22)

(23)

(24)

(25)

在對模型分解之后，第二階段可采用規(guī)劃求解程序?qū)崿F(xiàn)全局最優(yōu)解的計算。

下面說明該兩階段算法與原模型優(yōu)化解的等效性。對于式(12)，GM的計算與θ密切相關(guān)，而θ要滿足式(11)、式(13)、式(14)、式(16)。因此在第一階段根據(jù)貪婪取走算法每確定一個可能的功能艙室布局方案，就通過第二階段的模型探尋滿足式(19)的最優(yōu)壓載方案θ，即可說明這一功能艙室布局方案在安全性上是滿足要求的，屬于可行的方案。但該可行方案是否為最優(yōu)方案，還需通過式(17)確定。故半潛維修船功能艙室布局優(yōu)化模型求解算法步驟如下。

步驟1：初始化，令當前I個待布局艙室全部添加至維修艙集合，即m=I。

步驟2：計算維修艙質(zhì)量與壓載艙滿艙時質(zhì)量之和，若小于WB，轉(zhuǎn)步驟3，否則轉(zhuǎn)步驟4。

步驟3：計算目標函數(shù)值，并計算若取走某一艙室時目標函數(shù)值的增量，取走增量最大對應的n艙室。若存在相同的最大增量，則取走空間小的艙室，若為左右對稱的艙室，則先取走右舷艙室，轉(zhuǎn)步驟5。

步驟4：調(diào)用規(guī)劃求解程序求解第二階段模型，解得GM。若GM小于GM，轉(zhuǎn)步驟3，否則保存當前方案至可行方案集中，再轉(zhuǎn)步驟3。

步驟5：從維修艙集合中刪去n艙室，并將n艙室添加至壓載艙集合中。將當前維修艙集合中的某一艙室與壓載艙集合中的某一艙室置換，若目標函數(shù)值變大，則保存置換后的艙室集合，否則保留原艙室集合。令m=I-1，若m=0，轉(zhuǎn)步驟6，否則轉(zhuǎn)步驟2。

步驟6：選擇可行方案集中目標函數(shù)值最大的方案作為最優(yōu)方案，若可行方案集為空集，則無可行方案。

3 算例分析

以船長228 m、船寬43 m、型深13 m的半潛船體為例，空船及各種負載的質(zhì)量為28 869 t，重心坐標為(120.45 m,0.00 m,11.35 m)。船內(nèi)共有85個待布局艙室，采取由下而上、從后至前、先中間后左右舷的編號方式對85個艙室進行編號。各待布局艙室的重心坐標值、艙底z坐標值、自由液面面積對其傾斜軸線的橫向慣性矩等數(shù)據(jù)均已知。此外，模型中涉及的參數(shù)取值有α=0.6，φ=1.5，ω1=ω2=0.5。在算法之初，考慮維修艙內(nèi)作業(yè)高度需求，將待布局艙室中高度不超過2.5 m的艙室直接取走，添加至壓載艙集合，剩余61個待布局艙室。在保證船舶能安全下潛至設(shè)計的最大沉深(吃水27 m)的前提下，通過編程運算，共產(chǎn)生7組可行方案，如圖1所示。

圖1 可行方案目標值Fig.1 Objective value of feasible solutions

圖1中條形圖的每一條代表一種可行方案，其高度表示目標函數(shù)值F；折線為每一種可行方案對應的初穩(wěn)性高度值GM。其中：m=1表示選擇27號艙布局為維修艙；m=2表示選擇26～27號艙布局為維修艙；m=3表示選擇26～28號艙布局為維修艙；m=4表示選擇26～29號艙布局為維修艙；m=5表示選擇26～30號艙布局為維修艙；m=6表示選擇26～30、32號艙布局為維修艙；m=7表示選擇26～30、32～33號艙布局為維修艙。由圖1可知，在維修設(shè)備質(zhì)量系數(shù)α=0.6的情況下，目標函數(shù)值F隨著維修艙數(shù)量的增加而增加，但初穩(wěn)性高度值GM呈下降趨勢，即目標函數(shù)值越大，對應的初穩(wěn)性高度值越小。此時最優(yōu)方案為m=7，即布局7個維修艙，78個壓載艙，其變量值見表1。

表1 最優(yōu)方案的變量值

為了進一步探明維修設(shè)備質(zhì)量系數(shù)α對功能艙室布局方案的影響，采用變參數(shù)分析法對α做敏感性分析。當α變大時，即增加維修設(shè)備質(zhì)量，船舶整體的重力增大，緩解了壓載艙容的緊張局面，故可進一步增大維修艙的空間；反之，則需減小維修艙的空間，如圖2所示。區(qū)域Ⅰ為α=0.4、α=0.5時的可行方案，最優(yōu)方案為m=5；區(qū)域Ⅰ～Ⅱ為α=0.6時的可行方案，區(qū)域Ⅰ～Ⅲ為α=0.7時的可行方案，區(qū)域Ⅰ～Ⅳ為α=0.8時的可行方案，最優(yōu)方案均為m=7?？梢钥闯?，隨著α的增大，可行方案數(shù)不斷增多，但最優(yōu)的維修艙數(shù)量并不無限增大。選擇目標值較大且較為接近的三個方案m=5、m=6、m=7研究α對船舶初穩(wěn)性高度的影響，三種方案的布局情況如圖3所示。

圖2 α對m的影響分析 Tab.2 Analysis of effect in m by α

(a) m=5

(b) m=6

(c) m=7圖3 維修艙布局方案圖 Tab.3 Layout of maintenance and repair tanks

圖4為針對方案m=5、m=6、m=7的敏感性分析，可以看出初穩(wěn)性高度GM隨著α的增大而增大。但對于方案m=6，當α=0.5時，其壓載方案不能滿足規(guī)范要求的初穩(wěn)性高度0.5 m(圖4中虛線所示)最小限值；當α=0.4時，不存在可行的壓載方案。對于方案m=7，當α=0.4、α=0.5時，不存在可行的壓載方案。若裝載的維修設(shè)備質(zhì)量較大，如α=0.8，則不會影響船舶安全下潛至設(shè)計的最大沉深；若裝載的維修設(shè)備質(zhì)量較小，如α=0.4，則可能出現(xiàn)無可行的壓載方案或初穩(wěn)性高度值達不到規(guī)范要求，即船舶難以下潛或安全下潛至設(shè)計的最大沉深的情況。

圖4 α對GM的影響分析 Tab.4 Analysis of effect in GM by α

4 結(jié)論

為了解決半潛維修船功能艙室布局問題，建立技術(shù)可行前提下的半潛維修船功能艙室布局優(yōu)化模型，得到以下結(jié)論：

1)算例的結(jié)果表明該模型能夠較好地反映半潛維修船功能艙室布局問題。目標函數(shù)中考慮維修艙的艙室空間大小、艙室間的鄰接關(guān)系、艙室的全局位置這三種因素得到的維修艙布局方案較為合理，該目標函數(shù)能夠作為衡量艙室布局的目標。

2)通過對模型的分解，并設(shè)計了貪婪取走啟發(fā)式算法與規(guī)劃求解相結(jié)合的兩階段算法，能夠高效求解模型，避免陷入組合爆炸或指數(shù)爆炸的困境。

3)通過對維修設(shè)備質(zhì)量系數(shù)α的敏感性分析，探究了其對維修艙布局方案以及初穩(wěn)性高度的影響規(guī)律。

綜上所述，該方法為半潛維修船功能艙室布局優(yōu)化問題提供了一個有效途徑，可提高半潛維修船在功能艙室布局過程中決策的科學性。