海上搜寻船舶选择问题研究

王 军，于安民，杨春林

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

0 引 言

海上发生险情后，人员在海水中的生存时间随海水温度的不同而变化，普通成年人在0 ℃海水中预计生存时间为不超过0.2 h[1]，故为最大限度挽救人命，需要迅速开展并完成搜寻任务。但受事故水域附近可用于搜救专业船舶数量与距离等限制，往往需要调用其附近的过往船舶参与救援。当船舶或人员遇险后，存在的搜寻力量包括事发海域附近的过路船舶(文中研究人命救助，根据《国际海上人命安全公约》，过往船舶有义务接受主管当局调派，参与人员搜寻行动)，在港停靠的专业救助船舶，及专业的空中搜寻力量(航空器)。如何对搜寻资源进行选择，以达到快速、高效对搜寻海域进行覆盖，是目前学界急需解决的问题。

针对海上搜寻问题，B.O.KOOPMAN[2-3]建立了基本的搜寻理论。国际海事组织与国际民用航空组织联合推出了《国际航空与海上搜寻救助》手册[4]，该手册已成为航空和海事领域内组织、协调搜救行动的纲领性文件。J.R.FROST等[5]针对早期搜寻理论进行介绍，包括搜寻分类、目标位置分布等。文献[6]对包含概率的概念、模型、搜寻力量等进行了详细阐述。A.GUITOUNI等[7]将搜寻问题分解成搜寻成功概率最大和路径生成两阶段决策问题。潘伟[8]针对优先搜索海域问题，采用蒙特卡罗方法模拟随机粒子，根据概率分布情况建立概率分布密度模型。L.LIN等[9]对搜寻问题中带有优先级的搜寻区域概率分布图进行了研究。李浩[10]从包含概率角度出发，研究了区域半径、漂移误差等因素对包含概率的影响。

针对海上搜寻力量选择优化的研究，国内外学者从不同角度，运用层次分析、组合优化等多种方法进行了定性研究。朱玉柱等[11]从人命救助和财产救助两方面提出了选择搜寻资源的方法。LI Wei等[12]运用模糊数学和现代决策理论提出搜寻资源选择优化的多种方法。于卫红等[13]利用BP神经网络模型，确定影响搜寻资源选择的各决策因素集权重。M.KARATAS等[14]以优化各区域直升机配置为目标构建了整数规划模型。胡宏启等[15]在搜寻区域为若干个子区域前提下，对搜寻力量优化展开研究，构建了以搜寻成功率最大为目标的模型。

在海上搜寻中，漂浮物概率分布可分为：标准态分布(高斯分布)，均匀分布和广义分布。刑胜伟等[16]认为目标在海域内服从均匀分布，考虑到船舶搜寻能力和与待搜寻海域距离，对备选搜寻船舶进行定量分析，以最短时间覆盖海域为目标，建立了船舶选择优化模型；但并未将待搜寻海域进一步划分，只针对单一区域选择搜寻船舶，也未指定某一搜寻船舶负责区域。

综上所述，基于文献[16]，笔者考虑了目标在海域不同区域内的概率分布，并以此为依据将海域进一步细分，划分出若干个子区域，并计算目标在各子区域内概率，进而明确待搜寻子区域的优先级；并对文献[16]中的模型进行改进，研究了搜寻船舶向多个区域指派问题。由此得出在资源、时间等约束下，搜寻船舶赶往不同子区域的船舶指派方案，以达到尽快对待搜寻海域完成搜寻覆盖的目的。

1 问题描述

针对紧急搜寻任务，考虑到搜寻任务的时效性，往往单一搜寻资源无法在规定时间内完成任务，需要多船协同搜寻。因此，在开展搜寻行动前需要定制合理的船舶选择方案，以最短时间对搜寻海域完成搜寻覆盖。

笔者根据经典搜寻规划方法(CSPM，classical search planning method)，目标落水后的位置称作最后已知位置(LKP，last known position)，经漂移推算后得到搜寻基点(datum)[17]，以搜寻基点为圆心，以总误差为半径，得到圆形搜寻区域。为方便设计搜寻路线，将搜寻区域扩展为圆形区域的外切正方形，并得到扩展之后正方形的包含概率(POC，probability of containment)。根据简化的搜寻规划方法(SSPM，simplified search planning method)，认定目标在待搜寻海域内服从二维标准正态分布[5]。以扩展后得到的正方形海域相邻两边任意点为分界，可将搜寻区域划分为不同子区域，并根据横纵坐标不同区间相乘求得目标在各个子区域内概率。

