多約束條件下氣象航線規(guī)劃的智能混合算法

文 婷

（北京海蘭信數(shù)據(jù)科技股份有限公司，北京100095）

0 前 言

海洋運輸是國際間商品交換中最重要的運輸方式之一，據(jù)統(tǒng)計在國際貿(mào)易中80%以上的貨物是通過海洋運輸來實現(xiàn)的。 設(shè)計一條安全、經(jīng)濟的氣象航線是海運的重要課題。 在船舶最佳氣象航線設(shè)計問題的研究中，主要考慮一個較為廣泛的地理域的中期和短期天氣影響，特別是波高和波向?qū)Υ昂叫兴俣鹊挠绊?，實現(xiàn)最短航行時間或最小燃油消耗的目標(biāo)。 該問題的求解由于各種約束條件而變得非常復(fù)雜，如可以事先獲得的由海岸線、淺水區(qū)和軍事禁行區(qū)等產(chǎn)生的靜態(tài)約束，以及可以通過天氣預(yù)報技術(shù)進行預(yù)測的動態(tài)約束條件如強風(fēng)、 巨浪等。

船舶氣象航線規(guī)劃問題，其求解辦法可以分為精確算法和啟發(fā)式算法兩種。 精確算法如等時方法［1-2］、Dijkstra 算法［3］、動態(tài)規(guī)劃算法等，能進行精確求解，但計算量會隨問題規(guī)模呈指數(shù)型增長；啟發(fā)式算法則是基于經(jīng)驗給出待解決優(yōu)化問題的一個可行解或近似最優(yōu)解，如模擬退火算法、蟻群算法［4］、粒子群算法［5］、神經(jīng)網(wǎng)絡(luò)等，遺傳算法［6-8］也是一種較為有效的解決復(fù)雜優(yōu)化問題的啟發(fā)式算法。 遺傳算法不受搜索空間的限制性假設(shè)約束，具有并行性，可采用多點同時進行搜索，在迭代計算過程中通過交換和變異產(chǎn)生新個體，可不斷擴大搜索范圍避免陷入局部最優(yōu)。 但其收斂速度和計算精度極易受到初始種群質(zhì)量的影響，好的初始種群能加快算法收斂速度。 目前，出現(xiàn)了許多基于遺傳算法的機器人路徑或飛行器航線規(guī)劃［9-11］算法應(yīng)用，但將其運用于船舶航線規(guī)劃的并不多見。筆者提出一種結(jié)合A*算法［12］和遺傳算法的智能混合算法，即使用A*算法搜索可行航線加入到初始種群中，以提升初始種群質(zhì)量，加快遺傳算法收斂速度，同時使用遺傳算法快速完成航線搜索方向上的連續(xù)查找，提高航線規(guī)劃質(zhì)量。

1 氣象航線規(guī)劃問題數(shù)學(xué)模型

1.1 問題的一般性描述

按照船舶航行點對點（出發(fā)點和目標(biāo)點）模式，定義船舶最佳航線問題的一般數(shù)學(xué)模型。 船舶最佳氣象航線求取問題可以表示為：在一系列約束條件下，求取使某一技術(shù)指標(biāo)達到最優(yōu)的航線。 船舶的位置X=（ψ，λ）（ψ 為緯度坐標(biāo)，λ 為經(jīng)度坐標(biāo)） 與時間t 可由式（1）表示：

X=f（X′，U′，W′，M′） （1）

式中：X′、U′、W′、M′與前一時刻t′相對應(yīng)，U′代表控制變量，W′代表氣象條件信息（風(fēng)速風(fēng)向、浪高浪向和涌等信息），M′代表確保船舶安全的約束條件，包括地理約束、控制約束和安全約束等。

由于氣象條件W′是位置X′和時間t′的函數(shù)，因此方程（1）也可寫成如下的形式：

X=f（X′，U′，t′，M′） （2）

因此，最佳氣象航線問題可以表示為尋找控制變量的約束優(yōu)化過程，而優(yōu)化目標(biāo)通常可為最短航程、最短航行時間、最小燃油消耗、固定時間到達或者這些目標(biāo)的組合，并滿足以下條件：X=（ψ0，λ0），t=t0，（ψ0，λ0） 為起點經(jīng)緯度坐標(biāo)；X=（ψn，λn），t=tn，（ψn，λn）為終點經(jīng)緯度坐標(biāo)；約束條件M′包括地理、氣象條件、運營和安全限制等。

