海上搜尋船舶分配問題優(yōu)化研究

王 軍，楊春林，王美蓉

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

0 引 言

當發(fā)生海難時，如何在最短的時間內制定出高效、科學的搜救方案，以減少人員傷亡和財產損失是眾多學者在海上搜救領域致力于研究的問題。而海上搜救可分為海上搜尋與海上救助兩大部分，同時海上搜尋往往是提供海上救助的前提，也是海上搜救整個過程中的關鍵環(huán)節(jié)，因此快速展開海上搜尋工作尤為重要。由于海上搜尋涉及很多不確定性因素，如目標海域位置與范圍大小的確定、目標附近海域是否有可用于搜尋或救助的船舶、目標與停靠在港的專業(yè)搜救船舶以及空中搜尋救援基地的距離大小等，導致海上搜尋工作往往難度比較大。因此，決策人員如何分配搜尋船舶，以達到對給定海域以最短時間、用最少的船舶資源對其完成搜尋覆蓋，是海上搜救領域的難題。

目前，針對海上搜救船舶選擇與分配問題，LI Wei等[1]以現(xiàn)代決策理論和模糊數(shù)學評價為基礎，提出了3種多目標優(yōu)化搜救船舶選擇方法(多屬性加權和評價法、漢明距離法和模糊相似優(yōu)先度法)，同時證明了3種方法的可行性，并給出了時間是影響船舶選擇的主要因素；邢勝偉等[2]根據(jù)在獲取船舶信息的前提下，將海上搜尋力量選擇問題抽象為帶有船舶總量約束的最優(yōu)化問題，建立了船舶選擇優(yōu)化模型，并考慮在不同船舶數(shù)約束下,分析最優(yōu)方案與成本之間的關系,進而確定船舶選擇方案；于衛(wèi)紅等[3]基于船舶優(yōu)選所考慮的主要因素，建立BP神經(jīng)網(wǎng)絡模型，并通過構建的模型確定影響船舶選擇的各決策因素集的權重，進而確定優(yōu)選方案；李巖等[4]以傳統(tǒng)拍賣規(guī)則為基礎，引入多智能體技術，提出了改進拍賣規(guī)則的多智能體海上搜尋任務分配方法，并通過仿真結果驗證了該方法的有效性；胡宏啟等[5]考慮在多子區(qū)域及多搜索主體的前提下，構建了以搜尋成功率最大為目標的模型，并驗證了模型的可行性；王軍等[6]依據(jù)目標在待搜尋海域內的概率分布情況，將待搜尋海域劃分為若干子海域，并以目標在各子海域的概率分布大小確定待搜尋子海域的優(yōu)先級關系，建立了以各子海域搜尋結束的時間期望總和最小為目標的搜尋船舶選擇模型，并驗證了模型的可行性。但是作者在其問題研究上沒有考慮到搜尋船舶多次利用的問題，所得方案中的每艘船舶都只執(zhí)行一個子海域的搜尋工作，即對某一子海域搜尋完畢后的船舶就不再參與其他子海域的搜尋工作。因此，筆者將重點針對文獻[6]中沒有考慮搜尋船舶多次利用問題進行優(yōu)化改進。

綜上所述，筆者將在文獻[6]的基礎上進一步優(yōu)化研究，針對其假設的搜尋船舶對某一子海域搜尋結束后就不再繼續(xù)參與其他子海域搜尋的局限性問題進行優(yōu)化改進，研究以最短時間、使用最少的船舶資源條件完成對給定概率分布不同的多個子海域搜尋覆蓋的船舶分配問題。

1 問題描述

由于在風、流等眾多因素綜合影響下，遇險目標位置發(fā)生漂移情況，以至于目標準確位置難以確定。盡管在現(xiàn)有技術條件下可以利用數(shù)值模型預測目標漂移軌跡，然而由于海況的復雜性，往往預測的目標位置與目標實際所在位置都存在一定偏差[7]。但可在分析估算目標漂移位置信息的基礎上，利用總搜尋誤差和搜尋安全系數(shù)推算出搜尋半徑，進而確定搜尋海域[8]。因此，筆者將針對已確定的搜尋海域研究搜尋船舶的分配問題。