因为目标在不同子区域内概率不同，故概率高的子区域对响应时间、搜寻优先级要求更高，因而对优质搜寻资源调用优先级也更高。假设Z为子区域的集合，j={1, 2, …, |Z|}为子区域序号，目标在个子区域内概率为Pj(j=1, 2, 3, …)，如图1。对概率大的子区域则应展开重点搜寻，要求船舶以最快速度赶赴概率高的海域，同时要求参加行动的搜寻资源尽快对海域完成搜寻覆盖。

图1 搜寻船舶与待搜寻子区域结构示意

鉴于此，笔者考虑将待搜寻区域划分成若干个子区域后，通过构建模型来求得搜寻船舶向各自区域的指派方案。

2 模型建立

2.1 模型假设

笔者针对该模型，进行如下假设：

1)目标经漂移推算后的搜寻基点已知；

2)待搜寻海域已知；

3)备选船舶位置、航速等信息已知；

4)当开始搜寻时，不考虑目标在经漂移推算后的区域内漂移；

5)天气、海况良好，船舶航行不受限；

6)船舶对某一子区域搜寻完毕后不参与其他子区域搜寻。

2.2 符 号

该模型中的符号定义如下：

I为可用搜寻船舶集合，I={1, 2, …,i, …,

|I|}；

J为各子区域集合，J={1, 2, …,j, …, |J|}；

Dij为船舶i与子区域j之间最近的直线距离，(n mile)，i∈{1, 2, …, |I|}，j∈{1, 2, …, |J|}；

Vi为船舶i的最大航速，kt，i∈{1, 2, …, |I|}；

Pj为子区域j的包含概率，j∈{1, 2, …, |J|}；

Mj为子区域j的船舶容纳量，j∈{1, 2, …, |J|}；

Ci为船舶i在单位时间内搜寻覆盖的能力，(n mile2/h)，i∈{1, 2, …, |I|}；

S为整片搜寻海域的面积，(n mile2)；

Sj为子区域j的面积，j∈{1, 2, …, |J|}；

2.3 子区域划分方法

根据文献[10]，即先确定搜寻基点，总误差为半径得到的圆形区域，再作圆的外切正方形，这样既扩大了包含概率又方便设计航线[18]。

海域包含概率为PPOC=1-e(-R2/2)(e为自然对数的底数)，R为标准差σ下圆的半径(标准差σ下的包含概率仅有39%)[6]。根据规定，包含概率PPOC=50%时的半径被统计学家定义为位置偏差分界线，此时式中R相当于位置总或然误差E[19]，得到PPOC=1-e(-R2/2)=50%，此时R=E=1.18σ。当将半径扩展为3E时，得到包含概率接近100%区域。

为得出圆的外切正方形包含概率，认为基准点概率密度分布为圆形正态分布(标准正态分布)，当一组点(x1,y1)，(x2,y2)，…，(xn,yn)以这种形式分布时，xn、yn均呈正态分布，则得到圆形正态分布[20]。

若圆形半径为一个标准差，则外切正方形边长为2个标准差，从-1到+1，如图2。在正方形中有序对(x,y)代表点的概率是一个联合概率[10]，x和y都在(-1, +1)标准差之间。因为x和y都是正态分布，这些概率值可由标准正态分布表计算得出。

标准正态分布[22]如式(1)：

(1)

曲线关于零对称，故正态分布变量小于零的概率为50%[21]。假设内切圆半径为1，根据标准正态分布[21]，(-∞,1)区间内密度为0.841 3，故(1,+∞)区间密度为1-0.841 3=0.158 7；(-1,+1)之间概率为0.841 3-0.158 7=0.682 6。故x,y同时在(-1, +1)之间联合概率为0.682 6×0.682 6=0.47，即47%，如图2。

图2 外切正方形的包含概率

x,y的区间均为(-3E, 3E)，故当x和y的区间不同时，可将x和y区间中的任意几点作为分界点，将搜寻海域分为J个子区域，利用联合概率密度法计算对应子区域的包含概率值。x在(-3E, 3E)取3个随机数分别为-1.61E、-0.69E、0.85E；y在(-3E, 3E)取3个随机数分别为-1.87E、0.37E、1.13E，求得其概率分布，如图3。

图3 正方形概率分布示意

