王 杰，費 鵬，陳 凱

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

0 引 言

目前，中國已成為世界主要的遠洋漁業(yè)大國之一。遠洋漁船作業(yè)時，經(jīng)常會遇到生產(chǎn)生活物資供給不足、捕撈漁品無處存放等問題，影響到遠洋捕撈的效率。通過補給船的專業(yè)運輸，為海上作業(yè)漁船提供漁具、食物與燃油等生產(chǎn)生活物資，并將漁船的漁獲運回陸岸基地，可以有效解決上述問題。

針對補給船航線規(guī)劃問題，諸多學(xué)者進行了研究并將其視為車輛調(diào)度問題[1-2],曹守啟等[3]對靜態(tài)條件下遠洋漁船補給航路問題進行了研究，采用回歸分析法預(yù)測其完成生產(chǎn)工作的初始等待時間，建立關(guān)于航路和補給時間的多目標(biāo)優(yōu)化模型，使其能夠?qū)崿F(xiàn)補給船最大運輸效率。關(guān)于路徑優(yōu)化問題，彭鑫等[4]針對傳統(tǒng)的配送車輛路徑問題，增加客戶的混合時間窗和車輛在客戶點的服務(wù)時間，基于此構(gòu)建車輛路徑問題的數(shù)學(xué)模型；張文博等[5]通過針對動態(tài)需求下帶時間窗的車輛路徑問題，以最小配送成本為目標(biāo)，使用兩階段規(guī)劃策略進行求解；B.J. POWEL等[6]綜合考慮船隊在航行過程中所遇到的多種影響因素，結(jié)合線性規(guī)劃和整數(shù)規(guī)劃建立混合優(yōu)化模型；陳龍等[7]采用動態(tài)規(guī)劃法，構(gòu)建在多個階段進行投資決策的遠洋漁船編隊優(yōu)化網(wǎng)絡(luò)模型。綜上，國內(nèi)外關(guān)于路徑優(yōu)化問題研究較多，但針對補給船航線規(guī)劃的研究卻寥寥無幾，且沒有綜合考慮遠洋漁船的時間約束以及動態(tài)需求[8]。為此，針對補給船的航線規(guī)劃問題進行探討，具有較大的研究空間和現(xiàn)實意義。

主要研究補給船的最優(yōu)補給航線問題，以補給成本最小為目標(biāo)函數(shù)，構(gòu)建基于混合時間窗下需求動態(tài)變化的補給船航線規(guī)劃模型，提高補給效率及優(yōu)化服務(wù)。

1 問題描述及模型建立

1.1 問題闡述

海上環(huán)境復(fù)雜多變，遠洋漁船作業(yè)及其補給特點鮮明。一是遠洋漁船通常組成捕撈船隊，聚集在漁場附近活動，空間位移相對較?。欢菑拈L期來看，遠洋漁場資源豐富，所捕漁獲量具有連續(xù)性，利于預(yù)測；三是為增加捕撈時間，遠洋漁船通常會把之前所打撈的漁獲由補給船捎回，末期部分漁獲會由漁船返程時自行帶回。

基于此，補給船根據(jù)任務(wù)目標(biāo)依次給待補給漁船運送生產(chǎn)生活物資，并將漁獲帶回。管理人員在安排補給航線時，需要考慮以下因素：一是補給船到達時間是否會影響到漁船正常作業(yè)，若在漁船生產(chǎn)生活物資耗盡后到達，漁船人員的生產(chǎn)生活將陷入困境；若在漁獲滿載后到達，將增加漁船非作業(yè)等待時間；二是在補給船進行補給時，漁船會持續(xù)進行海上作業(yè)，船上的生產(chǎn)生活物資以及漁獲量也會產(chǎn)生相應(yīng)變化。因此，補給船管理者要合理安排補給方案，提高補給船的作業(yè)效率。

1.2 模型假設(shè)

由于受到海洋復(fù)雜環(huán)境的影響，補給船的補給作業(yè)也會受到各種因素的干擾，因此筆者做出以下假設(shè)：

1)補給船對于補給方案的處理以及補給船調(diào)度所需時間忽略不計。

2)數(shù)條補給船在接到任務(wù)時，開始從同一地點出發(fā)，并以經(jīng)濟航速行進，且最大載貨量、最遠航行距離基本保持一致，不受周圍環(huán)境等因素影響。

3)補給船開始補給作業(yè)時，漁船與補給船之間的相對距離不變。

4)漁船的生產(chǎn)生活物資消耗量和捕撈量具有一定的連續(xù)性。

5)補給船完成補給任務(wù)后返回出發(fā)地。

1.3 補給船航線規(guī)劃模型建立

