面向遠海島嶼的救助基地選址優化模型及其算法

王翊萱, 王 諾, 高忠印, 吳 迪, 林婉妮

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

0 引言

所謂遠海島嶼，是指遠離大陸，難以直接獲得陸地支援的島嶼。當遠海發生海難事故時，由于海上人命救助的時效性極強，救援的黃金時機稍縱即逝，從大陸救助基地調遣救援力量趕赴現場施救效率過低，因而需要在遠海島嶼設立救助基地以縮短馳援時間[1]。但因遠海救助基地投資巨大，所以涉及諸多問題一直難以解決[2]。隨著我國海運的迅速發展，海上航行安全的重要性日益凸顯，在遠海海域選擇島礁建設救助基地已成為當前亟需解決的重要問題，這對于提高遠海海上的響應能力具有重要意義。

有關海上救助值班點的選擇問題，目前已有部分研究成果，如基于加權費馬點原理，建立針對南海的救助動態值點選址模型[3]；利用P-中值建立了應急救助站點選址模型[4]。關于海上救助力量的配置問題，有的學者針對海上溢油應急處置問題提出了一套相應的應急船舶調度方案[5]，通過分析船舶的分布密度、類型、性能和地理因素等分配搜救資源[6]。關于救助基地的選址問題也有一些可供借鑒的成果，如以受災點的需求為變量，以救援時間為約束，建立以總運輸成本最小為目標的應急救援中心選址模型[7]。近年來，關于GIS在海事救助領域的應用研究也有所增加，其內容主要包括模擬浮標漂移軌跡、確定搜索區域以及跟蹤漂移浮標運動，對目標實時監控和信息化管理，提高應對海上突發事故的能力[8,9]等。

分析以上文獻可以看到，盡管相關研究已有一些成果，但在面向遠海島嶼進行救助地基選址的優化方法研究方面仍存在明顯空白。有鑒于此，本文以遠海島嶼優化救助基地選址為研究目標，以海域救助值班點選擇、救助船舶配置及救助基地建設成本估算為基本內容，以建設運營總成本最低和對過往商船覆蓋率最大為優化目標，結合現代技術手段，提出了新的優化模型和求解方法，其主要工作和貢獻是：①基于GIS空間分析功能，采用模糊C-均值聚類算法對研究區海域往來船舶密度進行聚類，求出救助動態值班點的較佳分布；②從整個邊遠海域救助系統角度出發，建立考慮建設總成本最小和過往商船覆蓋率最大的雙目標優化模型；③引入自適應拉伸的擁擠距離公式，設計了自適應精英保留策略的NSGA-II算法對模型進行求解。最后，以我國南沙島礁群救助基地選址及配置救助船舶為例，驗證了本文優化模型和算法的可行性和有效性。

1 模型分析

1.1 問題描述

本文需優化的目標有兩個，一是如何選擇海上救助值班點，使其對過往船舶的覆蓋面盡可能地大，以提高海上救援效率；二是如何選擇可提供救助船舶停泊的基地數量和位置，使其建設和運營成本盡可能地少，以節省救援設施的費用。為此，本文面臨的問題是：①若動態值班點的數量過少，則對遠海海域的覆蓋面積減小，若偏遠海域發生海難，則救助船舶無法在最短時間內趕到，救助成功率降低；而若動態值班點數量過多，則需配備更多的救助船舶，其成本勢必會增加，因此如何確定動態值班點的數量及位置是需要解決的第1個問題；②因我國大型救助船舶的數量較少，若在每個值班點均配置大型救助船舶，則需要更高的購置成本；而若配置中型救助船舶，又難以達到理想的救助海域覆蓋率，因此如何為每個值班點配置適當船型是需要解決的第2個問題；③若選擇只建設1個救助船舶基地，雖會明顯降低泊位的建設成本，但勢必造成動態值班點與基地的距離過遠，使得救助船舶回基地補給的航行時間增加、運行效率降低；而若建設多個救助基地，則初期投資成本將激增，因此如何確定救助基地的數量與位置是需要解決的第3個問題。上述3個問題涉及的變量眾多，且相互交叉，因而需統籌優化。

