王 軍，于安民，楊春林

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

0 引 言

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

針對海上搜尋問題，B.O.KOOPMAN[2-3]建立了基本的搜尋理論。國際海事組織與國際民用航空組織聯(lián)合推出了《國際航空與海上搜尋救助》手冊[4]，該手冊已成為航空和海事領域內(nèi)組織、協(xié)調(diào)搜救行動的綱領性文件。J.R.FROST等[5]針對早期搜尋理論進行介紹，包括搜尋分類、目標位置分布等。文獻[6]對包含概率的概念、模型、搜尋力量等進行了詳細闡述。A.GUITOUNI等[7]將搜尋問題分解成搜尋成功概率最大和路徑生成兩階段決策問題。潘偉[8]針對優(yōu)先搜索海域問題，采用蒙特卡羅方法模擬隨機粒子，根據(jù)概率分布情況建立概率分布密度模型。L.LIN等[9]對搜尋問題中帶有優(yōu)先級的搜尋區(qū)域概率分布圖進行了研究。李浩[10]從包含概率角度出發(fā)，研究了區(qū)域半徑、漂移誤差等因素對包含概率的影響。

針對海上搜尋力量選擇優(yōu)化的研究，國內(nèi)外學者從不同角度，運用層次分析、組合優(yōu)化等多種方法進行了定性研究。朱玉柱等[11]從人命救助和財產(chǎn)救助兩方面提出了選擇搜尋資源的方法。LI Wei等[12]運用模糊數(shù)學和現(xiàn)代決策理論提出搜尋資源選擇優(yōu)化的多種方法。于衛(wèi)紅等[13]利用BP神經(jīng)網(wǎng)絡模型，確定影響搜尋資源選擇的各決策因素集權重。M.KARATAS等[14]以優(yōu)化各區(qū)域直升機配置為目標構建了整數(shù)規(guī)劃模型。胡宏啟等[15]在搜尋區(qū)域為若干個子區(qū)域前提下，對搜尋力量優(yōu)化展開研究，構建了以搜尋成功率最大為目標的模型。

在海上搜尋中，漂浮物概率分布可分為：標準態(tài)分布(高斯分布)，均勻分布和廣義分布。刑勝偉等[16]認為目標在海域內(nèi)服從均勻分布，考慮到船舶搜尋能力和與待搜尋海域距離，對備選搜尋船舶進行定量分析，以最短時間覆蓋海域為目標，建立了船舶選擇優(yōu)化模型；但并未將待搜尋海域進一步劃分，只針對單一區(qū)域選擇搜尋船舶，也未指定某一搜尋船舶負責區(qū)域。

綜上所述，基于文獻[16]，筆者考慮了目標在海域不同區(qū)域內(nèi)的概率分布，并以此為依據(jù)將海域進一步細分，劃分出若干個子區(qū)域，并計算目標在各子區(qū)域內(nèi)概率，進而明確待搜尋子區(qū)域的優(yōu)先級；并對文獻[16]中的模型進行改進，研究了搜尋船舶向多個區(qū)域指派問題。由此得出在資源、時間等約束下，搜尋船舶趕往不同子區(qū)域的船舶指派方案，以達到盡快對待搜尋海域完成搜尋覆蓋的目的。

1 問題描述

針對緊急搜尋任務，考慮到搜尋任務的時效性，往往單一搜尋資源無法在規(guī)定時間內(nèi)完成任務，需要多船協(xié)同搜尋。因此，在開展搜尋行動前需要定制合理的船舶選擇方案，以最短時間對搜尋海域完成搜尋覆蓋。