1.2 航線數(shù)學(xué)描述

船舶航線由多個航路段構(gòu)成，每段航路之間以恒向線相連，每段航路都包含該段航路端點的經(jīng)緯度位置、航向角及航行速度信息，如圖1 所示：A 和B 分別表示出發(fā)點和目標(biāo)點；Ni（i=0，…，n），表示船舶航線的第 個航路拐點， 其中N0=A，Nn=B；ψi表示航路點Ni的緯度坐標(biāo)；λi表示航路點Ni的經(jīng)度坐標(biāo)；Vi表示第i 段航路的船舶靜水設(shè)定速度；φi表示第i 段航路的航向信息，以正北方向為0°，沿順時針方向遞增。

圖1 船舶航線模型

定義如下的可調(diào)變量來表示船舶航線：

1）航段數(shù)量：船舶航線上的航段數(shù)表示為n（n≥2），該參數(shù)可根據(jù)優(yōu)化算法的某些步驟進行調(diào)整。

2） 船點坐標(biāo)：表示每個航路拐點的經(jīng)緯度位置信息，船點坐標(biāo)可用向量X 來表示，各個航路點的位置坐標(biāo)見式（3）。

3） 航向變量：表示每段航路的航向角信息。 船舶在每段航路之間以恒向線進行航行，每段航路的恒向線航向可構(gòu)成航向變量，用向量φ 表示，見式（4）。

4）航速變量：表示每段航路對應(yīng)的計劃靜水航速，該速度與螺旋槳轉(zhuǎn)速相關(guān)。 在靜水航速設(shè)定值用向量υ 來表示。

1.3 航線約束條件

規(guī)劃出的船舶航線應(yīng)滿足以下約束條件：

1）航線不超出航行區(qū)域的外部邊界限制；

2） 航線不經(jīng)過淺灘水域的安全輪廓、陸地和島嶼等禁行區(qū)域；

3） 航線不經(jīng)過由惡劣天氣條件引起的氣象警報區(qū)；

4）航速在允許的最大和最小船速取值范圍內(nèi)；

5）滿足用戶設(shè)定的航行任務(wù)需求約束。

約束條件1）和2）是在航行期間不變的靜態(tài)約束區(qū)域，可通過一組由地理坐標(biāo)構(gòu)成的多邊形集合提供。約束條件3）是隨著時間不斷變化的由惡劣氣象條件引起的動態(tài)警報區(qū)，對于某一預(yù)計的時間點對應(yīng)著一組由地理坐標(biāo)構(gòu)成的多邊形集合。 約束條件1）、2）和3）給出了優(yōu)化時的地理空間約束，根據(jù)這3 個條件可以得到允許的可航行區(qū)域為所選取的航路規(guī)劃區(qū)域與上述約束區(qū)域的差集，將其記為Ωa（t）。 約束條件4）取決于船舶自身的結(jié)構(gòu)參數(shù)以及不同天氣條件下的船舶承載能力。 船舶在每段靜水的設(shè)定速度應(yīng)受限于某一區(qū)間［Vmin，Vmax］內(nèi)，其中Vmin為船舶最小靜水設(shè)定速度，Vmax為船舶最大靜水設(shè)定速度。約束條件5）是指規(guī)劃出的航線滿足用戶設(shè)定的優(yōu)化目標(biāo)，比如航線預(yù)計航行時間最短、航線航行的燃油消耗最低等。

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

目標(biāo)函數(shù)用于反映航線質(zhì)量的性能指標(biāo)，是航線規(guī)劃的最終目的。 基于不同的航行任務(wù)需求設(shè)計了不同的目標(biāo)函數(shù)用于優(yōu)化計算。 使用航線長度、航行時間和燃油消耗3 個不同的變量作為衡量航線的基本性能指標(biāo)。

總的航線的長度可以由每段航線長度累加所得，如式（6）所示：

L=∑n-10Li（6）

式中：L 為總的航線長度，n mile；n 為總 的航路 點數(shù)；Li為每段恒向線長度，n mile，可由恒向線公式計算。

總的航行時間可由每條航路段所花時間求和得到，如式（7）所示：

式中：Tvoyage為總的航行時間，h；ti為每段的航行時間，h；Vi，a為第 段航路的實際速度，kn。

