海上搜尋船舶選擇問題研究

王 軍，于安民，楊春林

(大連海事大學 交通運輸工程學院，遼寧 大連 116026)

0 引 言

海上發生險情后，人員在海水中的生存時間隨海水溫度的不同而變化，普通成年人在0 ℃海水中預計生存時間為不超過0.2 h[1]，故為最大限度挽救人命，需要迅速開展并完成搜尋任務。但受事故水域附近可用于搜救專業船舶數量與距離等限制，往往需要調用其附近的過往船舶參與救援。當船舶或人員遇險后，存在的搜尋力量包括事發海域附近的過路船舶(文中研究人命救助，根據《國際海上人命安全公約》，過往船舶有義務接受主管當局調派，參與人員搜尋行動)，在港?？康膶I救助船舶，及專業的空中搜尋力量(航空器)。如何對搜尋資源進行選擇，以達到快速、高效對搜尋海域進行覆蓋，是目前學界急需解決的問題。

針對海上搜尋問題，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 結 語

筆者根據目標在海上的概率分布，將海上待搜尋區域劃分為若干個待搜尋子區域，并得出各子區域的包含概率。以各子區域包含概率不同為前提，研究了向多個搜尋區域派遣搜尋船舶的問題。并且對求解單一區域搜尋船舶選擇方案模型進行改進，使其適用于求解向多個區域指派搜尋船舶問題，提高了這一模型在實際海上搜尋中的適用性。并根據決策者風險偏好不同，求得不同情況下的搜尋船舶選擇方案，為有關決策部門確定選擇方案提供科學依據。