筆者根據(jù)經(jīng)典搜尋規(guī)劃方法(CSPM，classical search planning method)，目標落水后的位置稱作最后已知位置(LKP，last known position)，經(jīng)漂移推算后得到搜尋基點(datum)[17]，以搜尋基點為圓心，以總誤差為半徑，得到圓形搜尋區(qū)域。為方便設計搜尋路線，將搜尋區(qū)域擴展為圓形區(qū)域的外切正方形，并得到擴展之后正方形的包含概率(POC，probability of containment)。根據(jù)簡化的搜尋規(guī)劃方法(SSPM，simplified search planning method)，認定目標在待搜尋海域內(nèi)服從二維標準正態(tài)分布[5]。以擴展后得到的正方形海域相鄰兩邊任意點為分界，可將搜尋區(qū)域劃分為不同子區(qū)域，并根據(jù)橫縱坐標不同區(qū)間相乘求得目標在各個子區(qū)域內(nèi)概率。

因為目標在不同子區(qū)域內(nèi)概率不同，故概率高的子區(qū)域?qū)憫獣r間、搜尋優(yōu)先級要求更高，因而對優(yōu)質(zhì)搜尋資源調(diào)用優(yōu)先級也更高。假設Z為子區(qū)域的集合，j={1, 2, …, |Z|}為子區(qū)域序號，目標在個子區(qū)域內(nèi)概率為Pj(j=1, 2, 3, …)，如圖1。對概率大的子區(qū)域則應展開重點搜尋，要求船舶以最快速度趕赴概率高的海域，同時要求參加行動的搜尋資源盡快對海域完成搜尋覆蓋。

圖1 搜尋船舶與待搜尋子區(qū)域結構示意

鑒于此，筆者考慮將待搜尋區(qū)域劃分成若干個子區(qū)域后，通過構建模型來求得搜尋船舶向各自區(qū)域的指派方案。

2 模型建立

2.1 模型假設

筆者針對該模型，進行如下假設：

1)目標經(jīng)漂移推算后的搜尋基點已知；

2)待搜尋海域已知；

3)備選船舶位置、航速等信息已知；

4)當開始搜尋時，不考慮目標在經(jīng)漂移推算后的區(qū)域內(nèi)漂移；

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

6)船舶對某一子區(qū)域搜尋完畢后不參與其他子區(qū)域搜尋。

2.2 符 號

該模型中的符號定義如下：

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

|I|}；

J為各子區(qū)域集合，J={1, 2, …,j, …, |J|}；

Dij為船舶i與子區(qū)域j之間最近的直線距離，(n mile)，i∈{1, 2, …, |I|}，j∈{1, 2, …, |J|}；

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

Pj為子區(qū)域j的包含概率，j∈{1, 2, …, |J|}；

Mj為子區(qū)域j的船舶容納量，j∈{1, 2, …, |J|}；

Ci為船舶i在單位時間內(nèi)搜尋覆蓋的能力，(n mile2/h)，i∈{1, 2, …, |I|}；

S為整片搜尋海域的面積，(n mile2)；

Sj為子區(qū)域j的面積，j∈{1, 2, …, |J|}；

2.3 子區(qū)域劃分方法

根據(jù)文獻[10]，即先確定搜尋基點，總誤差為半徑得到的圓形區(qū)域，再作圓的外切正方形，這樣既擴大了包含概率又方便設計航線[18]。

海域包含概率為PPOC=1-e(-R2/2)(e為自然對數(shù)的底數(shù))，R為標準差σ下圓的半徑(標準差σ下的包含概率僅有39%)[6]。根據(jù)規(guī)定，包含概率PPOC=50%時的半徑被統(tǒng)計學家定義為位置偏差分界線，此時式中R相當于位置總或然誤差E[19]，得到PPOC=1-e(-R2/2)=50%，此時R=E=1.18σ。當將半徑擴展為3E時，得到包含概率接近100%區(qū)域。

為得出圓的外切正方形包含概率，認為基準點概率密度分布為圓形正態(tài)分布(標準正態(tài)分布)，當一組點(x1,y1)，(x2,y2)，…，(xn,yn)以這種形式分布時，xn、yn均呈正態(tài)分布，則得到圓形正態(tài)分布[20]。

