李曉君　謝新連

(大連海事大學綜合運輸研究所　大連　116026)

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

李曉君謝新連

(大連海事大學綜合運輸研究所大連116026)

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

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

李曉君 (1988- ):男，博士生，主要研究領域為交通運輸規(guī)劃與管理

0引言

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

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

1模型建立

1.1基本假設

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

1.2競爭行為的時間約束

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

因服務對象存在差異性，ti的表達式不同，軍艦、油田設備維修點的ti求法如下.

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

(1)

式中：Vt1為拖船設計航速，kn；Vt2為拖船拖帶故障軍艦或設備時的航速,kn；Vt3為軍艦設計航速,kn.

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

ti≤

(2)

式中：rt為拖船費,萬元/h；rb為半潛維修船費,萬元/h；rs為設備(如鉆井平臺)小時租金,萬元/h.

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

1.3模型建立

目標函數(shù)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

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

通過上面模型可得出半潛維修船?？扛?，但上式求解的基本前提是，所有半潛維修船均在?？扛弁２创?，而實際中往往會因運輸或維修任務，不能保證半潛維修船均在港，在這種情況下，在港半潛維修船應至少保證對軍艦維修點的覆蓋.

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

p+q=k

(10)

因維修任務是隨機的，p艘半潛維修船對應的港口是隨機的，在這種情況下q艘半潛維修船要能夠保障對軍艦維修點的重點覆蓋.就必須滿足如下條件：

(11)

式中：Yi,j=1，當dij≤Vtj，否則為0.

1.4模型求解

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

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

2算例與分析

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

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

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

通過觀察比較可知，青島、寧波、?？?地的岸基維修廠分別距離軍艦維修區(qū)A(i= 1，2，3)最近，煙臺、深圳的岸基維修廠分別距離油田設備維修去B(i= 4，5)最近，它們與半潛維修在軍艦、油田設備維修上形成競爭關系，式(7)中mindij見表2.

表2　min dij

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

表3　Vtj值

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

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

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

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

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

2.3最優(yōu)解確定

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

表5　k與p關系

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

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

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

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

3結(jié)束語

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

參 考 文 獻

[1]謝新連,?；菰?馬夢知.自航式半潛維修船[P].中國,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]李東,晏湘濤,匡興華.考慮設施失效的軍事物流配送中心選址模型[J].計算機工程與應用,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]李曉君.半潛船運輸組織與成本效益分析[D].大連：大連海事大學,2013.

中圖法分類號：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

*高等學校博士學科點專項科研基金課題(批準號：20102125110002)、中央高校基本科研業(yè)務費專項資金(批準號：3132013320)資助