李明峰， 王勝正， 謝宗軒

(上海海事大學(xué) 商船學(xué)院， 上海 201306)

隨著計(jì)算機(jī)和智能技術(shù)的不斷發(fā)展，氣象導(dǎo)航技術(shù)得到越來越多的關(guān)注。氣象導(dǎo)航是指根據(jù)準(zhǔn)確有效的天氣和海洋預(yù)報(bào)及大洋氣候資料，并結(jié)合船舶相關(guān)信息和航次信息等，為船舶航行設(shè)計(jì)出最佳的氣象航線。[1]近年來，隨著對能效的要求不斷提高，航運(yùn)業(yè)對氣象導(dǎo)航的要求越來越高。在氣象航線優(yōu)化過程中，不僅要同時(shí)對航路和航速進(jìn)行優(yōu)化，而且要綜合考慮油耗、航行時(shí)間和航行安全等多個(gè)目標(biāo)。因此，氣象航線優(yōu)化是一種復(fù)雜的多變量、多動態(tài)約束、多目標(biāo)問題。

在氣象導(dǎo)航和航線優(yōu)化方面，國內(nèi)外學(xué)者開展了許多研究。傳統(tǒng)的規(guī)劃算法有：一方面主要基于Dijkstra和A*算法進(jìn)行航線優(yōu)化，例如：PARK等[2]以最低油耗為優(yōu)化目標(biāo)，先設(shè)定船舶航速恒定并使用A*算法調(diào)節(jié)航線轉(zhuǎn)向點(diǎn)的位置，再結(jié)合幾何規(guī)劃法分配每個(gè)航段的航速，從而得到最優(yōu)航線；JOO等[3]先采用A*算法調(diào)節(jié)航線轉(zhuǎn)向點(diǎn)位置，并以氣象數(shù)據(jù)為基礎(chǔ)，采用Dijkstra算法優(yōu)化每個(gè)航段的航速，而實(shí)際情況中航路與航速是相互依賴的，分段優(yōu)化不是非常合理的方式。另一方面主要基于等時(shí)線、動態(tài)規(guī)劃及其改進(jìn)算法進(jìn)行航線優(yōu)化，例如：RAPHAEL等[4]以航行油耗最低為目標(biāo)，基于氣象預(yù)報(bào)圖提出一種三維動態(tài)規(guī)劃算法，該算法將船舶航行等效為多階段決策過程，將航線等效為一組有限的航路點(diǎn)，在船速恒定的情況下，通過分配航路點(diǎn)和到達(dá)航路點(diǎn)的時(shí)間尋找最優(yōu)航線；張進(jìn)峰等[5]充分考慮船舶在大風(fēng)浪中的風(fēng)增阻、波浪增阻和失速特征，建立基于動態(tài)規(guī)劃算法的近海船舶避臺航線優(yōu)化模型，在避讓臺風(fēng)的前提下，得到航行距離的最短航線；LIN等[6]提出一種基于三維修正等時(shí)線法(Three-Dimensional Modified Isochrone,3DMI)的多動態(tài)影響因素的船舶航線優(yōu)化法，采用浮動網(wǎng)格系統(tǒng)定義船舶航線優(yōu)化的時(shí)空布局，建立優(yōu)化模型，根據(jù)策略的不同，調(diào)整約束條件權(quán)重，尋找最優(yōu)航線。然而，這些算法多假設(shè)船舶恒速或等功率航行，并沒有涉及對每個(gè)航段航速的優(yōu)化。

