郭興華，趙倉(cāng)龍

（江蘇航運(yùn)職業(yè)技術(shù)學(xué)院 航海技術(shù)學(xué)院，江蘇 南通 226010）

0 引 言

在海上交通中，航線規(guī)劃直接影響到船舶的運(yùn)輸效率、運(yùn)營(yíng)成本以及海洋環(huán)境保護(hù)等多個(gè)方面[1-2]。特別是在海上交通高峰期間，由于船舶數(shù)量和運(yùn)輸需求的增加，如何合理地規(guī)劃航線以避免碰撞、減少交通擁堵以及降低環(huán)境污染等問(wèn)題變得尤為重要[3]。因此，相關(guān)學(xué)者對(duì)海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃進(jìn)行仿真分析，為實(shí)際航線規(guī)劃提供有效的決策支持。寧君等[4]提出改進(jìn)隨機(jī)搜索樹(shù)（Rapidly Exploring Random Tree，RRT）算法的路徑規(guī)劃方法，該方法利用神經(jīng)網(wǎng)絡(luò)改進(jìn)RRT，分析船舶動(dòng)力學(xué)特性，以疏導(dǎo)時(shí)間最少作為目標(biāo)函數(shù)，經(jīng)過(guò)模型訓(xùn)練得出最優(yōu)船舶疏導(dǎo)路徑。黃國(guó)良等[5]提出改進(jìn)蟻群算法的路徑規(guī)劃方法，通過(guò)勢(shì)場(chǎng)函數(shù)優(yōu)化蟻群算法的船舶疏導(dǎo)路徑尋優(yōu)能力，以疏導(dǎo)路徑最短作為目標(biāo)函數(shù)，經(jīng)計(jì)算得出最優(yōu)的船舶疏導(dǎo)路徑。上述2 種方法因在模型尋優(yōu)的過(guò)程中計(jì)算量比較復(fù)雜，耗時(shí)較長(zhǎng)，導(dǎo)致船舶疏導(dǎo)路徑規(guī)劃效果不佳。

針對(duì)上述方法的局限性，通過(guò)仿真模型來(lái)模擬高峰期間的海上交通情況，并利用改進(jìn)混合遺傳算法對(duì)船舶疏導(dǎo)路徑實(shí)施規(guī)劃和優(yōu)化，有效地為海上交通管理部門(mén)和運(yùn)營(yíng)機(jī)構(gòu)提供有益的參考和幫助。

1 海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃仿真

1.1 海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃問(wèn)題描述

海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃問(wèn)題是在海圖上搜索到最佳航路[6]，實(shí)現(xiàn)海上交通高峰航線船舶疏導(dǎo)，解決海上交通高峰航線擁堵的問(wèn)題。設(shè)置A、B分別代表船舶終點(diǎn)、起點(diǎn)，海上交通高峰航線中船舶設(shè)置為障礙物，從A到B需要避開(kāi)海上交通高峰航線中船舶的航線。將該問(wèn)題轉(zhuǎn)化為數(shù)學(xué)模型，構(gòu)建以航程、安全性、平滑性最小為目標(biāo)函數(shù)，該目標(biāo)函數(shù)表達(dá)式如下：

式中：Q為一條疏導(dǎo)路徑；length(Q)為疏導(dǎo)路徑Q的航程描述；safety(Q)為疏導(dǎo)路徑Q的安全性；smoothless(Q)為疏導(dǎo)路徑Q的平滑性。

疏導(dǎo)路徑Q上第i個(gè)疏導(dǎo)路徑點(diǎn)用ki描述，其坐標(biāo)是(xi,yi)，疏導(dǎo)路徑Q為：

式中：k0描述疏導(dǎo)路徑起點(diǎn)A；kn+1描述疏導(dǎo)路徑起點(diǎn)B。

疏導(dǎo)路徑Q的航程length(Q)求解公式如下：

式中：疏導(dǎo)路徑點(diǎn)ki和疏導(dǎo)路徑點(diǎn)ki+1直線距離用dis(ki,ki+1)描述。

疏導(dǎo)路徑Q的安全性safety(Q)計(jì)算公式為：

式中：Gj(j=1,2,...,m)描述第j個(gè)障礙物即海上交通高峰航線船舶；kiki+I描述航段；描述Gj與kiki+I最短距離。

式中，ε描述轉(zhuǎn)向角。