船舶在每段航路的實際速度受該段設(shè)定的靜水速度和航行期間的風(fēng)浪條件所干擾，采用文獻［8］的經(jīng)驗公式計算在特定氣象信息和靜水設(shè)定速度條件下的船舶速度損失大小。

總?cè)加拖目捎擅織l航路段所花的油耗求和得到，如式（8）來表示：

式中：Q 為總的燃油消耗；Vi為第i 段航路對應(yīng)的設(shè)定靜水速度；ti為第i 段航路的航行時間；q（Vi）為在給定靜水速度Vi下對應(yīng)的燃油消耗率，可根據(jù)試驗數(shù)據(jù)利用插值的方法來獲取。

針對上面提到的基本航線性能指標(biāo)，設(shè)計了最短航行時間、最小油耗和固定時間到達3 個優(yōu)化問題，其目標(biāo)函數(shù)（minX?Ωa（t），V∈［Vmin，Vmax］）分別如式（9）～式（11）表示：

式 中：ETA 為 預(yù) 計 到 達 時 間 （Estimated Time of Arrival），h；ATA 為實際到達時間 （ Actual Time of Arrival），h；Talarm為警報時間， 即在氣象警報區(qū)中的時間，h。

2 氣象航線規(guī)劃的智能混合算法

提出的智能混合算法以標(biāo)準(zhǔn)遺傳算法為基礎(chǔ)，使用A* 算法優(yōu)化初始種群， 采用多種群技術(shù)和精英保留策略來增加種群多樣性和加快算法收斂速度。 提出混合變異算子以增強對最優(yōu)解的搜索，是精確算法與啟發(fā)式算法的結(jié)合。 智能混合算法流程如圖2 所示。

2.1 編碼策略

船舶航線可由航段數(shù)、航點坐標(biāo)、航向和每段對應(yīng)靜水速度確定。 航段數(shù)量根據(jù)實際情況確定，每段航向可由其端點的航路點坐標(biāo)應(yīng)用恒向線公式得到。 因此，每個用于表征航線的染色體中應(yīng)包含航線的航路點坐標(biāo)和每段對應(yīng)靜水速度信息。

算法采用下述航行區(qū)域初始化方法，得到易于表示航線的控制變量編碼策略：

圖2 智能混合算法流程圖

1） 根據(jù)給定的航線起點和終點坐標(biāo)得到一條基準(zhǔn)航線的航路點坐標(biāo)，該基準(zhǔn)航線可選為大圓航線、恒向線或者自定義航線，將該基準(zhǔn)航線的航路點坐標(biāo)用BaseRoute 來表示。

BaseRoute=｛（ψ0，λ0），…，（ψi，λi），…，（ψn，λn）｝ （12）

2） 在這些基準(zhǔn)航路點上，對其在某一方向上擴展某一長度，便可得到航行區(qū)域。 用向量dir 來表示擴展方向， 向量Lengt 表示向上和向下擴展的最大長度，起點和終點不擴展，指定擴展方向為航路點相鄰兩條航段所構(gòu)成夾角的平分線方向，如式（13）、式（14）所示。 顯然在該擴展方向上航線搜索范圍是連續(xù)的，這與其他一些算法中離散的網(wǎng)格系統(tǒng)相比擁有更高的搜索精度。

航行區(qū)域初始化示例如圖3 所示。 在建立航行區(qū)域后，一條航線的航路點坐標(biāo)可用其與對應(yīng)基準(zhǔn)航路點之間沿擴展方向的連線距離來表示，通過這個擴展長度結(jié)合基準(zhǔn)航路點坐標(biāo)和擴展方向，應(yīng)用恒向線公式可計算出對應(yīng)的經(jīng)緯度坐標(biāo)。 航線控制變量表達式如（15）所示，其中：向量U 的前n+1 個分量表示在對應(yīng)基準(zhǔn)航點上的擴展長度，代表航點位置信息， 其取值范圍為Loweri≤Ui≤Upperi，i=0，…，n；向量U 的后n 個分量代表每段航線上想要的靜水航行速度，其取值范圍為Vmin≤Ui≤Vmax，i=n+1，…，2n。

圖3 航行區(qū)域初始化示意圖

U=［U0… Ui… UnUn+1… U2n］ （15）

2.2 種群初始化