綜合考慮補給船受到補給時間的限制以及漁船作業(yè)的特點，提出構(gòu)建混合時間窗下需求動態(tài)變化的補給船航線規(guī)劃模型。

1.3.1 懲罰函數(shù)

補給船的主要任務(wù)是保證遠洋捕撈人員的正常生活要求，減少漁船非作業(yè)等待時間，為此在構(gòu)建目標(biāo)函數(shù)時，建立懲罰成本函數(shù)。將漁船的剩余生產(chǎn)生活物資使用時間用T1表示，漁船的漁獲滿艙時間用T2表示。

1)當(dāng)T1≤T2時

在此情況下，補給船的時間限制為硬時間窗，其懲罰函數(shù)如圖1，具體懲罰函數(shù)為：

圖1 T1≤T2Fig. 1 T1≤T2

(1)

其中M為比較大的正數(shù)。經(jīng)整理得：

f1(tia)=Mmax(tia-T1,0)

(2)

2)當(dāng)T1>T2時

當(dāng)補給船的到達時間在T2、T1之間時會產(chǎn)生懲罰成本，且偏離T2越大，其懲罰成本越高，但到達時間不能大于T1。在此時間段內(nèi)，假設(shè)懲罰成本為線性增長，其懲罰函數(shù)如圖2，具體懲罰函數(shù)為：

圖2 T1>T2Fig. 2 T1>T2

(3)

其中M為足夠大的正數(shù)。經(jīng)整理得：

tia>0

(4)

綜合1)、2)兩種情況，統(tǒng)一得出其懲罰函數(shù)為：

(5)

式中：tia為補給船a到達漁船i位置所用的時間；P為補給船受到的單位時間懲罰值。

1.3.2 漁船的物資需求量和漁獲變化量

補給船的到達時間直接影響著漁船的實際生產(chǎn)生活物資需求量和漁獲卸載量，而到達時間由補給船的海上航行時間和對之前漁船的服務(wù)時間決定。因此當(dāng)補給船a到達漁船i時，其生產(chǎn)生活物資實際需求量應(yīng)為初始需求量與增加量之和；漁獲的實際卸載量應(yīng)為初始漁獲量與增加量之和。漁船的實際生產(chǎn)生活物資需求量以及漁獲卸貨量計算公式為：

(6)

(7)

式(6)為漁船的實際生產(chǎn)生活物資需求量；式(7)為漁船的實際漁獲卸載量。

1.3.3 優(yōu)化模型建立

根據(jù)以上分析，筆者以最小補給成本作為目標(biāo)函數(shù)，漁船生產(chǎn)生活物資需求量和漁獲卸載量函數(shù)為主要約束條件之一，構(gòu)建以下優(yōu)化模型：

(8)

s.t.

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

式中：Z為總補給成本；q為補給船每行駛一個單位距離所需要的運輸成本；H為補給船所能夠行駛的最遠距離；Q為補給船所能夠允許的最大裝載量；s為補給船總數(shù)量；g為補給船的每一單位裝卸所需要的成本；n為需要補給船給其補給的漁船數(shù)量；na為補給船a服務(wù)的漁船數(shù)量。

式(8)為目標(biāo)函數(shù)，由補給船運輸成本、裝卸成本和懲罰成本組成；式(9)為每艘補給船的最遠運輸距離限制；式(10)為每艘補給船裝載的生產(chǎn)生活物資總量不能超過補給船的最大載貨量；式(11)為每艘補給船裝載的漁獲總量不能超過補給船的最大載貨量；式(12)為補給船總的最大載貨量限制；式(13)為等待補給的漁船數(shù)量限制；式(14)、式(15)為一艘漁船由且僅由一艘補給船提供補給；式(16)為補給船的航行路線構(gòu)成一個閉環(huán)；式(17)為補給船a到達漁船j位置所用的時間；式(18)為對決策變量cija進行約束。

2 模型算法設(shè)計

遺傳算法是一種典型的迭代算法，在實際運用中會出現(xiàn)局部搜索能力較差，容易早熟的現(xiàn)象。筆者把Tent混沌映射與遺傳算法相結(jié)合，構(gòu)造改進遺傳算法，改變傳統(tǒng)遺傳算法群體適應(yīng)值差別較大的現(xiàn)象。

2.1 編碼方法

采用簡單直觀的自然數(shù)編碼方法，以“0”表示補給船的出發(fā)地，n個自然數(shù)(1,2,…n)表示n個等待補給的漁船，一個染色體表示一個解決方案。

2.2 初始化種群

利用Tent混沌映射對種群進行初始化。利用Tent映射式(19)對其進行混沌擾動，產(chǎn)生混沌變量，然后根據(jù)式(20)將其映射到所要優(yōu)化變量的取值范圍內(nèi)并取整，選擇相應(yīng)個體作為初始種群[9-10]。

