海上搜寻船舶分配问题优化研究

王 军，杨春林，王美蓉

(大连海事大学 交通运输工程学院， 辽宁 大连 116026)

0 引 言

当发生海难时，如何在最短的时间内制定出高效、科学的搜救方案，以减少人员伤亡和财产损失是众多学者在海上搜救领域致力于研究的问题。而海上搜救可分为海上搜寻与海上救助两大部分，同时海上搜寻往往是提供海上救助的前提，也是海上搜救整个过程中的关键环节，因此快速展开海上搜寻工作尤为重要。由于海上搜寻涉及很多不确定性因素，如目标海域位置与范围大小的确定、目标附近海域是否有可用于搜寻或救助的船舶、目标与停靠在港的专业搜救船舶以及空中搜寻救援基地的距离大小等，导致海上搜寻工作往往难度比较大。因此，决策人员如何分配搜寻船舶，以达到对给定海域以最短时间、用最少的船舶资源对其完成搜寻覆盖，是海上搜救领域的难题。

目前，针对海上搜救船舶选择与分配问题，LI Wei等[1]以现代决策理论和模糊数学评价为基础，提出了3种多目标优化搜救船舶选择方法(多属性加权和评价法、汉明距离法和模糊相似优先度法)，同时证明了3种方法的可行性，并给出了时间是影响船舶选择的主要因素；邢胜伟等[2]根据在获取船舶信息的前提下，将海上搜寻力量选择问题抽象为带有船舶总量约束的最优化问题，建立了船舶选择优化模型，并考虑在不同船舶数约束下,分析最优方案与成本之间的关系,进而确定船舶选择方案；于卫红等[3]基于船舶优选所考虑的主要因素，建立BP神经网络模型，并通过构建的模型确定影响船舶选择的各决策因素集的权重，进而确定优选方案；李岩等[4]以传统拍卖规则为基础，引入多智能体技术，提出了改进拍卖规则的多智能体海上搜寻任务分配方法，并通过仿真结果验证了该方法的有效性；胡宏启等[5]考虑在多子区域及多搜索主体的前提下，构建了以搜寻成功率最大为目标的模型，并验证了模型的可行性；王军等[6]依据目标在待搜寻海域内的概率分布情况，将待搜寻海域划分为若干子海域，并以目标在各子海域的概率分布大小确定待搜寻子海域的优先级关系，建立了以各子海域搜寻结束的时间期望总和最小为目标的搜寻船舶选择模型，并验证了模型的可行性。但是作者在其问题研究上没有考虑到搜寻船舶多次利用的问题，所得方案中的每艘船舶都只执行一个子海域的搜寻工作，即对某一子海域搜寻完毕后的船舶就不再参与其他子海域的搜寻工作。因此，笔者将重点针对文献[6]中没有考虑搜寻船舶多次利用问题进行优化改进。

综上所述，笔者将在文献[6]的基础上进一步优化研究，针对其假设的搜寻船舶对某一子海域搜寻结束后就不再继续参与其他子海域搜寻的局限性问题进行优化改进，研究以最短时间、使用最少的船舶资源条件完成对给定概率分布不同的多个子海域搜寻覆盖的船舶分配问题。

1 问题描述

由于在风、流等众多因素综合影响下，遇险目标位置发生漂移情况，以至于目标准确位置难以确定。尽管在现有技术条件下可以利用数值模型预测目标漂移轨迹，然而由于海况的复杂性，往往预测的目标位置与目标实际所在位置都存在一定偏差[7]。但可在分析估算目标漂移位置信息的基础上，利用总搜寻误差和搜寻安全系数推算出搜寻半径，进而确定搜寻海域[8]。因此，笔者将针对已确定的搜寻海域研究搜寻船舶的分配问题。

笔者在前人对经典包含概率、发现概率研究的基础上，假设已知目标存在于各待搜寻子海域的概率分布信息，即各搜寻子海域包含概率的情况。同时，通过利用现有的科技手段(船舶自动识别系统(AIS)[9]、船舶交通服务系统(VTS)[10]、船舶远程信息识别与跟踪系统(LRIT)[11]、中气导、船达通、船讯网等)将目标周边海域船舶及在港停靠的专业搜救船舶等信息快速显示并统计出来。如图1，是通过利用船讯网获取某时刻某港口区域所有的船舶数据(包括每艘船舶的位置、类型、状态、航速等详细信息)。在此基础上，研究制定派往概率分布情况不同的各子海域的船舶分配方案。在研究过程中，笔者将通过设计相关算法实现在概率分布越大的子海域选派出完成该海域搜寻覆盖时间越短的船舶，同时所设计的算法将实现研究重点考虑搜寻船舶多次利用的目的。