近些年，很多智能算法被應(yīng)用到了航線優(yōu)化中。例如： WANG等[7]提出一種實(shí)數(shù)編碼遺傳算法(Genetic Algorithm, GA)，用于尋找航行時(shí)間最短的航線，該算法根據(jù)個(gè)體在排序群體中的位置進(jìn)行適應(yīng)度分配，極大地簡化了適應(yīng)度值的計(jì)算，同時(shí)引入一種混合變異算子來增強(qiáng)對最優(yōu)解的搜索并保持種群多樣性；余文曌等[8]針對GA在路徑規(guī)劃中出現(xiàn)過多搜索冗余和收斂效率低等問題，提出一種基于彈性網(wǎng)格改進(jìn)的GA，并將其應(yīng)用到無人艇路徑規(guī)劃中；TSOU等[9]建立模擬生物體最佳行為的路徑搜索模型，通過一個(gè)離散的網(wǎng)格系統(tǒng)和蟻群算法，以盡量減少燃料消耗和CO2排放量為目標(biāo)，獲得最優(yōu)的航線；陳立家等[10]針對蟻群算法計(jì)算量大和尋優(yōu)效率低下的問題，建立航線設(shè)計(jì)網(wǎng)絡(luò)模型，并對蟻群算法進(jìn)行改進(jìn)，對信息素濃度進(jìn)行人為控制，提出一種多約束條件下以航行綜合成本最低為目的的最優(yōu)航線生成算法；陳曉等[11]采用Maklink圖和Dijkstra算法產(chǎn)生初始路徑，減少蟻群算法的計(jì)算量，提高算法的尋優(yōu)效率；趙化川等[12]結(jié)合船舶失速計(jì)算公式和船舶臨界速度計(jì)算公式，分別建立航時(shí)最短、燃油最少的數(shù)學(xué)模型，并使用模擬退火算法分別求解。以上智能算法大多基于單目標(biāo)進(jìn)行航線優(yōu)化，不能滿足當(dāng)前的需求。針對該問題,LI等[13]以航行時(shí)間和航行風(fēng)險(xiǎn)為對象建立模型，并采用非支配排序遺傳算法-II[14](Non-Dominated Sorting Genetic Algorithm II，NSGA-II)求解，但該方法僅對轉(zhuǎn)向點(diǎn)的位置進(jìn)行優(yōu)化設(shè)計(jì)，并沒有對每一航段的航速進(jìn)行分配。

本文基于現(xiàn)有氣象航線優(yōu)化方法存在的問題，提出一種多變量、多目標(biāo)氣象航線優(yōu)化方法。該方法以船舶轉(zhuǎn)向點(diǎn)位置和每個(gè)航段的航速為優(yōu)化對象，以船舶特性和動態(tài)規(guī)避惡劣海況為約束條件，以航行時(shí)間和航行油耗為優(yōu)化目標(biāo)，建立多目標(biāo)航線優(yōu)化模型，并采用多目標(biāo)遺傳進(jìn)化算法求解得到最優(yōu)航線。

1 多變量多目標(biāo)航行優(yōu)化建模

1.1 模型變量定義

轉(zhuǎn)向點(diǎn)位置(包括出發(fā)港與目的港)和每個(gè)航段的航速組成船舶的一條完整的航線，其中部分轉(zhuǎn)向點(diǎn)要求航線必須經(jīng)過(如港口以及大洋航路點(diǎn))，這些轉(zhuǎn)向點(diǎn)的地理位置信息是在航線規(guī)劃初期就確定的，在算法迭代中不予調(diào)整，優(yōu)化前的航線示意見圖1。初始航線中包含有m個(gè)固定轉(zhuǎn)向點(diǎn)，P=[P1,P2,…,Pm]，優(yōu)化方法示意見圖2。將固定轉(zhuǎn)向點(diǎn)以大圓航線相連，每段大圓航段按等距離Δs進(jìn)一步細(xì)分，在大圓航線上可得到n個(gè)位置已知的等分點(diǎn)，作為產(chǎn)生n個(gè)位置待優(yōu)化轉(zhuǎn)向點(diǎn)的基準(zhǔn)點(diǎn)B=[B1,B2,…，Bn]，規(guī)定n個(gè)待優(yōu)化的轉(zhuǎn)向點(diǎn)X=[X1,X2,…,Xn]的位置調(diào)整只能限制在以基準(zhǔn)點(diǎn)為垂足，垂直于當(dāng)前大圓航段的一定距離h內(nèi)，從而使每個(gè)待優(yōu)化轉(zhuǎn)向點(diǎn)的位置可由基準(zhǔn)點(diǎn)位置計(jì)算得出，其中，Pi、Bi和Xi分別為第i個(gè)固定轉(zhuǎn)向點(diǎn)、第i個(gè)基準(zhǔn)點(diǎn)和第i個(gè)待優(yōu)化轉(zhuǎn)向點(diǎn)的位置向量。因此，船舶航線優(yōu)化問題的變量為n個(gè)待優(yōu)化轉(zhuǎn)向點(diǎn)的位置X=[X1,X2,…,Xn]和m+n-1段航段的對水航速(vW=[vW1,vW2,…,vWm+n-1])共2n+m-1個(gè)決策變量，在得到這些變量值之后，連接待優(yōu)化轉(zhuǎn)向點(diǎn)和固定轉(zhuǎn)向點(diǎn)即可得到一條優(yōu)化航線。

圖1 優(yōu)化前航線示意

圖2 船舶航線優(yōu)化法示意

1.2 目標(biāo)函數(shù)

本文建立以船舶航行的總油耗和航行總時(shí)間為優(yōu)化目標(biāo)的多目標(biāo)函數(shù)：

