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

李曉君　謝新連

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

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

李曉君謝新連

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

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

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

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

0引言

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

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

1模型建立

1.1基本假設

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

1.2競爭行為的時間約束

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

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

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

(1)

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

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

ti≤

(2)

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

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

1.3模型建立

目標函數

(3)

(4)

(5)

(6)

(7)

(8)

(9)

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

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

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

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

p+q=k

(10)

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

(11)

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

1.4模型求解

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

具體步驟如下：(1) 將所有備選停靠港均選定，形成選址集合X，將每個需求點指派給與運輸距離最小的一個候選設施點，沒有獲得需求點的停靠港放入棄址集合Y；(2) 用式(7),(11)來判斷停靠港是否符合要求，不符合的剔除；(3)k=k-1，從X中選擇并取走一個設施點放入Y，需要滿足以下條件：假如將它取走并將它的需求點重新分配給就近停靠港后，能夠滿足式(7),(11)，并使總平均權距離增加量最小；(4) 應用局部搜索法[9]，將目前取走點集合Y中的某一點與選址點集合X中的—個點置換，若目標函數值Z有所改善，則保存置換后的選址點集合，否則，仍保存前一次的方案；(5) 重復步驟(3)、(4)，直到k值不變.

2算例與分析

2.1時間約束參數的確定

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

表1　半潛維修船備選停靠港與需求點距離　n mile

通過觀察比較可知，青島、寧波、海口3地的岸基維修廠分別距離軍艦維修區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]，依據式(1)、(2)可得tj值，表3.

表3　Vtj值

2.2權重系數確定

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

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

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

表4　權重系數wj

2.3最優解確定

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

表5　k與p關系

計算結果顯示要滿足所有需求，至少需要三艘半潛維修船.配備充足的半潛維修船必然會提高對整個海域故障船舶設備的維修保障，但數量的增多會造成維修能力的浪費，因此數量應適宜.表5顯示當k=3時，允許任意一艘船舶離港作業的情況下，依然能夠保證對我國軍艦航區的覆蓋；k=5時，允許任意兩艘船舶離港作業的情況下，能夠保證對我國軍艦航區的覆蓋.在這兩種情況下半潛維修船對應的停靠港以及服務的需求點見表6、表7所列.

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

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

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

3結束語

為確定半潛維修船的最佳配備數量及選址，建立了k-中值選址模型，首先模型充分考慮了岸基維修與海上維修的競爭關系，通過模型確定出的半潛維修船布局，能夠使半潛維修船在與岸基維修競爭中，顯現出經濟及時間上的優勢.其次模型實現了對特殊需求點的重要覆蓋，極大提高對我國軍艦的維修保障能力，然后運用改進的貪婪取走啟發式算法進行求解，該算法在加快求解速度的同時，也提高解的精度，最后結合我國港口及維修需求的分布情況，求解得到了半潛維修船的最佳配備數量及選址，建議在我國沿海配備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)、中央高校基本科研業務費專項資金(批準號：3132013320)資助