综合以上说明及描述，将在已确定概率分布不同的多个待搜寻子海域、有机会参与搜寻的船舶信息等前提下，以完成各子海域搜寻覆盖时间期望总和最小为目标，研究概率分布情况不同的多个子海域分配搜寻船舶的问题。

2 模型建立

2.1 模型假设

1)待搜寻子海域面积大小及目标在各子海域的概率已知；

2)对于面积相等的子海域，所设定的船舶容纳量相等；

3)有机会执行搜寻任务的船舶及其所在位置等信息已知；

4)目标在一定时间范围内存在于某子海域的概率大小不变；

5)有机会参与搜寻的船舶在当时的天气、海况等情况下航行不受限；

6)船舶不考虑搜寻过程中因自身性能等问题而导致不能搜寻的情况。

2.2 符号说明

设I、J、K分别为I={1,2,3，…，n}、J={1,2,3，…，m}、K={1,2,3，…，n}，符号说明如下所述：

2.3 船舶分配模型

由于本研究考虑到搜寻船舶是否满足执行多个子海域的搜寻工作问题，因此船舶Lj到达子海域Ai的时间Tji可分为两种情况：①当某搜寻船舶Lj在不满足执行多个子海域搜寻任务时，仅考虑搜寻船舶到达子海域需要的时间；②当Lj满足执行多个子海域的搜寻任务时，将计算出搜寻船舶Lj完成当前子海域搜寻覆盖的时间，同时需要加上航行到另一子海域的时间。因此，时间Tji可表示为：

(1)

考虑到每艘船舶到达各子海域的时间、单位时间内搜寻能力等存在差异的情况，故存在某搜寻船舶是否有机会参与搜寻任务(即船舶到达某子海域时，而在其前面已到达的船舶是否已完成该子海域搜寻覆盖的工作)的问题，为此引入决策变量：

(2)

基于以上说明与分析，搜寻船舶从时刻T0开始到完成搜寻覆盖子海域Ai需满足：

(3)

即：

(4)

因此，构建船舶分配的数学模型为：

(5)

s.t. ∑xj≤Mi(i∈I，j∈J)

(6)

其中，式(4)为完成各子海域搜寻覆盖的时间；式(5)为目标函数，即完成各子海域搜寻覆盖的时间期望总和；式(6)为子海域船舶容纳量限制，即参与子海域搜寻的船舶总数小于等于其船舶容纳量限制。

3 算法实现

针对笔者提出的船舶分配模型，在搜寻时间期望上采用了基于优先队列的算法来实现，并利用遗传算法找出最佳分配方案。

3.1 搜寻时间期望实现算法

为更清楚地说明与表示设计算法的实现过程，在此将对所要求的船舶分配方案进行简单地描述以及重新进行部分符号说明，具体如下所述：

3.1.1 方案描述

记搜寻方案为S，S是方案中每艘船舶所被分配的搜寻子海域表集合，设方案S一共有m艘船舶，则S表示为：

S={si|1≤i≤m}

(7)

式中：si是第i艘船舶需要搜寻的子海域表集合，设第i艘船参与搜寻的子海域有ni个，则si表示为：

si={p1,p2,…,pni}

(8)

第i艘船舶的第j个搜寻子海域可记为si(j)。如，s2={2,5,3}表示2号船舶依次搜寻编号为2、5、3的3个子海域，s2(1)=2表示2号船舶搜寻的第1个海域是 2号子海域。

3.1.2 符号表示

3.1.3 搜寻时间期望求解

记优先队列为Q，Q中的元素记为x，对优先队列Q的相关操作为：

1)Q.push(x)表示向Q中添加元素x；

2)x=Q.pop()表示取出Q中关键属性最小的元素并赋给x。