(1)

(2)

式(1)和式(2)中:T為航行的總時(shí)間;G為航行總油耗;di為航線第i段的距離，為相鄰兩轉(zhuǎn)向點(diǎn)位置的函數(shù);vGi為第i段的對地航速;vWi為第i段的對水航速;g(vWi)為主機(jī)每日油耗，t/d;f(Hi，Wave)為浪高懲罰函數(shù)；N=m+n-1為航線的航段總數(shù)。

每個(gè)航段的對地航速vGi為對水航速vWi的函數(shù)式為

vGi=vWi-Δvi

(3)

式(3)中:vWi為第i段的對水航速;Δvi為第i段的航速損失。

船舶在海上航行時(shí)，其航速會較靜水條件時(shí)減小，這種航速下降的現(xiàn)象稱為船舶失速。船舶失速分為兩種類型:

1) 由于風(fēng)和波浪的擾動，在主機(jī)功率不變的情況下航速較靜水條件時(shí)減小稱為自然失速。

2) 船舶在大風(fēng)浪中航行時(shí)，為減輕波沖擊和劇烈搖蕩引起的拍底、甲板上浪等危險(xiǎn)現(xiàn)象而采取的有計(jì)劃的降低航速稱為有意減速[1]。計(jì)算船舶的速度損失[15]為

(4)

式(4)中:Δvi為第i段的速度損失;vWi為第i段的對水航速;Cβ為方向衰減系數(shù)，與船舶的遭遇角相關(guān)；CU為速度衰減系數(shù)，取決于船舶的方型系數(shù)和裝載情況及弗勞德數(shù)Fr；CForm為船型系數(shù)。Cβ、CU和CForm的計(jì)算見文獻(xiàn)[16]。

主機(jī)每日油耗的計(jì)算很多都采用經(jīng)驗(yàn)公式計(jì)算，即

(5)

式(5)中:g為主機(jī)每日油耗;vWi為第i段的對水航速，kn;a、b、c和d為擬合系數(shù)。

1.3 懲罰函數(shù)

本文在建立的油耗和航行時(shí)間模型引入一個(gè)懲罰函數(shù)f(Hi，Wave)，其表達(dá)式為

(6)

式(6)中:Hi，Wave為航線第i段的平均浪高;Ht為航行中允許的最大浪高;K為值較大的懲罰系數(shù)。模型引入懲罰函數(shù)之后，在算法迭代的過程中，如果在隨機(jī)產(chǎn)生的一條航線中的任一航段中，船舶在高于最大允許浪高的環(huán)境下航行，會得到一個(gè)較大的懲罰值，使該條航線的航行時(shí)間T和油耗G急劇增加，以致在算法的后續(xù)迭代中，該條航線最終被淘汰。相反，當(dāng)航線中每一個(gè)航段的浪高都在允許的浪高下，航線的T和G的計(jì)算不會受到影響。因此，懲罰函數(shù)使得在最終規(guī)劃出的航線的每個(gè)航段中，船舶始終在小于最大允許的浪高條件下航行。

1.4 模型約束條件

在實(shí)際的航行過程中，需要為模型添加以下幾個(gè)約束條件：

1) 船舶的航速不能超過船舶設(shè)計(jì)的航速范圍，即

vmin≤vWi≤vmax

(7)

2) 待優(yōu)化轉(zhuǎn)向點(diǎn)的位置必須限制于垂直于當(dāng)前大圓航段的一定距離h內(nèi)，即

(8)

式(8)中:Δdi為第i個(gè)優(yōu)化點(diǎn)與基準(zhǔn)點(diǎn)的距離。

2 多變量多目標(biāo)優(yōu)化問題求解

本文基于強(qiáng)度帕累托算法2(Strength Pareto Evolutionary Algorithm 2，SPEA2)求解模型，該算法是在多目標(biāo)算法SPEA的基礎(chǔ)上改進(jìn)而來的,有關(guān)SPEA2算法的具體介紹見文獻(xiàn)[17]。

2.1 初始種群的產(chǎn)生