原则上，若在正方形相邻两边选取足够多的点，可将海域进行无限细分，可求得目标在无限小海域里的概率。但如若将目标在子区域内的概率进一步细分，则到达此子区域的搜寻船舶将先搜寻子区域中概率大的海域，对于搜寻船舶设计航线难度较大，也将增加计算难度。故笔者在确定子区域时认为目标服从正太分布，搜寻船舶对子区域开展搜寻时认为目标在子区域内服从均匀分布。

2.4 船舶选择模型

设搜寻船舶收到任务的时刻为T0，子区域j的搜寻完成时刻为Tj(j∈{1, 2, …, |J|})。则对于参与j区域搜寻的船舶i，其行动时间如式(2)：

(2)

(3)

(4)

故实现对海域j完全覆盖[16]，需满足式(5)：

(5)

实现对整片海域完全覆盖，需满足式(6)、(7)：

(6)

(7)

式(5)表示某子区域内船舶的搜寻面积累加等于该子区域的面积；式(6)表示各搜寻船舶在各子区域内搜寻面积累加等于整片待搜寻海域的面积；式(7)表示子区域j被搜寻完成的时刻。故该模型可由式(8)、(9)表示：

(8)

(9)

式(8)表示使各子区域被搜寻完成的时间期望总和最小，从而控制包含概率大的子区域被搜寻完成时间尽量短；式(9)表示使子区域船舶总数不应超过该区域的船舶容纳量。

3 算法实现

为加快算法找到满意解的速度，笔者将遗传算法与局部搜索算法相结合，设计改进的遗传算法，使其更快速有效地得到搜救船舶调度方案。设计算法流程如图4。

图4 算法流程

根据图4流程，设计以下求解步骤：

1)编码：文中采用船舶染色体作为解的编码，每一条染色体是所有客户的一组排列。采用0表示搜救区域起始点，因此解码时0的个数将比搜救区域的个数多1；同时考虑到每一个搜救区域所能容纳船舶的数量有限，设计一个虚拟搜救区域，用于区分参与搜救船舶；将所有的0插入到染色体中，就可得到各个搜救区域的船舶调度方案。例如：染色体：0 5 3 0 4 0 1 0 2 6 0表示一共有4个搜救区域，第1区域安排编号为5和3的船舶参与搜救；第2区域安排编号为4的船舶参与搜救；第3区域安排编号为1的船舶参与搜救；而第4区域为虚拟区域，因此编号为2、6的船舶不参与搜救。

2)种群初始化：令文中所建立海上搜救优化模型中的目标函数为适应度函数，设置种群大小和最大进化次数，随机生成包含一定数目个体的初始种群，每个个体表示为染色体的基因编码。

3)局部搜索：由于每条尚未解码的染色体存在多种解码方式，而一个好的解码方式可有效提高算法搜索效果。笔者设计的局部搜索算法，运用two-opt对每个解码后的个体进行局部搜索，选择最好的解码结果。Two-opt操作先随机选择两个交换点，然后将倒置两个交换点之间序列，最后将倒置后的序列插入到原染色体中，如图5。

图5 Two-opt操作示意

若新的解码个体适应度值优于原解码个体，则用新解码替代原解码。

4)适应度评价：算法中的适应度值为搜救过程中不同搜救区域搜救完成时间的加权值，它的值越低，表示个体适应度越好，搜救方案更加合理有效。对于违反模型中搜救区域船舶容纳量约束的个体，将在适应度函数中添加一个较大惩罚值，表示该搜救方案不可行，该方案不会被考虑。

5)选择：笔者采用锦标赛法进行选择操作，即随机选择两个个体，比较两者适应度值大小，选择其中适应度好的个体进入下一代。重复该操作，直到新的个体数与当前个体数相同为止。显然，锦标赛法采用适应度值相对值作为选择标准，在一定程度上可避免超级个体影响；同时，采用锦标赛法随机选择个体，可能使得当前最优个体没有被选择，为保证种群优良性，引入精英保留策略，用当前最优个体替换新一代种群中最差个体。

6)交叉：交叉算子主要有部分映射交叉和顺序交叉。笔者采用OX交叉方法，OX操作能保留排列并融合不同排列的有序结构单元。以图5为例：随机选取两个父代个体，将父代1中与父代2后3个基因相同的基因位删除，得到删除基因后的父代1，以同样方法得到删除基因后的父代2；然后将父代2中的后3位基因顺序插入父代1中的空缺基因位，得到子代个体1，以同样方法得到子代个体2，如图6。

图6 交叉算子示意

7)变异：变异是对个体的某个或某些基因值按某一较小概率进行改变，是产生新个体的辅助方法。在文中，变异算子采用两点互换变异，即随机选取两个变异点，将这两点基因互换，得到变异后的新个体。

