海上搜尋船舶分配問題優化研究

王 軍，楊春林，王美蓉

(大連海事大學 交通運輸工程學院， 遼寧 大連 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]中參與搜尋的船舶只對子海域進行一次搜尋的局限性問題，使搜尋船舶得到了合理地使用。同時，研究得到的搜尋船舶分配方案在滿足以完成各子海域搜尋覆蓋時間期望總和最小為目標的條件下，實現了向包含概率不同的多個子海域合理分配搜尋船舶的目的。可見，優化后所得到的船舶分配方案更加科學、合理，能為有關決策部門制定海上搜尋船舶分配方案提供更加科學、更符合實際的理論依據。