本文采用實(shí)數(shù)編碼，種群中每個(gè)個(gè)體代表出發(fā)港到目的港的1條航線，初始種群的產(chǎn)生包括產(chǎn)生每條航線的待優(yōu)化轉(zhuǎn)向點(diǎn)經(jīng)緯度位置(X=[X1,X2,…,Xn]和航線上每個(gè)航段的對水航速vW=[vW1,vW2,…,vWN]。

航線待優(yōu)化轉(zhuǎn)向點(diǎn)的產(chǎn)生和計(jì)算見圖3、式(9)和式(10)。

圖3 航線待優(yōu)化轉(zhuǎn)向點(diǎn)產(chǎn)生示意

(9)

Δdi=(rand(1)-0.5)×h

(10)

式(9)和式(10)中：rand(1)為產(chǎn)生一個(gè)(0，1)的隨機(jī)數(shù)；h為待優(yōu)化轉(zhuǎn)向點(diǎn)位置調(diào)整的最大范圍。由式(9)和式(10)可知:要獲得航線中隨機(jī)生成的待優(yōu)化轉(zhuǎn)向點(diǎn)的位置，需要輸入基準(zhǔn)點(diǎn)的位置(B=[B1,B2,…,Bn])、待優(yōu)化轉(zhuǎn)向點(diǎn)與基準(zhǔn)點(diǎn)的距離Δdi(正負(fù)號代表轉(zhuǎn)向點(diǎn)位于大圓航段左側(cè)還是右側(cè))和船舶在基準(zhǔn)點(diǎn)的航向θi等3個(gè)量。

航線上每個(gè)航段的對水航速vWi的計(jì)算式為

vWi=rand(1)×[vmax-vmin]+vmin

(11)

式(11)中:vWi為第i段的對水航速；vmin和vmax為船舶允許的最小航速和最大航速。

2.2 基于浪高加權(quán)懲罰的適應(yīng)度評估

種群中個(gè)體i的適應(yīng)度計(jì)算式為

F(i)=R(i)+D(i)

(12)

(13)

本文在計(jì)算T和G的過程中引入懲罰函數(shù)，當(dāng)一條航線中任意一航段所在區(qū)域浪高高于最大允許值Ht時(shí)，通過懲罰函數(shù)給予航線的T和G一個(gè)較大的懲罰值，使得在確定支配關(guān)系時(shí)，具有較大T和G的個(gè)體(即航線)受到更多其他個(gè)體的支配。因此，該個(gè)體原始適應(yīng)度值R增大，由式(12)可知，適應(yīng)度值F也隨之增大。在SPEA2環(huán)境選擇中，對于適應(yīng)度較大的個(gè)體，算法分兩種情況處理：

1) 該個(gè)體無法進(jìn)入檔案集。

2) 在算法迭代前期該個(gè)體進(jìn)入檔案集，但隨著算法的迭代，該個(gè)體逐漸被新產(chǎn)生的非支配個(gè)體取代。

檔案集中每個(gè)個(gè)體代表的航線均未遭遇惡劣海況，且未受其他航線個(gè)體支配(原始適應(yīng)度值為0)，具體算法流程見圖4。

圖4 多變量多目標(biāo)航線優(yōu)化流程圖

3 試驗(yàn)分析

3.1 試驗(yàn)定義

為驗(yàn)證本文提出的優(yōu)化方法的有效性，基于氣象導(dǎo)航軟件，將其應(yīng)用到集裝箱船舶航線規(guī)劃中，初始航線為A與B兩點(diǎn)之間的大圓航線，試驗(yàn)相關(guān)的參數(shù)見表1。

表1 試驗(yàn)相關(guān)參數(shù)設(shè)置

本次主要進(jìn)行兩個(gè)試驗(yàn)：試驗(yàn)1為驗(yàn)證根據(jù)本文提出的方法得到的航線在規(guī)避惡劣海況方面的效果，起點(diǎn)與終點(diǎn)之間的大圓航線作為對比對象，相關(guān)數(shù)據(jù)也在試驗(yàn)結(jié)果中列出；試驗(yàn)2為驗(yàn)證該方法在實(shí)現(xiàn)各種用戶偏好下的航線優(yōu)化效果，分別對采用本文提出的方法得到的最短航時(shí)航線、最低G航線和兩點(diǎn)之間的大圓航線的進(jìn)行對比分析。在兩個(gè)試驗(yàn)中，設(shè)大圓航線的對水航速恒為15 kn。

3.2 試驗(yàn)1

A與B兩點(diǎn)之間的大圓航線和在11月11日00:00的浪高分布見圖5。由圖5可知:船舶在11月11日00:00時(shí)刻已遭遇6 m以上的浪高，采用該方法優(yōu)化出的航線與大圓航線對比見圖6。在此次試驗(yàn)中，為更全面地了解動態(tài)變化的氣象信息，氣象軟件在每天的00:00、06:00、12:00和18:00設(shè)置評估點(diǎn)，軟件會自動獲取評估點(diǎn)所在位置的浪高、風(fēng)速等氣象信息，兩條航線每天06:00和18：00評估點(diǎn)位置及相應(yīng)的浪高分別見7和圖8，兩條航線的整個(gè)航行過程中的浪高分布見圖9。

