李曉君　謝新連

(大連海事大學(xué)綜合運(yùn)輸研究所　大連　116026)

基于競(jìng)爭(zhēng)的半潛維修船最佳配備數(shù)量及選址*

李曉君謝新連

(大連海事大學(xué)綜合運(yùn)輸研究所大連116026)

摘要：為解決在競(jìng)爭(zhēng)條件下半潛船維修船的最佳配備數(shù)量及選址問(wèn)題，分析明確了半潛維修船的功能特點(diǎn).針對(duì)岸基維修的競(jìng)爭(zhēng)，建立了基于時(shí)間和經(jīng)濟(jì)影響的半潛維修船到達(dá)故障點(diǎn)的最遲時(shí)間約束式.在構(gòu)建的k-中值選址模型基礎(chǔ)上，增加了對(duì)軍艦維修區(qū)的重點(diǎn)覆蓋的條件約束，并設(shè)計(jì)了求解該模型的貪婪啟發(fā)式算法.結(jié)合實(shí)例，運(yùn)用局部搜索替換的改進(jìn)貪婪取走啟發(fā)式算法求解該模型，得出了我國(guó)半潛船維修船的最佳配備數(shù)量及選址.

關(guān)鍵詞：水路運(yùn)輸；設(shè)備選址；貪婪取走啟發(fā)式算法；半潛維修船；k-中值問(wèn)題

李曉君 (1988- ):男，博士生，主要研究領(lǐng)域?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理

0引言

自航式半潛維修船[1]具有自航、遠(yuǎn)航能力，航速12～15 kn，船上設(shè)置潛浮裝卸設(shè)施、大型起重設(shè)備、機(jī)械維修加工設(shè)備、救撈設(shè)備、維修保養(yǎng)工具、材料倉(cāng)庫(kù)等設(shè)施設(shè)備；船體能夠相對(duì)于滿載正浮狀態(tài)下潛一定深度，使維修或載貨甲板下潛至水面以下，以便將故障艦船等其他待修、待運(yùn)、待救援大型物體浮裝在甲板上.適用于艦船及其他海上工程結(jié)構(gòu)物近海、遠(yuǎn)洋維修、保養(yǎng)、救助、打撈、干拖運(yùn)輸.應(yīng)用于海上維修時(shí)，半潛維修船接近故障船舶之后，通過(guò)調(diào)整船內(nèi)設(shè)置的壓載水艙中的壓載水，把承載主甲板沉入水中，然后將待修船舶浮拖至主甲板上，或利用船吊將所要承運(yùn)、維修的故障艦船拖行至半潛維修船的維修或載貨甲板上，利用船上配備的維修力量，對(duì)故障艦船及時(shí)實(shí)施救援搶修.

半潛維修船不僅能夠承擔(dān)維修任務(wù)，而且可以承擔(dān)大件運(yùn)輸任務(wù).半潛維修船在港口間、遠(yuǎn)海海面布局的合理與否，關(guān)系到能否最大限度的發(fā)揮其維修、運(yùn)輸?shù)墓δ?本文旨在研究我國(guó)沿海港口半潛維修船的配備數(shù)量及其選址問(wèn)題.

1模型建立

1.1基本假設(shè)

設(shè)集合I,J分別為維修、運(yùn)輸服務(wù)需求點(diǎn)和?？扛鄣募?dij為需求點(diǎn)i至半潛船停靠港j的距離;k為半潛維修船的數(shù)量;ωj為i的權(quán)重系數(shù).根據(jù)服務(wù)對(duì)象的不同將I分為A,B,C,D4個(gè)集合，分別代表軍艦、油氣田設(shè)備、商船維修點(diǎn)和生產(chǎn)鉆井平臺(tái)等重大件的制造廠.為了解決問(wèn)題方便做了以下假設(shè)：(1)軍艦活動(dòng)區(qū)域、油氣田、商船活動(dòng)區(qū)域均以特定需求點(diǎn)代替，需求點(diǎn)為區(qū)域的中點(diǎn)；(2)當(dāng)一艘半潛維修船從開始執(zhí)行某任務(wù)直至完成期間，無(wú)論其他任務(wù)重大與否，都不再接受新任務(wù)；(3)對(duì)于每一需求點(diǎn)通過(guò)設(shè)定權(quán)重系數(shù)來(lái)決定其重要性，該權(quán)重系數(shù)主要考慮了軍事、維修、經(jīng)濟(jì)以及競(jìng)爭(zhēng)等因素；(4)考慮到半潛船造價(jià),以及自身維護(hù)費(fèi)用高，被選為?？扛鄣母劭趦H配備一艘半潛維修船.

