王 杰，費(fèi) 鵬，陳 凱

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

0 引 言

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

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

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

1 問題描述及模型建立

1.1 問題闡述

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

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

1.2 模型假設(shè)

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

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

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

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

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

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

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

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

1.3.1 懲罰函數(shù)

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

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

在此情況下，補(bǔ)給船的時(shí)間限制為硬時(shí)間窗，其懲罰函數(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時(shí)

當(dāng)補(bǔ)給船的到達(dá)時(shí)間在T2、T1之間時(shí)會(huì)產(chǎn)生懲罰成本，且偏離T2越大，其懲罰成本越高，但到達(dá)時(shí)間不能大于T1。在此時(shí)間段內(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為補(bǔ)給船a到達(dá)漁船i位置所用的時(shí)間；P為補(bǔ)給船受到的單位時(shí)間懲罰值。

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

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

(6)

(7)

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

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

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

(8)

s.t.

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

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

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

2 模型算法設(shè)計(jì)

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

2.1 編碼方法

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

2.2 初始化種群

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

(19)

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

(20)

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

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

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

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

2.5 遺傳操作

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

2.6 終止條件

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

3 算例分析

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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