1.2 基于混合遺傳算法的海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃方法

分析海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃問(wèn)題，采用混合遺傳算法求解該模型最優(yōu)解。為準(zhǔn)確描述海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃過(guò)程中，需要采用柵格法仿真模擬出海上交通高峰航線船舶環(huán)境，利用仿真軟件實(shí)施仿真建模，假設(shè)路徑規(guī)劃海面為矩形，將海面換分成邊長(zhǎng)相等的正方形柵格構(gòu)建海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃柵格地圖。其中，包括可通行柵格與障礙柵格，柵格地圖行列分別為row、col，α代表一個(gè)柵格，關(guān)聯(lián)矩陣值表達(dá)式如下：

其中：當(dāng)Map(α)=D>0時(shí)，代表柵格上無(wú)障礙物，此時(shí)船舶能通行，常數(shù)用D描述；當(dāng)Map(α)=0時(shí)，代表柵格上有障礙物，此時(shí)船舶不能通行。在海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃柵格地圖中黑色柵格、白色柵格分別表示障礙物、船舶可移動(dòng)范圍。

在構(gòu)建仿真柵格圖后，利用混合改進(jìn)遺傳算法進(jìn)行搜索船舶疏導(dǎo)路徑?；旌细倪M(jìn)遺傳算法是將非線性規(guī)劃算法與改進(jìn)遺傳算法相結(jié)合，提高算法的尋優(yōu)效率，并對(duì)海上交通高峰航線船舶疏導(dǎo)路徑實(shí)施優(yōu)化。第一步利用改進(jìn)遺傳算法尋找海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃模型的全局最優(yōu)解，通過(guò)在遺傳算法中添加安全算子、平滑算子、最短路徑算子形成改進(jìn)遺傳算法，疏導(dǎo)路徑規(guī)劃模型的全局尋優(yōu)具體過(guò)程如下：

步驟1疏導(dǎo)路徑編碼和進(jìn)行種群的初始化操作

在已知海上交通高峰環(huán)境地圖上選取個(gè)N×N網(wǎng)格點(diǎn)，各疏導(dǎo)路徑均經(jīng)過(guò)網(wǎng)格中心位置，構(gòu)建疏導(dǎo)路徑的編碼向量并用(φ1,φ2,···,φn)描述，海上交通高峰航線船舶在i點(diǎn)轉(zhuǎn)向角用 φi描述。當(dāng)φi＜0時(shí)，船舶向左行駛；當(dāng)φi>0時(shí)，船舶向右行駛。在該算法中疏導(dǎo)路徑代表由遺傳因子組成的染色體，為了降低船舶間碰撞概率，設(shè)置遺傳因子變量值大于15°。

步驟2疏導(dǎo)路徑適應(yīng)度函數(shù)求解

為了對(duì)疏導(dǎo)路徑實(shí)施評(píng)價(jià)，需要構(gòu)建適應(yīng)度函數(shù)，其表達(dá)式如下：

式中： η描述懲罰因子； χ描述疏導(dǎo)路徑和計(jì)劃路徑偏差度的加權(quán)因子；Hc描述優(yōu)化后路徑結(jié)束位置離計(jì)劃路徑目的地距離； μ描述碰撞危險(xiǎn)度因子；Hl描述優(yōu)化疏導(dǎo)路徑上每個(gè)點(diǎn)和目標(biāo)路徑點(diǎn)之間的距離；Hs描述船舶海域半徑。

步驟3搜索疏導(dǎo)路徑

① 通過(guò)輪盤(pán)賭法實(shí)施遺傳操作選取生命力強(qiáng)的染色體即疏導(dǎo)路徑。

② 通過(guò)算數(shù)交叉操作得出新的基因組，即新的疏導(dǎo)路徑組合。

③ 利用變異算子得出均值和方差替換以前基因值，即變異后得出新疏導(dǎo)路徑。

④ 安全算子。海上交通高峰航線船舶疏導(dǎo)路徑需要規(guī)避障礙物，在柵格中選取離障礙物最優(yōu)柵格并將該柵格節(jié)點(diǎn)設(shè)置在船舶疏導(dǎo)路徑中。

⑤ 平滑算子。利用平滑算子求解船舶疏導(dǎo)路徑最大轉(zhuǎn)向角，保證船舶疏導(dǎo)過(guò)程的穩(wěn)定性。