1.2競(jìng)爭(zhēng)行為的時(shí)間約束

為獲得需求點(diǎn)的維修任務(wù)，半潛維修船與其他船舶或設(shè)施存在著競(jìng)爭(zhēng).半潛維修船在近海維修中的最大競(jìng)爭(zhēng)來(lái)源于岸基維修，即拖船拖帶回廠維修，因此客戶在維修故障設(shè)備時(shí),會(huì)考慮到二者維修的經(jīng)濟(jì)性及時(shí)間性，這里存在一個(gè)臨界的時(shí)間值ti(ti為客戶i所能接受的半潛維修船航行至維修故障設(shè)備需求點(diǎn)的最遲時(shí)間)，半潛維修船能夠在ti時(shí)間內(nèi)到達(dá)，則客戶會(huì)選擇半潛維修船，若不能到達(dá)，則由拖船拖帶回廠維修.

因服務(wù)對(duì)象存在差異性，ti的表達(dá)式不同，軍艦、油田設(shè)備維修點(diǎn)的ti求法如下.

1) 軍艦維修軍艦維修主要考慮時(shí)間性，即軍艦要求在最短的時(shí)間內(nèi)恢復(fù)正常作戰(zhàn)狀態(tài).若采用岸基維修，則軍艦恢復(fù)正常狀態(tài)時(shí)間由4部分組成：拖船航行至故障點(diǎn)時(shí)間、將故障軍艦拖回至維修船時(shí)間、維修時(shí)間、軍艦航行回原故障點(diǎn)時(shí)間.采用半潛維修船維修，故障軍艦恢復(fù)正常狀態(tài)時(shí)間由2部分組成：半潛維修船航行至故障點(diǎn)的時(shí)間和維修時(shí)間.假設(shè)故障軍艦在維修廠或在半潛維修船上進(jìn)行維修，所花費(fèi)時(shí)間是相同的，產(chǎn)生的費(fèi)用也是相等的.則軍艦維修的ti滿足：

(1)

式中：Vt1為拖船設(shè)計(jì)航速，kn；Vt2為拖船拖帶故障軍艦或設(shè)備時(shí)的航速,kn；Vt3為軍艦設(shè)計(jì)航速,kn.

2) 油田設(shè)備維修油田設(shè)備維修客戶主要考慮的是其經(jīng)濟(jì)成本，該成本包括：設(shè)備維修費(fèi)用、支付半潛維修船(拖船)運(yùn)輸費(fèi)用、因設(shè)備無(wú)法作業(yè)所損失的收益.另外，采用岸基維修，當(dāng)故障油田設(shè)備維修好后，需用拖船將設(shè)備再拖回至原位.因此油田設(shè)備維修ti滿足：

ti≤

(2)

式中：rt為拖船費(fèi),萬(wàn)元/h；rb為半潛維修船費(fèi),萬(wàn)元/h；rs為設(shè)備(如鉆井平臺(tái))小時(shí)租金,萬(wàn)元/h.

設(shè)備租金一般按照天計(jì)量，為得到更為精確的結(jié)果，本文轉(zhuǎn)換成小時(shí)計(jì)算.

1.3模型建立

目標(biāo)函數(shù)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

式中：若需求點(diǎn)i由j港的半潛維修船維修有xij=1，否則為0；若j被選為半潛維修船?？扛郏瑒tyj=1，否則為0；V為半潛維修船的航速.

該模型是一個(gè)k-中值選址模型，目標(biāo)函數(shù)式(1)是使總需求權(quán)距離最小，約束式(2)保證每個(gè)需求點(diǎn)都能被一艘半潛維修船服務(wù);約束式(3)為分配合理性約束，只有j被選為半潛維修船?？扛?，才能獲得需求;約束式(4)是所有被選為?？扛鄣臄?shù)量和為k，約束式(5)是指若j要服務(wù)A，B需求點(diǎn)i，半潛維修船要滿足從?？扛酆叫兄列枨簏c(diǎn)i的時(shí)間小于ti.

通過(guò)上面模型可得出半潛維修船停靠港，但上式求解的基本前提是，所有半潛維修船均在?？扛弁２创?，而實(shí)際中往往會(huì)因運(yùn)輸或維修任務(wù)，不能保證半潛維修船均在港，在這種情況下，在港半潛維修船應(yīng)至少保證對(duì)軍艦維修點(diǎn)的覆蓋.

設(shè)p為最大離港執(zhí)行任務(wù)的半潛維修船數(shù)量，q為在港半潛維修船數(shù)量，則有

p+q=k

(10)