若圓形半徑為一個標準差，則外切正方形邊長為2個標準差，從-1到+1，如圖2。在正方形中有序?qū)?x,y)代表點的概率是一個聯(lián)合概率[10]，x和y都在(-1, +1)標準差之間。因為x和y都是正態(tài)分布，這些概率值可由標準正態(tài)分布表計算得出。

標準正態(tài)分布[22]如式(1)：

(1)

曲線關于零對稱，故正態(tài)分布變量小于零的概率為50%[21]。假設內(nèi)切圓半徑為1，根據(jù)標準正態(tài)分布[21]，(-∞,1)區(qū)間內(nèi)密度為0.841 3，故(1,+∞)區(qū)間密度為1-0.841 3=0.158 7；(-1,+1)之間概率為0.841 3-0.158 7=0.682 6。故x,y同時在(-1, +1)之間聯(lián)合概率為0.682 6×0.682 6=0.47，即47%，如圖2。

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

x,y的區(qū)間均為(-3E, 3E)，故當x和y的區(qū)間不同時，可將x和y區(qū)間中的任意幾點作為分界點，將搜尋海域分為J個子區(qū)域，利用聯(lián)合概率密度法計算對應子區(qū)域的包含概率值。x在(-3E, 3E)取3個隨機數(shù)分別為-1.61E、-0.69E、0.85E；y在(-3E, 3E)取3個隨機數(shù)分別為-1.87E、0.37E、1.13E，求得其概率分布，如圖3。

圖3 正方形概率分布示意

原則上，若在正方形相鄰兩邊選取足夠多的點，可將海域進行無限細分，可求得目標在無限小海域里的概率。但如若將目標在子區(qū)域內(nèi)的概率進一步細分，則到達此子區(qū)域的搜尋船舶將先搜尋子區(qū)域中概率大的海域，對于搜尋船舶設計航線難度較大，也將增加計算難度。故筆者在確定子區(qū)域時認為目標服從正太分布，搜尋船舶對子區(qū)域開展搜尋時認為目標在子區(qū)域內(nèi)服從均勻分布。

2.4 船舶選擇模型

設搜尋船舶收到任務的時刻為T0，子區(qū)域j的搜尋完成時刻為Tj(j∈{1, 2, …, |J|})。則對于參與j區(qū)域搜尋的船舶i，其行動時間如式(2)：

(2)

(3)

(4)

故實現(xiàn)對海域j完全覆蓋[16]，需滿足式(5)：

(5)

實現(xiàn)對整片海域完全覆蓋，需滿足式(6)、(7)：

(6)

(7)

式(5)表示某子區(qū)域內(nèi)船舶的搜尋面積累加等于該子區(qū)域的面積；式(6)表示各搜尋船舶在各子區(qū)域內(nèi)搜尋面積累加等于整片待搜尋海域的面積；式(7)表示子區(qū)域j被搜尋完成的時刻。故該模型可由式(8)、(9)表示：

(8)

(9)

式(8)表示使各子區(qū)域被搜尋完成的時間期望總和最小，從而控制包含概率大的子區(qū)域被搜尋完成時間盡量短；式(9)表示使子區(qū)域船舶總數(shù)不應超過該區(qū)域的船舶容納量。

3 算法實現(xiàn)

為加快算法找到滿意解的速度，筆者將遺傳算法與局部搜索算法相結合，設計改進的遺傳算法，使其更快速有效地得到搜救船舶調(diào)度方案。設計算法流程如圖4。

圖4 算法流程

根據(jù)圖4流程，設計以下求解步驟：