⑥ 最短路徑算子。通過(guò)最短路徑算子尋找海上交通高峰航線船舶疏導(dǎo)路徑的最短航程。

通過(guò)第一步得出海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃模型的全局最優(yōu)解；第二步，利用非性規(guī)劃求解海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃模型的局部最優(yōu)解。

2 結(jié)果實(shí)驗(yàn)分析

為了驗(yàn)證本文方法的應(yīng)用效果，通過(guò)Matlab R2020a實(shí)施仿真實(shí)驗(yàn)。分別構(gòu)建復(fù)雜與簡(jiǎn)單的海上交通高峰航線船舶仿真場(chǎng)景。復(fù)雜場(chǎng)景中船舶數(shù)量為200 條，障礙物數(shù)量為100 個(gè)而簡(jiǎn)單場(chǎng)景中船舶數(shù)量為50 條，劃方法、文獻(xiàn)[5]改進(jìn)蟻群算法的規(guī)劃方法。2 種場(chǎng)景下，海上交通高峰航線船舶疏導(dǎo)路徑進(jìn)行規(guī)劃，測(cè)試結(jié)果見(jiàn)表1。分析可知，針對(duì)不同場(chǎng)景下，本文方法的疏導(dǎo)路徑拐點(diǎn)數(shù)量最少，在疏導(dǎo)過(guò)程中船舶碰撞次數(shù)為0，疏導(dǎo)路徑航程最短，平緩系數(shù)低于0.15，安全性系數(shù)高達(dá)0.98。綜合表1 參數(shù)測(cè)評(píng)結(jié)果，可知本文方法的應(yīng)用效果明顯優(yōu)于其他2 種方法的應(yīng)用效果，說(shuō)明本文方法魯棒性和尋優(yōu)能力最強(qiáng)。

表1 不同場(chǎng)景下3 種方法的規(guī)劃效果Tab. 1 Planning effects of three methods in different scenarios

選取其中一艘船作為測(cè)試對(duì)象，采用本文方法針對(duì)2 種場(chǎng)景下海上交通高峰航線船舶疏導(dǎo)路徑，見(jiàn)圖1。分析可知，本文研究方法2 種場(chǎng)景下海上交通高峰航線船舶疏導(dǎo)路徑具有較好的方向性，結(jié)合表1 數(shù)據(jù)可知所規(guī)劃最優(yōu)疏導(dǎo)路徑安全性、平滑性、航程最少，符合海上交通高峰航線船舶疏導(dǎo)路徑目標(biāo)函數(shù)。

圖1 海上交通高峰航線船舶疏導(dǎo)路徑Fig. 1 Ship diversion paths on maritime traffic peak routes

以復(fù)雜場(chǎng)景為例，本文方法的海上交通高峰航線船舶疏導(dǎo)路徑仿真圖見(jiàn)圖2。分析可知，復(fù)雜場(chǎng)景下，本文方法的疏導(dǎo)路徑效果較好，以實(shí)驗(yàn)船舶為例，本文方法在短時(shí)內(nèi)可規(guī)劃出最優(yōu)疏導(dǎo)路徑，合理規(guī)避障礙物，采用本文方法對(duì)其他海上交通高峰航線船舶實(shí)施疏導(dǎo)路徑規(guī)劃，可快速實(shí)現(xiàn)海上交通暢通。

圖2 復(fù)雜場(chǎng)景下本文方法的疏導(dǎo)路徑仿真圖Fig. 2 Simulation of the grooming path of our method in complex scenarios

3 結(jié) 語(yǔ)

由于海上交通高峰期間船舶數(shù)量和交通流量的增加，對(duì)船舶疏導(dǎo)路徑的規(guī)劃顯得尤為重要。通過(guò)海上交通高峰航線船舶疏導(dǎo)路徑規(guī)劃仿真分析。

將船舶疏導(dǎo)路徑規(guī)劃問(wèn)題轉(zhuǎn)化為圖論中的多目標(biāo)問(wèn)題，并利用混合遺傳算法得出最優(yōu)解。仿真實(shí)驗(yàn)表明，本文提出的船舶疏導(dǎo)路徑規(guī)劃算法，在不同場(chǎng)景下，通過(guò)調(diào)整算法參數(shù)和約束條件，可以獲得較好的規(guī)劃效果和魯棒性。