因維修任務(wù)是隨機(jī)的，p艘半潛維修船對(duì)應(yīng)的港口是隨機(jī)的，在這種情況下q艘半潛維修船要能夠保障對(duì)軍艦維修點(diǎn)的重點(diǎn)覆蓋.就必須滿足如下條件：

(11)

式中：Yi,j=1，當(dāng)dij≤Vtj，否則為0.

1.4模型求解

該模型為k-中值選址模型，屬于NP問(wèn)題[3]，現(xiàn)在已有很多基于局部搜索的啟發(fā)式算法可以來(lái)解決這一問(wèn)題[4]，為盡快得到較高精度的滿意解，本文采用貪婪取走啟發(fā)式算法，該算法的基本思想是首先將所有的備選地址均設(shè)為中心，然后按照距離最近原則將需求點(diǎn)指派到中心，然后根據(jù)總權(quán)距離增加最小的規(guī)則取走一個(gè)中心，直到滿足要求為止.但每次貪婪得到的選址方案只是一個(gè)局部最優(yōu)組合，不能保證全局最優(yōu)，因此在該算法過(guò)程中加入局部搜索替代進(jìn)行修正[5-7]，即用已取走的點(diǎn)，來(lái)替代保留的點(diǎn)，比較目標(biāo)函數(shù)變化，然后決定是否替換[8].

具體步驟如下：(1) 將所有備選?？扛劬x定，形成選址集合X，將每個(gè)需求點(diǎn)指派給與運(yùn)輸距離最小的一個(gè)候選設(shè)施點(diǎn)，沒(méi)有獲得需求點(diǎn)的停靠港放入棄址集合Y；(2) 用式(7),(11)來(lái)判斷?？扛凼欠穹弦螅环系奶蕹?；(3)k=k-1，從X中選擇并取走一個(gè)設(shè)施點(diǎn)放入Y，需要滿足以下條件：假如將它取走并將它的需求點(diǎn)重新分配給就近?？扛酆螅軌驖M足式(7),(11)，并使總平均權(quán)距離增加量最?。?4) 應(yīng)用局部搜索法[9]，將目前取走點(diǎn)集合Y中的某一點(diǎn)與選址點(diǎn)集合X中的—個(gè)點(diǎn)置換，若目標(biāo)函數(shù)值Z有所改善，則保存置換后的選址點(diǎn)集合，否則，仍保存前一次的方案；(5) 重復(fù)步驟(3)、(4)，直到k值不變.

2算例與分析

2.1時(shí)間約束參數(shù)的確定

半潛維修船需求點(diǎn)包括軍艦維修區(qū)A、油氣田設(shè)備維修區(qū)B、商船維修區(qū)C、大件運(yùn)輸需求點(diǎn)D，其中A有北海海區(qū)、東海海區(qū)、南海海區(qū)(i= 1，2，3)，B有渤海油田、南海油田(i=4，5)，C為東海外側(cè)(i=6)，D有大連、煙臺(tái)、上海(i=7，8，9).大連、天津、煙臺(tái)、青島、上海、寧波、廈門、深圳、海口為九個(gè)備選?？扛?j=1，2，…，9).半潛維修船備選?？扛叟c需求點(diǎn)距離見(jiàn)表1.

表1　半潛維修船備選?？扛叟c需求點(diǎn)距離　n mile

通過(guò)觀察比較可知，青島、寧波、海口3地的岸基維修廠分別距離軍艦維修區(qū)A(i= 1，2，3)最近，煙臺(tái)、深圳的岸基維修廠分別距離油田設(shè)備維修去B(i= 4，5)最近，它們與半潛維修在軍艦、油田設(shè)備維修上形成競(jìng)爭(zhēng)關(guān)系，式(7)中mindij見(jiàn)表2.

表2　min dij

計(jì)算中半潛維修船的費(fèi)用、航速均參考半潛船.本文中V為12 kn，Vt1為12 kn，Vt2為6 kn，Vt3為25 kn，拖船為3艘4 440 kW，拖船費(fèi)為0.56元/(kW·h)，則rt為 0.756萬(wàn)元/h，rs為2.210萬(wàn)元/h，rb為 1.965萬(wàn)元/h[10]，依據(jù)式(1)、(2)可得tj值，表3.

表3　Vtj值

2.2權(quán)重系數(shù)確定

當(dāng)需求點(diǎn)同時(shí)對(duì)半潛維修船提出作業(yè)要求時(shí)，應(yīng)如何分配半潛維修船？也即每個(gè)需求點(diǎn)的需求重要性權(quán)重系數(shù)wj如何確定，本文主要是基于需求點(diǎn)自身的重要性和其作業(yè)任務(wù)可替代性考慮，并且認(rèn)為二者對(duì)于權(quán)重系數(shù)影響貢獻(xiàn)是等同的，則最終取二者的加權(quán)平均值作為需求點(diǎn)的需求重要性權(quán)重系數(shù).