筆者在前人對經(jīng)典包含概率、發(fā)現(xiàn)概率研究的基礎上，假設已知目標存在于各待搜尋子海域的概率分布信息，即各搜尋子海域包含概率的情況。同時，通過利用現(xiàn)有的科技手段(船舶自動識別系統(tǒng)(AIS)[9]、船舶交通服務系統(tǒng)(VTS)[10]、船舶遠程信息識別與跟蹤系統(tǒng)(LRIT)[11]、中氣導、船達通、船訊網(wǎng)等)將目標周邊海域船舶及在港?？康膶I(yè)搜救船舶等信息快速顯示并統(tǒng)計出來。如圖1，是通過利用船訊網(wǎng)獲取某時刻某港口區(qū)域所有的船舶數(shù)據(jù)(包括每艘船舶的位置、類型、狀態(tài)、航速等詳細信息)。在此基礎上，研究制定派往概率分布情況不同的各子海域的船舶分配方案。在研究過程中，筆者將通過設計相關算法實現(xiàn)在概率分布越大的子海域選派出完成該海域搜尋覆蓋時間越短的船舶，同時所設計的算法將實現(xiàn)研究重點考慮搜尋船舶多次利用的目的。

綜合以上說明及描述，將在已確定概率分布不同的多個待搜尋子海域、有機會參與搜尋的船舶信息等前提下，以完成各子海域搜尋覆蓋時間期望總和最小為目標，研究概率分布情況不同的多個子海域分配搜尋船舶的問題。

2 模型建立

2.1 模型假設

1)待搜尋子海域面積大小及目標在各子海域的概率已知；

2)對于面積相等的子海域，所設定的船舶容納量相等；

3)有機會執(zhí)行搜尋任務的船舶及其所在位置等信息已知；

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 船舶分配模型

由于本研究考慮到搜尋船舶是否滿足執(zhí)行多個子海域的搜尋工作問題，因此船舶Lj到達子海域Ai的時間Tji可分為兩種情況：①當某搜尋船舶Lj在不滿足執(zhí)行多個子海域搜尋任務時，僅考慮搜尋船舶到達子海域需要的時間；②當Lj滿足執(zhí)行多個子海域的搜尋任務時，將計算出搜尋船舶Lj完成當前子海域搜尋覆蓋的時間，同時需要加上航行到另一子海域的時間。因此，時間Tji可表示為：

(1)

考慮到每艘船舶到達各子海域的時間、單位時間內搜尋能力等存在差異的情況，故存在某搜尋船舶是否有機會參與搜尋任務(即船舶到達某子海域時，而在其前面已到達的船舶是否已完成該子海域搜尋覆蓋的工作)的問題，為此引入決策變量：

(2)

基于以上說明與分析，搜尋船舶從時刻T0開始到完成搜尋覆蓋子海域Ai需滿足：

(3)

即：

(4)

因此，構建船舶分配的數(shù)學模型為：

(5)

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

(6)

其中，式(4)為完成各子海域搜尋覆蓋的時間；式(5)為目標函數(shù)，即完成各子海域搜尋覆蓋的時間期望總和；式(6)為子海域船舶容納量限制，即參與子海域搜尋的船舶總數(shù)小于等于其船舶容納量限制。

3 算法實現(xiàn)

針對筆者提出的船舶分配模型，在搜尋時間期望上采用了基于優(yōu)先隊列的算法來實現(xiàn)，并利用遺傳算法找出最佳分配方案。

3.1 搜尋時間期望實現(xiàn)算法

為更清楚地說明與表示設計算法的實現(xiàn)過程，在此將對所要求的船舶分配方案進行簡單地描述以及重新進行部分符號說明，具體如下所述：

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 搜尋時間期望求解

記優(yōu)先隊列為Q，Q中的元素記為x，對優(yōu)先隊列Q的相關操作為：

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

2)x=Q.pop()表示取出Q中關鍵屬性最小的元素并賦給x。