其中，x代表发生事件且由以下信息构成：①x.time表示发生事件的时间；②x.shipId表示事件发生的船的编号；③x.areaId表示事件发生的海域编号；④x.type表示事件的类型，即0表示船到达海域的事件；1表示船完成海域的搜寻任务的事件(如果还有任务未完成，船舶会继续搜寻下个子海域)。事件x可以表示为x={time,shipId,areaId,type}，位置依次表示相应属性。

方案的搜寻时间期望E(S)求解过程为：

2)则令u=Q.pop()，u代表下一个发生的事件。

3)如果u.type=0，表示船到达事件，根据u.time更新每个海域的搜寻进度；同时，船u.shipId立即开始搜寻任务。

4)如果u.type=1，表示船完成搜寻任务。

5)若Q非空，返回第2)步。

6)完成方案的搜寻过程后，判断每个海域的fini是否都为True，若存在有海域的fini为False，表示存在海域无法被搜寻完成，则令E(S)=∞。

7)输出搜索时间期望E(S)。

3.2 遗传算法搜索最佳方案设计

1)基因编码的设计，设船有m搜，区域有k个。本方法采用的基因编码格式为m×k的矩阵M∈Rm×k，并且矩阵M的每个元素mij取值都在0～1之间。

2)编码到方案的转换方法，即T：M→S如下：对于M的每一列数据，选取其中值最大的3个数。设第j列最大的3个数分别是mt1, j、mt2, j、mt3, j，则表示编号为t1、t2、t3的3艘船将被派去第j个区域。若第i艘船被派去搜索的区域的顺序是p1,p2,…,pni，则它们的基因满足：mi,p1>mi,p2>…>mi,pni。即基因值大小决定搜寻顺序，基因值大的海域优先搜寻。

3)遗传算法求解表达式为：

(9)

s.t. 0≤vi≤1

(10)

式中：v为矩阵M按照列优先向量化的向量，即v1=m1,1，v2=m2,1，以此类推。

4)遗传算法求解采用MATLAB的ga函数进行求解。

4 算例分析

假设某海域突发海上事故(将搜寻落水人员为研究对象)，根据现有的信息只能估算出其落水人员在一个面积为1 800平方海里的海域内(一定时间内不发生变化)。由于搜寻任务时间紧迫，为了高效、合理地利用搜寻船舶，提高搜寻效率以及搜寻成功率，为此将该海域划分为9个子海域(子海域从a1到a9进行编号)，并且每个子海域面积均为200平方海里。同时，根据前人对经典包含概率、发现概率的研究成果得知落水人员在各待搜寻子海域的概率情况，如图2。

利用船讯网测距功能等技术方法测算出各个子海域之间的距离(以一子海域中心位置作为起点到另一子海域的最短距离)，如表1。

图2 子海域包含概率示意Fig. 2 Schematic diagram of inclusion probability of sub-sea area

表1 子海域之间距离Table 1 Distance between sub-sea area n mile

同样通过利用船舶交通服务系统(VTS)、船讯网等现有技术手段进行查找、统计，综合评估得出目前有30艘可调配的船舶，且每艘船舶到各个子海域(以每个子海域中心为基点)的距离已知，因此可得到船舶到子海域的距离与搜寻船舶信息等数据。

4.1 数据结果与分析

针对构建的船舶分配数学模型进行求解算法设计，并结合算例中的搜寻船舶信息[6]、船舶到子海域的距离[6]、各子海域间的距离，以及子海域面积、目标存在概率和子海域船舶容纳量等数据信息[6]，经编写算法程序，将其在MATLAB(R2017 a)环境下运行，其程序迭代过程如图3。

图3 迭代次数与方案适应度值关系Fig. 3 Relationship between the number of iterations andthe fitness value of the scheme

从图3可以看出，随着迭代次数的不断增加，方案最优适应度值(best fitness)逐渐趋于收敛，方案平均适应度值(mean fitness)也随着迭代次数的增加而逐渐趋于稳定，并无限地接近方案最优适应度值。当迭代次数达到程序设定的最大迭代次数时(设定最大迭代次数为100)程序停止执行，并输出最优的船舶分配方案，如表2。

表2 船舶分配方案Table 2 Vessel allocation plan