1)編碼：文中采用船舶染色體作為解的編碼，每一條染色體是所有客戶的一組排列。采用0表示搜救區(qū)域起始點，因此解碼時0的個數(shù)將比搜救區(qū)域的個數(shù)多1；同時考慮到每一個搜救區(qū)域所能容納船舶的數(shù)量有限，設計一個虛擬搜救區(qū)域，用于區(qū)分參與搜救船舶；將所有的0插入到染色體中，就可得到各個搜救區(qū)域的船舶調(diào)度方案。例如：染色體：0 5 3 0 4 0 1 0 2 6 0表示一共有4個搜救區(qū)域，第1區(qū)域安排編號為5和3的船舶參與搜救；第2區(qū)域安排編號為4的船舶參與搜救；第3區(qū)域安排編號為1的船舶參與搜救；而第4區(qū)域為虛擬區(qū)域，因此編號為2、6的船舶不參與搜救。

2)種群初始化：令文中所建立海上搜救優(yōu)化模型中的目標函數(shù)為適應度函數(shù)，設置種群大小和最大進化次數(shù)，隨機生成包含一定數(shù)目個體的初始種群，每個個體表示為染色體的基因編碼。

3)局部搜索：由于每條尚未解碼的染色體存在多種解碼方式，而一個好的解碼方式可有效提高算法搜索效果。筆者設計的局部搜索算法，運用two-opt對每個解碼后的個體進行局部搜索，選擇最好的解碼結果。Two-opt操作先隨機選擇兩個交換點，然后將倒置兩個交換點之間序列，最后將倒置后的序列插入到原染色體中，如圖5。

圖5 Two-opt操作示意

若新的解碼個體適應度值優(yōu)于原解碼個體，則用新解碼替代原解碼。

4)適應度評價：算法中的適應度值為搜救過程中不同搜救區(qū)域搜救完成時間的加權值，它的值越低，表示個體適應度越好，搜救方案更加合理有效。對于違反模型中搜救區(qū)域船舶容納量約束的個體，將在適應度函數(shù)中添加一個較大懲罰值，表示該搜救方案不可行，該方案不會被考慮。

5)選擇：筆者采用錦標賽法進行選擇操作，即隨機選擇兩個個體，比較兩者適應度值大小，選擇其中適應度好的個體進入下一代。重復該操作，直到新的個體數(shù)與當前個體數(shù)相同為止。顯然，錦標賽法采用適應度值相對值作為選擇標準，在一定程度上可避免超級個體影響；同時，采用錦標賽法隨機選擇個體，可能使得當前最優(yōu)個體沒有被選擇，為保證種群優(yōu)良性，引入精英保留策略，用當前最優(yōu)個體替換新一代種群中最差個體。

6)交叉：交叉算子主要有部分映射交叉和順序交叉。筆者采用OX交叉方法，OX操作能保留排列并融合不同排列的有序結構單元。以圖5為例：隨機選取兩個父代個體，將父代1中與父代2后3個基因相同的基因位刪除，得到刪除基因后的父代1，以同樣方法得到刪除基因后的父代2；然后將父代2中的后3位基因順序插入父代1中的空缺基因位，得到子代個體1，以同樣方法得到子代個體2，如圖6。

圖6 交叉算子示意

7)變異：變異是對個體的某個或某些基因值按某一較小概率進行改變，是產(chǎn)生新個體的輔助方法。在文中，變異算子采用兩點互換變異，即隨機選取兩個變異點，將這兩點基因互換，得到變異后的新個體。

4 算例分析

假設某商船在中國東海失事，人員落水，海水溫度為15 ℃，根據(jù)水溫與生存時間的關系[1]，落水人員在海水中生存的極限時間為5 h，除去搜救船只到達搜索區(qū)域時間，搜索生還者的有限時間為nh。設待搜尋海域(外切正方形)900(n mile2)，在x、y方向都以(-E,E)為分界點，劃分成9個搜尋子區(qū)域，每個搜尋子區(qū)域面積為100(n mile2)，得到其概率，如圖7。

圖7 子區(qū)域包含概率示意