其中，x代表發(fā)生事件且由以下信息構成：①x.time表示發(fā)生事件的時間；②x.shipId表示事件發(fā)生的船的編號；③x.areaId表示事件發(fā)生的海域編號；④x.type表示事件的類型，即0表示船到達海域的事件；1表示船完成海域的搜尋任務的事件(如果還有任務未完成，船舶會繼續(xù)搜尋下個子海域)。事件x可以表示為x={time,shipId,areaId,type}，位置依次表示相應屬性。

方案的搜尋時間期望E(S)求解過程為：

2)則令u=Q.pop()，u代表下一個發(fā)生的事件。

3)如果u.type=0，表示船到達事件，根據(jù)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搜，區(qū)域有k個。本方法采用的基因編碼格式為m×k的矩陣M∈Rm×k，并且矩陣M的每個元素mij取值都在0～1之間。

2)編碼到方案的轉換方法，即T：M→S如下：對于M的每一列數(shù)據(jù)，選取其中值最大的3個數(shù)。設第j列最大的3個數(shù)分別是mt1, j、mt2, j、mt3, j，則表示編號為t1、t2、t3的3艘船將被派去第j個區(qū)域。若第i艘船被派去搜索的區(qū)域的順序是p1,p2,…,pni，則它們的基因滿足：mi,p1>mi,p2>…>mi,pni。即基因值大小決定搜尋順序，基因值大的海域優(yōu)先搜尋。

3)遺傳算法求解表達式為：

(9)

s.t. 0≤vi≤1

(10)

式中：v為矩陣M按照列優(yōu)先向量化的向量，即v1=m1,1，v2=m2,1，以此類推。

4)遺傳算法求解采用MATLAB的ga函數(shù)進行求解。

4 算例分析

假設某海域突發(fā)海上事故(將搜尋落水人員為研究對象)，根據(jù)現(xiàn)有的信息只能估算出其落水人員在一個面積為1 800平方海里的海域內(一定時間內不發(fā)生變化)。由于搜尋任務時間緊迫，為了高效、合理地利用搜尋船舶，提高搜尋效率以及搜尋成功率，為此將該海域劃分為9個子海域(子海域從a1到a9進行編號)，并且每個子海域面積均為200平方海里。同時，根據(jù)前人對經(jīng)典包含概率、發(fā)現(xiàn)概率的研究成果得知落水人員在各待搜尋子海域的概率情況，如圖2。

利用船訊網(wǎng)測距功能等技術方法測算出各個子海域之間的距離(以一子海域中心位置作為起點到另一子海域的最短距離)，如表1。

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

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

同樣通過利用船舶交通服務系統(tǒng)(VTS)、船訊網(wǎng)等現(xiàn)有技術手段進行查找、統(tǒng)計，綜合評估得出目前有30艘可調配的船舶，且每艘船舶到各個子海域(以每個子海域中心為基點)的距離已知，因此可得到船舶到子海域的距離與搜尋船舶信息等數(shù)據(jù)。

4.1 數(shù)據(jù)結果與分析

針對構建的船舶分配數(shù)學模型進行求解算法設計，并結合算例中的搜尋船舶信息[6]、船舶到子海域的距離[6]、各子海域間的距離，以及子海域面積、目標存在概率和子海域船舶容納量等數(shù)據(jù)信息[6]，經(jīng)編寫算法程序，將其在MATLAB(R2017 a)環(huán)境下運行，其程序迭代過程如圖3。

圖3 迭代次數(shù)與方案適應度值關系Fig. 3 Relationship between the number of iterations andthe fitness value of the scheme

從圖3可以看出，隨著迭代次數(shù)的不斷增加，方案最優(yōu)適應度值(best fitness)逐漸趨于收斂，方案平均適應度值(mean fitness)也隨著迭代次數(shù)的增加而逐漸趨于穩(wěn)定，并無限地接近方案最優(yōu)適應度值。當?shù)螖?shù)達到程序設定的最大迭代次數(shù)時(設定最大迭代次數(shù)為100)程序停止執(zhí)行，并輸出最優(yōu)的船舶分配方案，如表2。

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