从表2看出，该船舶分配方案给出了派往各个子海域执行搜寻任务的船舶编号以及完成各个子海域搜寻覆盖的时间，在该方案下由式(5)得完成各子海域搜寻覆盖的时间期望总和为2.36 h。若将目标存在概率为0.58、0.09、0.015的子海域分别定义为一级、二级、三级子海域，那么可以看到完成一级子海域搜寻覆盖的时间少于二级各子海域搜寻覆盖的时间，同时完成二级各子海域搜寻覆盖的时间又都少于三级各子海域搜寻覆盖的时间。即在该方案下完成一级、二级、三级子海域搜寻覆盖的时间总体上随着其目标存在概率的逐步减小而在增加，如图4 。由于概率越大的子海域搜寻覆盖时间越短对各子海域搜寻覆盖的时间期望总和越小的贡献就越大。可见，该船舶分配方案不仅实现了向多子海域分配搜寻船舶的目标，同时符合以完成各子海域搜寻覆盖时间期望总和最小为目标的要求。

图4 完成搜寻覆盖时间与其对应的概率大小Fig. 4 The time to complete the search coverage andits corresponding probability

同时，从表2中还可以看到编号为1、3、17的这3艘船舶都参与了两个子海域的搜寻工作，即1号船分别参与了1号子海域和7号子海域的搜寻工作，3号船分别参与了1号子海域和4号子海域的搜寻工作，17号船分别参与了3号子海域和7号子海域的搜寻工作；编号为28的船舶则参与了3个子海域的搜寻工作，即28号船分别参与了2号子海域、6号子海域以及8号子海域的搜寻工作。可见，该船舶分配方案满足笔者研究重点考虑船舶多次利用的要求，解决了文献[6]中船舶搜寻完某个子海域后就返回或闲置(没有搜到目标的情况)而没有考虑是否可以继续赶往下一个未完成搜寻覆盖的子海域进行搜寻的局限性问题。

4.2 优化前后方案对比分析

为更清楚直观地说明优化后的船舶分配方案更加合理及更具科学性，在此对优化前后所得方案进行对比分析。在船舶容纳量设定相同的情况下，针对文献[6]中所假设的搜寻船舶对某一子海域搜寻完毕后不参与其它子海域搜寻的情况，同样进行求解算法设计并编写算法程序求解出在不考虑搜寻船舶多次利用情况下的一组最优船舶分配方案，如表3。

表3 优化前船舶分配方案Table 3 Vessel allocation scheme before optimization

根据表2、表3可得出优化前后方案相关情况，如表4。

表4 优化前后方案对比Table 4 Comparison of schemes before and after optimization

从表4可以看出，在船舶容纳量相同的情况下，没进行优化前参与搜寻的船舶总数为27艘，在经过优化后参与搜寻的船舶总数为22艘，少用了5艘船舶，同时算出优化前完成各子海域搜寻覆盖的时间期望总和为2.41 h，而优化后完成各子海域搜寻覆盖的时间期望总和为2.36 h。可以得出，没有考虑船舶多次利用所得到的船舶分配方案过于冗余，造成了不必要的资源浪费情况，缺乏合理性。而在考虑搜寻船舶多次利用并进行优化改进后，完成各子海域搜寻覆盖的时间期望总和更少，且需要的船舶资源更少。可见，优化后的船舶分配方案在时间上以及船舶资源利用上都优于优化前的船舶分配方案，说明优化后搜寻船舶得到更科学的分配，更合理的利用。因此，优化后船舶分配方案更加合理，且更具科学性。

5 结 语

海上搜寻是海上搜救的关键环节，是开展海上救助的基础和前提，为此制定合理的船舶分配方案至关重要，但是在制定搜寻方案时，不能为了提高搜寻效率而不考虑付出的巨大成本和代价，而是追求高效搜寻的同时兼顾到搜寻方案的经济性及合理性，因此笔者着力于研究海上搜寻船舶的最优分配问题。

从上述的研究结果得出，优化后得到的船舶分配方案解决了文献[6]中参与搜寻的船舶只对子海域进行一次搜寻的局限性问题，使搜寻船舶得到了合理地使用。同时，研究得到的搜寻船舶分配方案在满足以完成各子海域搜寻覆盖时间期望总和最小为目标的条件下，实现了向包含概率不同的多个子海域合理分配搜寻船舶的目的。可见，优化后所得到的船舶分配方案更加科学、合理，能为有关决策部门制定海上搜寻船舶分配方案提供更加科学、更符合实际的理论依据。