1.2 符號設定

I表示商船集合，其編號i∈I；J表示動態值班點集合，其編號j∈J；K表示島礁集合，其編號k∈K；P表示泊位類型集合，其編號p∈P；S表示救助船型集合，其編號s∈S；xi表示商船i的位置；yj表示動態值班點j的位置；U表示隸屬度集合；uij表示商船i隸屬于動態值班點j的隸屬度，且有uij∈[0,1]，uij∈U；Ij表示動態值班點j覆蓋的商船集合(Ij?I)；Pk表示島礁k可以建設的泊位類型集合(Pk?P)；Sp表示p類型泊位可以掛靠的救助船型集合(Sp?S)；dij表示商船i與動態值班點j的距離；ljk表示動態值班點j與島礁k的距離；αp表示各島礁建設p類型泊位所需的單位建設成本；τ表示臨界響應時間閾值，即海上人命存活最大時間；vs表示s型救助船舶的速度；βs表示s型救助船舶的單位購置成本；δs表示s型救助船舶單位距離航行成本；δs表示s型救助船舶年運營成本；C表示各島礁建設救助基地的固定成本；Qs表示s型救助船舶的最大數量；Ukp表示島礁k可建設p類型泊位的最大數量；γ表示0-1變量，用于調節約束條件；Wk表示0-1變量，當島礁k被選為救助基地時Wk=1，否則Wk=0；Zkp表示整數變量，島礁k建設p類型泊位的數量；Xjs表示0-1變量，當為動態值班點j配置s型救助船舶時Xjs=1，否則Xjs=0；Yjk表示0-1變量，當動態值班點j的救助船依托島礁k的救助基地時Yjk=1，否則Yjk=0。

1.3 模型建立

1.3.1 海上救助動態值班點選擇模型

根據海上救助船舶資源現狀及航行商船密度分布，以各艘商船到各個動態值班點的加權距離之和最小為目標，建立海上救助船舶動態值班點選擇模型，即：

(1)

(2)

其中，式(1)為目標函數，表示各個商船到各個動態值班點的加權距離之和最??；式(2)表示各個商船到所有動態值班區域的隸屬度之和為1。

1.3.2 海上救助船舶配置及救助基地選址模型

基于式(1)得到的海上救助動態值班點的位置坐標，以總投資成本最少和過往商船覆蓋率最大為目標，建立海上救助船舶配置和救助基地選擇模型，即：

(3)

(4)

s.t.Ij={i|i∈I,Xjsvs/dij≤τ}

(5)

WkZkp≥Zkp,?k∈K;?p∈P

(6)

Zkp≤Ukp,?k∈K;?p∈P

(7)

(8)

(9)

(10)

(11)

(12)

Zkp≤M(1-γ),?k∈K;?p∈P

(13)

(14)

(15)

其中，式(3)表示總成本最小，其中依次為建設救助基地固定成本、泊位建設成本、救助船舶的購置和運營成本、救助船舶航行成本；式(4)表示過往商船覆蓋率最大。式(5)～式(15)為約束條件。式(5)表示在動態值班點j處配置s型救助船舶所能覆蓋的過往商船必須在其臨界響應時間范圍內；式(6)表示只有當島礁被選定為救助基地時才能建設泊位；式(7)表示在島礁k建設p類型泊位的數量必須要小于等于其所能建設的最大數量；式(8)表示島礁k可建設的泊位類型必須在其自身條件限制內；式(9)表示救助船舶數量限制；式(10)表示動態值班點j上最多只允許配置1艘救助船舶；式(11)表示如果動態值班點j沒有配置救助船舶，則不需要依托救助基地；式(12)表示動態值班點j配置了救助船舶后，必須且只能依托一個救助基地；式(13)和式(14)表示動態值班點j選擇依托的救助基地必須有能供其s型救助船舶掛靠的泊位類型；式(15)表示島礁k建設的泊位數量必須能夠供選擇該島礁作為依托的救助船舶同時掛靠。