從表2看出，該船舶分配方案給出了派往各個子海域執(zhí)行搜尋任務的船舶編號以及完成各個子海域搜尋覆蓋的時間，在該方案下由式(5)得完成各子海域搜尋覆蓋的時間期望總和為2.36 h。若將目標存在概率為0.58、0.09、0.015的子海域分別定義為一級、二級、三級子海域，那么可以看到完成一級子海域搜尋覆蓋的時間少于二級各子海域搜尋覆蓋的時間，同時完成二級各子海域搜尋覆蓋的時間又都少于三級各子海域搜尋覆蓋的時間。即在該方案下完成一級、二級、三級子海域搜尋覆蓋的時間總體上隨著其目標存在概率的逐步減小而在增加，如圖4 。由于概率越大的子海域搜尋覆蓋時間越短對各子海域搜尋覆蓋的時間期望總和越小的貢獻就越大?？梢?，該船舶分配方案不僅實現(xiàn)了向多子海域分配搜尋船舶的目標，同時符合以完成各子海域搜尋覆蓋時間期望總和最小為目標的要求。

圖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]中船舶搜尋完某個子海域后就返回或閑置(沒有搜到目標的情況)而沒有考慮是否可以繼續(xù)趕往下一個未完成搜尋覆蓋的子海域進行搜尋的局限性問題。

4.2 優(yōu)化前后方案對比分析

為更清楚直觀地說明優(yōu)化后的船舶分配方案更加合理及更具科學性，在此對優(yōu)化前后所得方案進行對比分析。在船舶容納量設定相同的情況下，針對文獻[6]中所假設的搜尋船舶對某一子海域搜尋完畢后不參與其它子海域搜尋的情況，同樣進行求解算法設計并編寫算法程序求解出在不考慮搜尋船舶多次利用情況下的一組最優(yōu)船舶分配方案，如表3。

表3 優(yōu)化前船舶分配方案Table 3 Vessel allocation scheme before optimization

根據(jù)表2、表3可得出優(yōu)化前后方案相關情況，如表4。

表4 優(yōu)化前后方案對比Table 4 Comparison of schemes before and after optimization

從表4可以看出，在船舶容納量相同的情況下，沒進行優(yōu)化前參與搜尋的船舶總數(shù)為27艘，在經(jīng)過優(yōu)化后參與搜尋的船舶總數(shù)為22艘，少用了5艘船舶，同時算出優(yōu)化前完成各子海域搜尋覆蓋的時間期望總和為2.41 h，而優(yōu)化后完成各子海域搜尋覆蓋的時間期望總和為2.36 h?？梢缘贸?，沒有考慮船舶多次利用所得到的船舶分配方案過于冗余，造成了不必要的資源浪費情況，缺乏合理性。而在考慮搜尋船舶多次利用并進行優(yōu)化改進后，完成各子海域搜尋覆蓋的時間期望總和更少，且需要的船舶資源更少?？梢姡瑑?yōu)化后的船舶分配方案在時間上以及船舶資源利用上都優(yōu)于優(yōu)化前的船舶分配方案，說明優(yōu)化后搜尋船舶得到更科學的分配，更合理的利用。因此，優(yōu)化后船舶分配方案更加合理，且更具科學性。

5 結 語

海上搜尋是海上搜救的關鍵環(huán)節(jié)，是開展海上救助的基礎和前提，為此制定合理的船舶分配方案至關重要，但是在制定搜尋方案時，不能為了提高搜尋效率而不考慮付出的巨大成本和代價，而是追求高效搜尋的同時兼顧到搜尋方案的經(jīng)濟性及合理性，因此筆者著力于研究海上搜尋船舶的最優(yōu)分配問題。

從上述的研究結果得出，優(yōu)化后得到的船舶分配方案解決了文獻[6]中參與搜尋的船舶只對子海域進行一次搜尋的局限性問題，使搜尋船舶得到了合理地使用。同時，研究得到的搜尋船舶分配方案在滿足以完成各子海域搜尋覆蓋時間期望總和最小為目標的條件下，實現(xiàn)了向包含概率不同的多個子海域合理分配搜尋船舶的目的?？梢姡瑑?yōu)化后所得到的船舶分配方案更加科學、合理，能為有關決策部門制定海上搜尋船舶分配方案提供更加科學、更符合實際的理論依據(jù)。