面向遠(yuǎn)海島嶼的救助基地選址優(yōu)化模型及其算法

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

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院,遼寧 大連 116026)

0 引言

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

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

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

1 模型分析

1.1 問題描述

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

1.2 符號(hào)設(shè)定

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

1.3 模型建立

1.3.1 海上救助動(dòng)態(tài)值班點(diǎn)選擇模型

根據(jù)海上救助船舶資源現(xiàn)狀及航行商船密度分布，以各艘商船到各個(gè)動(dòng)態(tài)值班點(diǎn)的加權(quán)距離之和最小為目標(biāo)，建立海上救助船舶動(dòng)態(tài)值班點(diǎn)選擇模型，即：

(1)

(2)

其中，式(1)為目標(biāo)函數(shù)，表示各個(gè)商船到各個(gè)動(dòng)態(tài)值班點(diǎn)的加權(quán)距離之和最??；式(2)表示各個(gè)商船到所有動(dòng)態(tài)值班區(qū)域的隸屬度之和為1。

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

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

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

2 計(jì)算方法

2.1 海上動(dòng)態(tài)值班點(diǎn)選擇計(jì)算模塊

要?jiǎng)澐趾Ｉ蟿?dòng)態(tài)值班點(diǎn)，其優(yōu)化思路是以各過往商船到動(dòng)態(tài)值班點(diǎn)的加權(quán)距離最短為目標(biāo)，將商船劃分為不同類別，以實(shí)現(xiàn)選取適當(dāng)?shù)母黝悇e中心點(diǎn)將其作為動(dòng)態(tài)值班點(diǎn)。本文采用模糊C-均值聚類算法進(jìn)行分析，該算法通過優(yōu)化目標(biāo)函數(shù)得到每個(gè)樣本點(diǎn)對(duì)所有類中心的隸屬度，從而實(shí)現(xiàn)對(duì)樣本數(shù)據(jù)進(jìn)行分類。為此，令式(1)中的Gf分別對(duì)yj和uij求偏導(dǎo)，取偏導(dǎo)數(shù)為0作為其極小值的必要條件，最終得到隸屬度矩陣U*和值班點(diǎn)集合J*，其表達(dá)式如下:

(16)

(17)

其中，式(16)計(jì)算動(dòng)態(tài)值班點(diǎn)的坐標(biāo)，式(17)計(jì)算各個(gè)商船的隸屬度，在[0,1]之間的隨機(jī)數(shù)初始化隸屬度矩陣，式中其他符號(hào)意義同上。

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

2.2.1 染色體設(shè)置

本文編碼染色體包括4部分信息：①各動(dòng)態(tài)值班點(diǎn)配置的救助船舶類型；②可被選為救助基地的島礁編號(hào)；③各動(dòng)態(tài)值班點(diǎn)救助船舶所依托的救助基地編號(hào)；④被選為救助基地后應(yīng)建設(shè)何種類型的泊位編號(hào)，以及每種類型泊位應(yīng)建設(shè)的數(shù)量。為表達(dá)上述信息，本文構(gòu)造2條染色體，如圖1所示。

2.2.2 算法改進(jìn)

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

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

(18)

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

(19)

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

對(duì)于精英保留策略，由于傳統(tǒng)的NSGA-II算法在選取精英個(gè)體規(guī)模時(shí)存在兩難選擇：若選取規(guī)模較小，則容易失去優(yōu)良的個(gè)體；若選取規(guī)模過大，則影響下一代的多樣性。對(duì)此，本文提出一種自適應(yīng)精英保留的策略，其計(jì)算式為:

Ek=N×αk

(20)

其中，αk表示第k代進(jìn)化過程中精英保留規(guī)模的影響因子，Ek表示第k代進(jìn)化中精英個(gè)體的數(shù)量，N為種群規(guī)模。αk的自適應(yīng)迭代公式如下:

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

(21)

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

2.3 最優(yōu)解選擇