1) 需求點(diǎn)自身重要性首先將需求重要性分為五個(gè)等級(jí)：不重要、重要、比較重要、非常重要、極其重要，每個(gè)等級(jí)賦值為：0,0.25,0.5,0.75,1.考慮到軍艦尤其是戰(zhàn)時(shí)，它對(duì)于國(guó)防有著極其重要作用因此賦值為1；對(duì)于海上油氣田上的設(shè)備和故障商船，一旦維修不及時(shí)都會(huì)發(fā)生設(shè)備損壞、人員傷亡事故，但考慮到油氣田發(fā)生溢油危害大，較之故障商船，海上油氣田上的故障設(shè)備維修更為重要，因此賦值為0.75，故障商船賦值為0.5；運(yùn)輸重大件會(huì)增加企業(yè)收入，是企業(yè)發(fā)展壯大的重要因素，因此賦值為0.25.

2) 替代性半潛維修船的作業(yè)，是可被其他船舶或設(shè)施所替代的，如浮船塢、拖輪、維修廠對(duì)半潛維修船維修作業(yè)的替代，半潛船對(duì)半潛維修船運(yùn)輸作業(yè)的替代等.因此根據(jù)其他船舶或設(shè)施對(duì)半潛維修船的可替代程度，將其劃分為五個(gè)等級(jí)：完全替代、可替代程度大、替代程度適中、替代程度小、幾乎不可替代，每個(gè)等級(jí)賦值為：0,0.25,0.5,0.75,1.軍艦執(zhí)行任務(wù)受損，特別是在演習(xí)或?qū)崙?zhàn)中，需要其能夠盡快恢復(fù)作戰(zhàn)能力，因此一般需要原地或就近維修，因此認(rèn)為幾乎不可替代為1.海上油氣田一般距離岸邊都比較近，在大多情況下，普通的拖輪或半潛船可將設(shè)備運(yùn)輸回岸上維修廠進(jìn)行維修，但有時(shí)因客戶需要對(duì)諸如鉆井平臺(tái)進(jìn)行原地維修，這樣的情形下，半潛維修船具有不可替代性；故障商船主要指在遠(yuǎn)海發(fā)生故障的船舶，拖輪等可采取將其拖回維修或用浮船塢進(jìn)行就地維修，當(dāng)商船故障嚴(yán)重需要遠(yuǎn)海就地維修時(shí)，半潛維修船也是具有不可替代性，由此看出油氣田設(shè)備和故障商船維修不能由拖輪等其他維修方式來(lái)完全替代，考慮到故障商船距離岸基較遠(yuǎn)將其拖帶回維修廠風(fēng)險(xiǎn)更高，因此認(rèn)為拖輪等其他設(shè)備在故障商船維修上對(duì)半潛維修船的替代程度比對(duì)油氣田設(shè)備維修的替代性程度小，所以故障商船和油氣田設(shè)備對(duì)應(yīng)的可替代系數(shù)分別為0.5,0.75；從運(yùn)輸作業(yè)上講半潛船可完全替代半潛維修船，因此在運(yùn)輸任務(wù)上半潛維修船對(duì)應(yīng)的可替代性為0.經(jīng)加權(quán)平均后得權(quán)重系數(shù)見(jiàn)表4.

表4　權(quán)重系數(shù)wj

2.3最優(yōu)解確定

利用改進(jìn)的貪婪取走啟發(fā)式算法可得出在不同半潛維修船數(shù)k下，k艘半潛維修船在沿海港口的分布，并得出能夠滿足軍艦維修的最大離港半潛維修船數(shù)p，其關(guān)系見(jiàn)表5所列.

表5　k與p關(guān)系

計(jì)算結(jié)果顯示要滿足所有需求，至少需要三艘半潛維修船.配備充足的半潛維修船必然會(huì)提高對(duì)整個(gè)海域故障船舶設(shè)備的維修保障，但數(shù)量的增多會(huì)造成維修能力的浪費(fèi)，因此數(shù)量應(yīng)適宜.表5顯示當(dāng)k=3時(shí)，允許任意一艘船舶離港作業(yè)的情況下，依然能夠保證對(duì)我國(guó)軍艦航區(qū)的覆蓋；k=5時(shí)，允許任意兩艘船舶離港作業(yè)的情況下，能夠保證對(duì)我國(guó)軍艦航區(qū)的覆蓋.在這兩種情況下半潛維修船對(duì)應(yīng)的?？扛垡约胺?wù)的需求點(diǎn)見(jiàn)表6、表7所列.