(19)

gij=|1+(n-1)xij|,i=1,2,…S；j=1,2,…n

(20)

2.3 計算生產(chǎn)生活物資需求量和漁獲卸載量

當(dāng)初始種群確定后，由式(6)、式(7)計算每艘待補給漁船在該條航線中的生產(chǎn)生活物資實際需求量和漁獲卸載量。

2.4 確定適應(yīng)度函數(shù)

在確定適應(yīng)度函數(shù)時，由于目標(biāo)函數(shù)Z要求取最小值，且適應(yīng)度越大越好，因此將目標(biāo)函數(shù)值的倒數(shù)定位為適應(yīng)度函數(shù)。

2.5 遺傳操作

遺傳操作包括選擇操作、交叉操作和變異操作。一是選擇操作，筆者采用輪盤賭選擇法；二是交叉操作，采用部分匹配交叉法進行交叉操作，隨機在父代個體選擇一個區(qū)域進行互換；三是變異操作，采用逆轉(zhuǎn)變異法，在準(zhǔn)備變異的父代個體隨機選定變異區(qū)域進行逆轉(zhuǎn)操作，從而形成一個新的基因串。

2.6 終止條件

采用設(shè)定最大進化代數(shù)的方法作為終止準(zhǔn)則。

3 算例分析

我國通常由10～40艘遠洋漁船組成一定規(guī)模的船隊，進行遠洋捕撈作業(yè)。為此，選取某一時刻，有18艘遠洋漁船需要補給船為其開展補給作業(yè)，此時有4艘補給船可以參與此次補給任務(wù)。每艘補給船的載貨量Q均為3 500 t，補給船可以航行的最遠距離H為5 000海里，經(jīng)濟航速v0為15 kn，每行駛一海里所需要成本為130元，單位裝卸成本為7.6元/噸。通過對漁船單小時所捕魚貨價值、生產(chǎn)生活物資消耗等各種費用預(yù)估，計算單小時懲罰成本為210元。漁船和補給船的其它參數(shù)如表1、表2。

表1 等待補給的漁船參數(shù)Table 1 Fishing boat parameters waiting for replenishment

表2 補給船出發(fā)地與漁船之間的距離Table 2 Distance between the starting point of the replenishment ship and the fishing boat 海里

通過MATLAB R2016a編程實現(xiàn)改進遺傳算法，在算法計算中，種群規(guī)模設(shè)置為200代，交叉概率為0.8，變異概率為0.1，迭代次數(shù)為800代，運行迭代結(jié)果如圖3。

圖3 改進遺傳算法適應(yīng)度曲線Fig. 3 Improved genetic algorithm fitness curve

此次任務(wù)共需向遠洋漁船補給生產(chǎn)生活物資1 291 t，返回時共裝載10 632 t漁獲物，補給總成本為61.694 1萬元。

補給船Ⅰ的補給順序為0—12—8—16—2—0，出發(fā)時共需載漁船所需生產(chǎn)生活物資287 t，返航時共載回漁獲2 292 t，返航裝載率為65.49%，裝載率較低。因此在進行補給時，可以考慮使用多種船型，讓載貨量低的補給船服務(wù)節(jié)點少的航線。

補給船Ⅱ的補給順序為0—3—17—11—14—0，出發(fā)時共需載漁船所需生產(chǎn)生活物資300 t，返航時共載回漁獲2 502 t，返航裝載率為71.49%。

補給船航線規(guī)劃方案如表3。

表3 補給船航線規(guī)劃方案Table 3 Route planning of replenishment ship

補給船Ⅲ的補給順序為0—10—18—6—4—9—0，出發(fā)時共需載漁船所需生產(chǎn)生活物資347 t，返航時共載回漁獲2 864 t，返航裝載率為81.83%。

補給船Ⅳ的補給順序為0—13—7—5—1—15—0，出發(fā)時共需載漁船所需生產(chǎn)生活物資357 t，返航時共載回漁獲2 974 t，返航裝載率為84.97%。

4 結(jié) 語

在滿足遠洋漁船正常補給需求的條件下，補給船到達時間的長短將直接影響到補給成本和補給效率，因此合理安排補給方案，既能保證漁船作業(yè)的正常進行，也有利于提高補給船的補給效率。在分析補給成本的基礎(chǔ)上，建立混合時間窗下的懲罰成本函數(shù)以及生產(chǎn)生活物資實際消耗量和漁獲增長量函數(shù)，構(gòu)建補給船航線規(guī)劃模型，最后利用改進遺傳算法進行求解，得出補給成本較低的優(yōu)化方案，有助于提升補給船的補給效率。