2 計算方法

2.1 海上動態值班點選擇計算模塊

要劃分海上動態值班點，其優化思路是以各過往商船到動態值班點的加權距離最短為目標，將商船劃分為不同類別，以實現選取適當的各類別中心點將其作為動態值班點。本文采用模糊C-均值聚類算法進行分析，該算法通過優化目標函數得到每個樣本點對所有類中心的隸屬度，從而實現對樣本數據進行分類。為此，令式(1)中的Gf分別對yj和uij求偏導，取偏導數為0作為其極小值的必要條件，最終得到隸屬度矩陣U*和值班點集合J*，其表達式如下:

(16)

(17)

其中，式(16)計算動態值班點的坐標，式(17)計算各個商船的隸屬度，在[0,1]之間的隨機數初始化隸屬度矩陣，式中其他符號意義同上。

2.2 海上救助船舶配置及救助基地選址計算模塊

2.2.1 染色體設置

本文編碼染色體包括4部分信息：①各動態值班點配置的救助船舶類型；②可被選為救助基地的島礁編號；③各動態值班點救助船舶所依托的救助基地編號；④被選為救助基地后應建設何種類型的泊位編號，以及每種類型泊位應建設的數量。為表達上述信息，本文構造2條染色體，如圖1所示。

2.2.2 算法改進

對于本文問題，傳統的NSGA-II算法存在解集收斂性和分布性較差的缺陷，使得求解時難以有效獲得優質的Pareto非劣解。因此，為使得算法能夠得到分布性較好且更為優質的解，本文從分布性和精英保留策略兩方面對算法進行改進。

對于分布性，NSGA-II的擁擠距離計算公式如下:

(18)

NSGA-II算法在運行初期，因個體差異較大，所以利用式(18)可以獲得較好的效果。但在運行后期，會出現優秀個體優勢不足，不利于解集形成較好的分布性。為彌補這一缺陷，本文提出一種自適應拉伸擁擠距離，其計算式為:

(19)

其中，N為種群中個體數量，T0為初始溫度，λ為降溫影響因子，k為迭代次數。

對于精英保留策略，由于傳統的NSGA-II算法在選取精英個體規模時存在兩難選擇：若選取規模較小，則容易失去優良的個體；若選取規模過大，則影響下一代的多樣性。對此，本文提出一種自適應精英保留的策略，其計算式為:

Ek=N×αk

(20)

其中，αk表示第k代進化過程中精英保留規模的影響因子，Ek表示第k代進化中精英個體的數量，N為種群規模。αk的自適應迭代公式如下:

αk=αmin+k(αmax-αmin)/Rmax

(21)

其中，Rmax表示最大迭代次數，αmax取0.8，αmin取0.2。

2.3 最優解選擇

利用以上算法可以得到一組Pareto非劣解集，但若要得出最優解，還需根據決策者的偏好進行選取。為此，本文參照文獻[10]的成果，根據Pareto前沿的幾何分布特點，選擇相對于兩個優化目標平均變化率最靈敏的交點所對應的解，即為性價比最優的解。

2.4 計算步驟

本文算法流程如圖2所示。

3 實例分析

現以我國將在南沙群島海域就建設救助基地選址和救助船舶配置的優化過程為例進行分析。

3.1 基礎數據

關于南海南沙群島附近海域(2°00′N～14°00′N，105°00′E～119°50′E)中過往商船的分布數據來源于美國國家海洋和大氣管理局[11]，結合南沙群島的自然條件，對各島礁可建的泊位規模進行評估(表1)。

表1 南沙主要島礁位置及可建設泊位條件