表6　半潛維修船的布局(k=3)

表7　半潛維修船的分布(k=5)

k=5時(shí)，在維修覆蓋能力方面要優(yōu)于k=3，但考慮到建造半潛維修船成本高，所以建議在我國(guó)沿海港口配備3艘，分別配備在煙臺(tái)、寧波和深圳，這樣可用最小的數(shù)量完成對(duì)需求點(diǎn)的覆蓋.

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

為確定半潛維修船的最佳配備數(shù)量及選址，建立了k-中值選址模型，首先模型充分考慮了岸基維修與海上維修的競(jìng)爭(zhēng)關(guān)系，通過(guò)模型確定出的半潛維修船布局，能夠使半潛維修船在與岸基維修競(jìng)爭(zhēng)中，顯現(xiàn)出經(jīng)濟(jì)及時(shí)間上的優(yōu)勢(shì).其次模型實(shí)現(xiàn)了對(duì)特殊需求點(diǎn)的重要覆蓋，極大提高對(duì)我國(guó)軍艦的維修保障能力，然后運(yùn)用改進(jìn)的貪婪取走啟發(fā)式算法進(jìn)行求解，該算法在加快求解速度的同時(shí)，也提高解的精度，最后結(jié)合我國(guó)港口及維修需求的分布情況，求解得到了半潛維修船的最佳配備數(shù)量及選址，建議在我國(guó)沿海配備3艘半潛維修船，煙臺(tái)、寧波和深圳3地各1艘.

參 考 文 獻(xiàn)

[1]謝新連,?；菰?馬夢(mèng)知.自航式半潛維修船[P].中國(guó),201310043450.2013-05-22.

[2]SáEZ-AGUADO J S,CAMELIA P T.Some heuristic methods for solving p-median problems with a coverage constraint[J].European Journal of Operational Research,2012,220:320-327.

[3]CORNUéJOLS G,NEMHAUSER G L,WOLSEY L A.The uncapacitated facility location problem[C].in:P.B.Mirchandani,R.L.Francis(Eds.),Discrete Location Theory,Wiley-Interscience,New York,1990：119-171.

[4]MLADENOVIC N,BRIMBERG J,HANSEN P,et al.The p-median problem:a survey of metaheuristic approaches[J].European Journal of Operational Research 2007,179:927-939.

[5]GHOSH D.Neighborhood search heuristics for the uncapacitated facility location problem[J]．European Journal of Operational Research,2003,150:150-162.

[6]RESENDE M G C,WERNECK R F.On the implementation of a swap-based local search procedure for the p-median problem[J].in:Richard E.Ladner (Ed.),Proceedings of the Fifth Workshop on Algorithm Engineering and Experiments (ALENEX’2003),SIAM,Philadelphia,2003:119-127.

[7]RESENDE M G C,WERNECK R C.A fast swap-based local search procedure for location problems[J].Annals of Operations Research,2007,150:205-230.

[8]李東,晏湘濤,匡興華.考慮設(shè)施失效的軍事物流配送中心選址模型[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(11):3-6.

[9]TEITZ M B,BART P.Heuristic methods for estimating the generalized vertex median of a weighted graph[J].Operations Research,1968,16:955-961.

[10]李曉君.半潛船運(yùn)輸組織與成本效益分析[D].大連：大連海事大學(xué),2013.

中圖法分類號(hào)：U692

doi:10.3963/j.issn.2095-3844.2015.01.007

收稿日期：2014-10-15

Study on the Best Equipped Number and Location of
Semi-submersible Vessel Maintenance Based Competition

LI XiaojunXIE Xinlian

(IntegratedTransportInstitute,DalianMaritimeUniversity,Dalian116026,China)

Abstract：To obtain the best equipped numbers and location of the semi-submersible vessel maintenance under competitive conditions, first, we analyzed the features of the semi-submersible vessel maintenance. Second, time constraints formula based on the impact of time and economy was developed for the competition of shore-based maintenance. Third, we added the constraints on the maintenance area of warship, and designed a greedy dropping heuristic algorithm on the basis of k-median location model. Finally, the best equipped numbers and location of the semi-submersible vessel maintenance were obtained using the improved greedy dropping heuristic algorithm with swap-based local search.

Key words：waterway transportation；faculty location；greedy dropping heuristic algorithm；semi-submersible vessel maintenance；k-median problems

*高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金課題(批準(zhǔn)號(hào)：20102125110002)、中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金(批準(zhǔn)號(hào)：3132013320)資助