制定好染色體編碼策略后，種群的初始化就變得非常簡單。 為保證初始種群的多樣性和優(yōu)質(zhì)性，算法綜合使用下面兩種方法來生成初始種群：

一是采用隨機遍歷的方法。 在航行區(qū)域中隨機產(chǎn)生一組滿足各基因取值范圍的隨機數(shù)來生成一組染色體，各染色體中第1 個和第n 個基因的取值為0 表示這兩點分別固定為出發(fā)地和目的地。 每條染色體表示一條航線。

二是采用A*算法生成可行航線。在航行區(qū)域初始化基礎(chǔ)上，沿基準(zhǔn)航線左右兩側(cè)按一定間距生成一組平行于基準(zhǔn)航線的航線，結(jié)合擴展方向線構(gòu)成航行區(qū)域內(nèi)的柵格網(wǎng)絡(luò)。 針對不同的優(yōu)化目標(biāo)，使用對應(yīng)的目標(biāo)函數(shù)建立A*算法的代價函數(shù)f（pi）：

f（pi）=ω·g（pi）+（1-ω）·h（pi），ω∈［0，1］ （16）式中：pi為第i 個航路點；g（pi）為起點到pi的路徑的估算目標(biāo)函數(shù)值；h（pi）為pi到終點的路徑的估算目標(biāo)函數(shù)值；ω 為權(quán)重值。 ω 的取值將直接影響到算法的計算效率和計算精確性，因此需對ω 進行多次調(diào)試以得到一個較好的值。

上述兩部分得到的航線組合在一起即構(gòu)成了初始種群。 以A*算法生成的可行航線提升了種群質(zhì)量，加速后續(xù)遺傳計算的收斂速度。 以隨機遍歷方法生成的航線保證了種群的多樣性和復(fù)雜性，避免算法輕易陷入局部最優(yōu)。

2.3 適應(yīng)度值計算

適應(yīng)度函數(shù)的選取直接影響算法收斂速度的快慢和算法的精度。 氣象航線規(guī)劃需滿足的準(zhǔn)則：一是航線安全有效；二是滿足優(yōu)化目標(biāo)需求。 基于這兩個準(zhǔn)則，根據(jù)目標(biāo)函數(shù)值和航線的安全性來確認(rèn)適應(yīng)度函數(shù)。 具體計算方法如下：

1） 根據(jù)目標(biāo)函數(shù)值的大小對染色個體進行降序排序，然后根據(jù)排序后的位置對每個染色體分配適應(yīng)度值，排在前面的個體適應(yīng)度低。 以最短航行時間優(yōu)化目標(biāo)為例，當(dāng)計算出每條航線的目標(biāo)函數(shù)值后， 用向量J 來表示種群中每個個體的目標(biāo)函數(shù)值：

J=［J1… Ji… JM］ （17）

式中：Ji為第i 個染色體（航線）的目標(biāo)函數(shù)值；M 為種群的大小。

若排序后第i 個染色體的位置為posi，那么該染色體的適應(yīng)度函數(shù)fltl可用式（18）定義：

2）對每條染色體對應(yīng)的航線做安全性檢查，檢查航線是否會經(jīng)過地理不可行區(qū)域或航線是否會經(jīng)過氣象警戒區(qū)。 最終的適應(yīng)度函數(shù)根據(jù)檢查結(jié)果進行如下修正：

顯然，適應(yīng)度值的大小與排序后的目標(biāo)函數(shù)值位置線性相關(guān)，排在最前面的位置（目標(biāo)函數(shù)值最大）的染色體的適應(yīng)度最低，而排在最后面位置（目標(biāo)函數(shù)值最?。┑娜旧w的適應(yīng)度最高。 適應(yīng)度值越高的函數(shù)說明其對應(yīng)的航線越接近最優(yōu)。

2.4 新種群生成

算法通過一系列遺傳算子操作得到新的子種群，這些操作包括選擇、交叉、變異、重插入。

1）選擇。選擇算子是根據(jù)種群中個體適應(yīng)度的大小來確定需要被復(fù)制到子種群中的個體，個體的適應(yīng)度越大則被復(fù)制到子種群的概率越大。 算法提供3 種選擇算子：輪盤賭選擇、隨機遍歷選擇和錦標(biāo)賽選擇。