4 算例分析

假设某商船在中国东海失事，人员落水，海水温度为15 ℃，根据水温与生存时间的关系[1]，落水人员在海水中生存的极限时间为5 h，除去搜救船只到达搜索区域时间，搜索生还者的有限时间为nh。设待搜寻海域(外切正方形)900(n mile2)，在x、y方向都以(-E,E)为分界点，划分成9个搜寻子区域，每个搜寻子区域面积为100(n mile2)，得到其概率，如图7。

图7 子区域包含概率示意

其中：P(Z1)>P(Z2)=P(Z3)=P(Z4)=P(Z5)>P(Z6)=P(Z7)=P(Z8)=P(Z9)，故根据包含概率大小将9个子区域分成3级，子区域1为第1级，子区域2～5为第2级，子区域6～9为第3级。待搜寻子区域的概率、面积、船舶容纳量等信息如表1。

表1 待搜寻子区域信息

笔者利用“船达通”网站，标记出待搜寻海域和周围30艘搜寻船舶，如图8(将30艘船舶全部显示，需页面比例尺较小，系统将船舶符号隐藏，只显示标记)。

图8 搜寻船舶和搜寻区域标记示意

利用该网站的测距功能(图9)，测量出每艘船舶距离9个子区域的最近直线距离，如表2。并通过查看船舶信息功能(图10)，获取到搜寻船舶的船速，搜寻船舶的搜寻覆盖能力等信息如表3。

图9 测距功能示意

表2 搜寻船舶与各子区域的距离

图10 查询船舶信息示意

针对笔者提出的模型，在算法实现基础上，设定初始种群规模为300，迭代次数为150次，交叉概率为0.9，变异概率为0.1，搜寻开始时刻T0=0(收到搜寻任务的时刻)。应用MATLAB进行求解，在迭代过程中可看出，随着迭代次数增加，目标值逐渐收敛，如图11。当迭代至50次后，收敛速度明显趋于平稳，当程序迭代至设定的150次时，得到船舶选择方案如表4。

图11 迭代次数与最优值的关系

表4 船舶选择方案

由此可知，此种船舶选择方案满足了不同子区域对船舶的调用优先权，包含概率最大的第1级子区域(子区域1)优先调用距离该海域近、搜寻覆盖能力较强的船舶，且搜寻结束时间最短；第2级子区域相比第3级子区域的搜寻结束时间也短，整个搜寻总动结束时间为子区域6搜寻完成时间，即4.91 h，各子区域搜寻结束时间期望总和的最小值为2.79 h。

考虑到第1级子区域概率要明显大于第2级子区域(9%)和第3级子区域(1.5%)，做决策时候可能会根据调度船舶总数(成本预算)和决策者风险偏好不同而改变3级子区域的船舶容纳量，比如着重向区域1派遣船舶，向第3级子区域少派遣船舶。为此，笔者分为5种情况讨论，如表5。不同船舶容纳量情况经运行后的结果如图12、表6。

表5 各情况下不同子区域的船舶容纳量

图12 搜寻完各区域所用时间

表6 不同情况所用时间的比较

考虑到3级子区域概率有明显差别，故3级子区域对优质搜寻资源(速度快，搜寻覆盖能力强)的调用优先级不同。从图12中的5条曲线可看出：完成搜寻第2级子区域所用时间相比第1级子区域有明显增加，完成第3级子区域所用时间相比第2级子区域也有明显增加。

情况4共调用20条船舶，且对子区域1派遣了4条船舶，所以搜寻完区域1和完成此次行动所用时间都最少。情况5相比情况4，对子区域6～9都少派遣了1条船，搜寻完成总时间要多。情况5相比情况3，向区域1多派遣了一条船，比情况3搜寻完子区域1时间节省了0.2 h。情况3因只调用了15条船舶，故完成此次搜寻型动所用时间最长，为8.36 h。

5 结 语

笔者根据目标在海上的概率分布，将海上待搜寻区域划分为若干个待搜寻子区域，并得出各子区域的包含概率。以各子区域包含概率不同为前提，研究了向多个搜寻区域派遣搜寻船舶的问题。并且对求解单一区域搜寻船舶选择方案模型进行改进，使其适用于求解向多个区域指派搜寻船舶问题，提高了这一模型在实际海上搜寻中的适用性。并根据决策者风险偏好不同，求得不同情况下的搜寻船舶选择方案，为有关决策部门确定选择方案提供科学依据。