圖5 2018-11-11T00:00浪高分布圖

圖6 大圓航線與優(yōu)化航線

圖7 大圓航線評估點(diǎn)浪高

圖8 優(yōu)化航線評估點(diǎn)浪高

圖9 浪高分布

優(yōu)化航線經(jīng)歷的氣象條件整體上比大圓航線好如見圖9所示，且大圓航線經(jīng)過高浪區(qū)域如見圖7所示，僅統(tǒng)計(jì)每天06:00和18:00時(shí)刻的浪高信息，大圓航線在11月11日的06:00和18:00及11月12日的06：00和18:00分別遭遇浪高為6.7 m、6.9 m、7.6 m和6.6 m的海浪，在該海況條件下航行，船舶的安全性受到嚴(yán)重威脅，但通過該方法優(yōu)化得到的航線并未遭遇高于6 m的海浪(見圖8)。圖8中:航線最高浪高僅為4.8 m，因此優(yōu)化航線通過調(diào)整轉(zhuǎn)向點(diǎn)位置和每航段的對水航速，有效避開航行過程中浪高高于6 m的惡劣海況區(qū)域。

3.3 試驗(yàn)2

本文提出的優(yōu)化方法可根據(jù)用戶的偏好優(yōu)化，SPEA2算法輸出的是一個(gè)帕累托解集，解集中均為非劣解，如果用戶需要的是T最短的航線，可接受相對較高的G，只需要按航行時(shí)間升序?qū)ε晾弁薪饧械暮骄€進(jìn)行排序，第1條航線即為最短航時(shí)航線。同樣，如果用戶需要航行G最低，只需要按航線G升序排序，第1條航線即為最低G航線。根據(jù)本文提出的方法得到的最低G航線、最短T航線和兩點(diǎn)之間的大圓航線見圖10,3條航線的相關(guān)數(shù)據(jù)對比見表2。

圖10 根據(jù)用戶偏好的優(yōu)化航線對比

由表2可知:最低G航線和最短T航線的距離相比大圓航線分別增長1.3%和0.7%，差距不是特別大，說明該方法更傾向于調(diào)節(jié)每個(gè)航段的航速來優(yōu)化航線，相比大圓航線，最低G航線的G下降了27.3%，T卻延長了11%，而最短T航線在t下縮短12.8%的同時(shí)，G增加了27.3%，最低G航線、最短T航線和大圓航線的航段油耗見圖11a(試驗(yàn)中的大圓航線以基準(zhǔn)點(diǎn)劃分每個(gè)航段)，最低油耗航線、最短航時(shí)航線和大圓航線的航段對水航速見圖11b。由圖11可知:較高的航速會導(dǎo)致油耗增加，最低油耗航線的船舶航速整體較低，導(dǎo)致t增加；最短航時(shí)航線為縮短t，整體的航速較高，導(dǎo)致航線總G增加，這與實(shí)際情況相符合。

表2 航線數(shù)據(jù)對比表

a) 航段油耗

b) 航段對水航速

4 結(jié)束語

為滿足航運(yùn)業(yè)對氣象航線優(yōu)化提出的航速航路同時(shí)優(yōu)化、綜合考慮多個(gè)目標(biāo)的要求，本文以G和T為優(yōu)化目標(biāo)，以航線轉(zhuǎn)向點(diǎn)位置和航段航速為優(yōu)化對象，以船舶特性(船舶最大最小航速)和規(guī)避惡劣氣象條件為約束，建立多變量、多目標(biāo)優(yōu)化模型，并進(jìn)行應(yīng)用。試驗(yàn)1證明本文提出的優(yōu)化方法能通過調(diào)節(jié)轉(zhuǎn)向點(diǎn)位置和航段對水航速有效避開惡劣海況區(qū)域;試驗(yàn)2證明該方法可根據(jù)用戶的偏好，選擇最低油耗、最短航時(shí)的優(yōu)化航線。

本文在氣象條件中僅考慮浪高，在后續(xù)工作中，還會考慮洋流、風(fēng)速和涌浪等更加豐富的氣象影響因素，并在規(guī)避惡劣區(qū)域的方法上施加安全距離，以確保與危險(xiǎn)分離，保證船舶航行的安全性，同時(shí)修改模型目標(biāo)函數(shù)，得到船舶航行其他指標(biāo)的優(yōu)化航線。