其中：P(Z1)>P(Z2)=P(Z3)=P(Z4)=P(Z5)>P(Z6)=P(Z7)=P(Z8)=P(Z9)，故根據(jù)包含概率大小將9個子區(qū)域分成3級，子區(qū)域1為第1級，子區(qū)域2～5為第2級，子區(qū)域6～9為第3級。待搜尋子區(qū)域的概率、面積、船舶容納量等信息如表1。

表1 待搜尋子區(qū)域信息

筆者利用“船達通”網(wǎng)站，標記出待搜尋海域和周圍30艘搜尋船舶，如圖8(將30艘船舶全部顯示，需頁面比例尺較小，系統(tǒng)將船舶符號隱藏，只顯示標記)。

圖8 搜尋船舶和搜尋區(qū)域標記示意

利用該網(wǎng)站的測距功能(圖9)，測量出每艘船舶距離9個子區(qū)域的最近直線距離，如表2。并通過查看船舶信息功能(圖10)，獲取到搜尋船舶的船速，搜尋船舶的搜尋覆蓋能力等信息如表3。

圖9 測距功能示意

表2 搜尋船舶與各子區(qū)域的距離

圖10 查詢船舶信息示意

針對筆者提出的模型，在算法實現(xiàn)基礎上，設定初始種群規(guī)模為300，迭代次數(shù)為150次，交叉概率為0.9，變異概率為0.1，搜尋開始時刻T0=0(收到搜尋任務的時刻)。應用MATLAB進行求解，在迭代過程中可看出，隨著迭代次數(shù)增加，目標值逐漸收斂，如圖11。當?shù)?0次后，收斂速度明顯趨于平穩(wěn)，當程序迭代至設定的150次時，得到船舶選擇方案如表4。

圖11 迭代次數(shù)與最優(yōu)值的關系

表4 船舶選擇方案

由此可知，此種船舶選擇方案滿足了不同子區(qū)域?qū)Υ暗恼{(diào)用優(yōu)先權，包含概率最大的第1級子區(qū)域(子區(qū)域1)優(yōu)先調(diào)用距離該海域近、搜尋覆蓋能力較強的船舶，且搜尋結束時間最短；第2級子區(qū)域相比第3級子區(qū)域的搜尋結束時間也短，整個搜尋總動結束時間為子區(qū)域6搜尋完成時間，即4.91 h，各子區(qū)域搜尋結束時間期望總和的最小值為2.79 h。

考慮到第1級子區(qū)域概率要明顯大于第2級子區(qū)域(9%)和第3級子區(qū)域(1.5%)，做決策時候可能會根據(jù)調(diào)度船舶總數(shù)(成本預算)和決策者風險偏好不同而改變3級子區(qū)域的船舶容納量，比如著重向區(qū)域1派遣船舶，向第3級子區(qū)域少派遣船舶。為此，筆者分為5種情況討論，如表5。不同船舶容納量情況經(jīng)運行后的結果如圖12、表6。

表5 各情況下不同子區(qū)域的船舶容納量

圖12 搜尋完各區(qū)域所用時間

表6 不同情況所用時間的比較

考慮到3級子區(qū)域概率有明顯差別，故3級子區(qū)域?qū)?yōu)質(zhì)搜尋資源(速度快，搜尋覆蓋能力強)的調(diào)用優(yōu)先級不同。從圖12中的5條曲線可看出：完成搜尋第2級子區(qū)域所用時間相比第1級子區(qū)域有明顯增加，完成第3級子區(qū)域所用時間相比第2級子區(qū)域也有明顯增加。

情況4共調(diào)用20條船舶，且對子區(qū)域1派遣了4條船舶，所以搜尋完區(qū)域1和完成此次行動所用時間都最少。情況5相比情況4，對子區(qū)域6～9都少派遣了1條船，搜尋完成總時間要多。情況5相比情況3，向區(qū)域1多派遣了一條船，比情況3搜尋完子區(qū)域1時間節(jié)省了0.2 h。情況3因只調(diào)用了15條船舶，故完成此次搜尋型動所用時間最長，為8.36 h。

5 結 語

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