2）交叉。交叉操作是用來產(chǎn)生新個體的最主要操作，其結(jié)合兩條染色體以便從父代中接收良好的基因，產(chǎn)生新的個體，使種群在進化過程中逐漸得到更優(yōu)的解。 由于本算法使用的是實數(shù)編碼，因此采用算術(shù)交叉來進行交叉操作。 假設(shè)被選擇的兩個需要執(zhí)行交叉操作的個體分別為Xt1、Xt2， 則交叉運算后所產(chǎn)生的新個體為

式中：α 是一個Nvar維的橫向量參數(shù)，其每一個值是某一區(qū)間內(nèi)的均勻隨機數(shù)。本算法中α 的取值區(qū)間設(shè)為［-0.5，1.5］，同時為了保證交叉后得到的子代在邊界范圍內(nèi)， 對超出邊界的值將其修改為邊界值。

3）變異。算法中采用均勻變異和高斯變異相結(jié)合的混合變異方法，對種群中的一部分群體進行均勻變異，一部分群體進行高斯變異，增加種群的多樣性。

4）重插入。根據(jù)適應(yīng)度的大小將一定比例的子種群重新插入到父代種群中，同時移除父代中適應(yīng)度較低的個體，將得到的新種群作為下一父代種群。采用重插入操作可以保證種群中優(yōu)良的個體不被淘汰，同時能加快收斂速度。

2.5 算法結(jié)束判斷

算法結(jié)束判斷條件有兩個：一是達到最大迭代次數(shù)時終止計算；二是當(dāng)種群中最優(yōu)個體（即目標(biāo)函數(shù)最小的航線）連續(xù)若干代沒有發(fā)生變化時終止計算。 最優(yōu)個體即是根據(jù)指定優(yōu)化目標(biāo)計算出的最優(yōu)航線。

3 仿真實驗與分析

為驗證算法的正確性和有效性，仿真實驗選擇航線設(shè)計的起點為上海港附近（31.27°N，121.86°E），終點為巴拿馬港附近（8.84°N，79.48°W），出發(fā)時間為2016-07-01 00∶00∶00。選擇進行仿真的船舶為集裝箱船型S175，其標(biāo)準(zhǔn)排水量為23 740 t。仿真實驗選取對上海港到巴拿馬港的經(jīng)驗航線進行優(yōu)化，經(jīng)驗航線如圖4 所示。 優(yōu)化目標(biāo)則選為最短航行時間。

圖4 上海港到巴拿馬港經(jīng)驗航線

通過將較長的航路段進行區(qū)域劃分，將需要優(yōu)化的航路點分別擴展+5°和-5°緯度得到航行區(qū)域的邊界。 將每段航路的靜水航速設(shè)為15 kn，將航行過程中波高大于5 m 和風(fēng)速大于25 kn 的區(qū)域記為氣象警報區(qū)。 對出港口附近和進港口附近的航路點不進行優(yōu)化而直接采用原航路點，最終計算得到的航線優(yōu)化結(jié)果如圖5 所示。

圖5 優(yōu)化航線結(jié)果示意圖

航線分析計算結(jié)果：經(jīng)驗航線的總航程為8 721.8 n mile，總航行時間為601.97 h，警報時間為5.4 h，平均航速為14.49 kn；優(yōu)化航線的總航程為8 675.9 n mile，總航行時間為596.95 h，警報時間為0 h，平均航速為14.53 kn。 從結(jié)果可以看出優(yōu)化航線比經(jīng)驗航線縮短航程45.9 n mile，減少航時5.02 h，并且沒有經(jīng)過氣象警報區(qū)。

4 結(jié) 語

本文對氣象航線規(guī)劃問題中涉及的數(shù)學(xué)問題進行建模分析，設(shè)計了一種結(jié)合A*算法和遺傳算法的氣象航線規(guī)劃智能混合算法，該算法能在航線搜索區(qū)域中進行連續(xù)搜索，具有較高的精度和較快的計算速度。實驗結(jié)果表明該算法能有效避開危險區(qū)域，在保證安全的前提下為船舶規(guī)劃出一條經(jīng)濟的航線。船舶氣象導(dǎo)航具有重大的經(jīng)濟效益和實用價值，隨著科學(xué)技術(shù)的進步和海運業(yè)的發(fā)展，智能決策工具也將逐漸運用到船舶導(dǎo)航中，實現(xiàn)航線規(guī)劃自動化，提高海上航行的安全性和經(jīng)濟性。