基于竞争的半潜维修船最佳配备数量及选址*

李晓君　谢新连

(大连海事大学综合运输研究所　大连　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)资助