對于救助船舶的配置，按照我國《海事船舶配備管理規定》中關于救助船舶的配置標準，因南沙群島海況惡劣，只有60米級及以上較大類型的救助船舶可以承擔邊遠海域的應急任務[12]。考慮到目前我國能夠承擔遠海巡邏任務的60米級以上中大型救助船舶約10艘左右[13]，因此本文以10艘救助船舶為基數進行配置計算，其代表船型的基本參數見表2。

表2 救助船舶船型、性能及營運成本有關參數

3.2 計算結果

使用Python語言編程，選用處理器為8G inter(R) i7-8750H，運行環境為ArcMap 10.6。根據模糊C-均值聚類算法對船舶數據進行聚類，得到10個類，每個類的動態值班點坐標見表3。設救助船舶臨界響應時間閾值δ=5h，NSGA-II算法的種群數量為30，交叉概率0.8，變異概率0.05，迭代次數500次。

表3 動態值班點坐標

經計算得到Pareto解的偏向度見表4，其中，Pareto解偏向度最小的方案為2#方案，其最優方案為：①關于救助基地選址：可在永暑島建設泊位4個，其中，4000噸級泊位1個、2000噸級泊位1個、1000噸級泊位2個；在華陽島建設泊位2個，其中，2000噸級泊位1個、1000噸級泊位1個；在渚碧島建設泊位4個，其中，2000噸級泊位3個、1000噸級泊位1個；在赤瓜島、美濟島、東門島、南薰島不建設基地(表5)；②關于救助船舶配置：在動態值班點1#配置100m級救助船舶1艘；在動態值班點2#、3#、4#、6#、8#各配置80m級救助船舶1艘；在動態值班點5#、7#、9#、10#各配置60m級救助船舶1艘；③關于動態值班點的依托基地：前往動態值班點1#、4#、7#、9#的救助船舶依托永暑島救助基地；前往動態值班點2#、3#、5#、6#的救助船舶依托渚碧島救助基地；前往動態值班點8#、10#的救助船舶依托華陽島救助基地(圖3)。

表4 Pareto非劣解集對應的參數表

表5 各島嶼救助船舶泊位建設方案

注：該圖基于國家測繪地理信息局標準地圖服務網站下載的審圖號為GS(2016)1609號的標準地圖制作，底圖無修改。

3.3 算法比較

為驗證算法改進后在擴大規模情況下的計算效果，以上述算例和算法參數為基礎，采用2組不同規模算例進行對比，設算例1為10個動態值班點、7個候選救助基地；設算例2為15個動態值班點、7個候選救助基地。計算結果顯示：從計算10次得到的SP(間距指標)值上來看，本文算法求得的SP指標在平均值上改進幅度為23.09%～27.64%、在最小值上改進幅度為18.10%～31.53%、在標準差上改進幅度15.99%～33.38%，表明本文算法求得的解集均勻性較好(表6)。綜上，改進NSGA-II算法獲得解的優化結果更好，且具有良好的分布性(圖4)。

表6 算法改進前后不同規模計算結果對比

4 結論

本文面向我國當前亟需解決的科學問題，以遠海島嶼優化救助基地選址為背景，以海域救助值班點選擇、救助船舶配置及救助基地建設成本優化為基本內容，以建設運營總成本最低和對過往商船覆蓋率最大為優化目標，建立考慮建設總成本最小和過往商船覆蓋率最大的雙目標優化模型?；贕IS的空間分析功能，采用模糊C-均值聚類算法對研究區海域往來船舶密度進行聚類，求出救助動態值班點的較佳分布；引入自適應拉伸的擁擠距離公式設計自適應精英保留策略的NSGA-II算法對模型進行求解。通過我國在南沙島礁群案例，驗證了本文模型及算法的可行性，從而為我國海上島嶼救助基地選址和在救助資源有限的情況下如何科學配置提供了分析方法。

需要指出，本文僅以救助船舶為救援主體開展研究，而實際中救助力量還配備有直升機等救援工具，此種情況下救助動態值班點選擇、救助力量配置、救助基地選址等的優化模型將會更加復雜，此類問題是下一步需要研究的內容。