利用以上算法可以得到一組Pareto非劣解集，但若要得出最優(yōu)解，還需根據(jù)決策者的偏好進(jìn)行選取。為此，本文參照文獻(xiàn)[10]的成果，根據(jù)Pareto前沿的幾何分布特點(diǎn)，選擇相對(duì)于兩個(gè)優(yōu)化目標(biāo)平均變化率最靈敏的交點(diǎn)所對(duì)應(yīng)的解，即為性價(jià)比最優(yōu)的解。

2.4 計(jì)算步驟

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

3 實(shí)例分析

現(xiàn)以我國(guó)將在南沙群島海域就建設(shè)救助基地選址和救助船舶配置的優(yōu)化過程為例進(jìn)行分析。

3.1 基礎(chǔ)數(shù)據(jù)

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

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

對(duì)于救助船舶的配置，按照我國(guó)《海事船舶配備管理規(guī)定》中關(guān)于救助船舶的配置標(biāo)準(zhǔn)，因南沙群島海況惡劣，只有60米級(jí)及以上較大類型的救助船舶可以承擔(dān)邊遠(yuǎn)海域的應(yīng)急任務(wù)[12]?？紤]到目前我國(guó)能夠承擔(dān)遠(yuǎn)海巡邏任務(wù)的60米級(jí)以上中大型救助船舶約10艘左右[13]，因此本文以10艘救助船舶為基數(shù)進(jìn)行配置計(jì)算，其代表船型的基本參數(shù)見表2。

表2 救助船舶船型、性能及營(yíng)運(yùn)成本有關(guān)參數(shù)

3.2 計(jì)算結(jié)果

使用Python語言編程，選用處理器為8G inter(R) i7-8750H，運(yùn)行環(huán)境為ArcMap 10.6。根據(jù)模糊C-均值聚類算法對(duì)船舶數(shù)據(jù)進(jìn)行聚類，得到10個(gè)類，每個(gè)類的動(dòng)態(tài)值班點(diǎn)坐標(biāo)見表3。設(shè)救助船舶臨界響應(yīng)時(shí)間閾值δ=5h，NSGA-II算法的種群數(shù)量為30，交叉概率0.8，變異概率0.05，迭代次數(shù)500次。

表3 動(dòng)態(tài)值班點(diǎn)坐標(biāo)

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

表4 Pareto非劣解集對(duì)應(yīng)的參數(shù)表

表5 各島嶼救助船舶泊位建設(shè)方案

注：該圖基于國(guó)家測(cè)繪地理信息局標(biāo)準(zhǔn)地圖服務(wù)網(wǎng)站下載的審圖號(hào)為GS(2016)1609號(hào)的標(biāo)準(zhǔn)地圖制作，底圖無修改。

3.3 算法比較

為驗(yàn)證算法改進(jìn)后在擴(kuò)大規(guī)模情況下的計(jì)算效果，以上述算例和算法參數(shù)為基礎(chǔ)，采用2組不同規(guī)模算例進(jìn)行對(duì)比，設(shè)算例1為10個(gè)動(dòng)態(tài)值班點(diǎn)、7個(gè)候選救助基地；設(shè)算例2為15個(gè)動(dòng)態(tài)值班點(diǎn)、7個(gè)候選救助基地。計(jì)算結(jié)果顯示：從計(jì)算10次得到的SP(間距指標(biāo))值上來看，本文算法求得的SP指標(biāo)在平均值上改進(jìn)幅度為23.09%～27.64%、在最小值上改進(jìn)幅度為18.10%～31.53%、在標(biāo)準(zhǔn)差上改進(jìn)幅度15.99%～33.38%，表明本文算法求得的解集均勻性較好(表6)。綜上，改進(jìn)NSGA-II算法獲得解的優(yōu)化結(jié)果更好，且具有良好的分布性(圖4)。

表6 算法改進(jìn)前后不同規(guī)模計(jì)算結(jié)果對(duì)比

4 結(jié)論

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

需要指出，本文僅以救助船舶為救援主體開展研究，而實(shí)際中救助力量還配備有直升機(jī)等救援工具，此種情況下救助動(dòng)態(tài)值班點(diǎn)選擇、救助力量配置、救助基地選址等的優(yōu)化模型將會(huì)更加復(fù)雜，此類問題是下一步需要研究的內(nèi)容。