基于遺傳算法的渡輪橫越航道動態路徑規劃研究

劉成勇 萬 一 王 新 陳蜀喆

(武漢理工大學航運學院1) 武漢 430063) (湖北省內河航運技術重點實驗室2) 武漢 430063)(長江引航中心3) 江陰 214400)

0 引 言

船舶橫越是指船舶行駛方向與航道形成一定角度，從航道一側穿越至另一側的行為[1]．內河渡輪在橫越航道時，極易與直行船舶發生碰撞，從而造成人員傷亡、水域污染、船舶受損甚至沉沒等危險[2]．因此，如何確定渡輪與直行船舶的安全緩沖區、如何規劃橫越的安全軌跡，以及直行船舶數量與渡輪橫越通過能力之間的關系，這些都是亟須解決的實際問題．

根據《內河避碰規則》要求，橫江渡輪需穿越通航分道或分邊航路時，應在無礙且沿規定航路行駛的船舶航行安全的情況下就近進行．對于渡輪航行過程中的碰撞風險，呂木榮等[3]通過水流、穿越角度及安全距離的影響，計算工程船穿越船舶流的時間與安全距離之間的關系．張赫等[4]通過船舶的不同穿越角度，選擇有利的穿越時機達到合適的穿越間隙穿越水道，有效降低船舶的碰撞風險．高建杰[5]建立汽渡輪碰撞危險度閾值計算模型，實現渡輪碰撞危險的預警．路徑規劃算法研究可分為全局路徑規劃算法，例如，遺傳算法[6]、A*算法[7]，和局部路徑規劃算法，例如蟻群算法[8]．對于傳統路徑規劃算法改進也能得到較好的效果，例如將國際海上避碰規則引入到船舶路徑規劃中，能夠使規劃后的船舶路徑更符合實際航行要求[9]；將無人船局部路徑規劃和控制循跡方法結合，可使規劃后的無人船路徑更短[10]；A*算法中引入激光雷達系統，可使得船舶路徑跳出局部最小解．

渡輪橫越航道時選擇安全可靠的橫越路徑可以有效避免直行船舶帶來的干擾問題．因此，了解不同航道飽和度情況下渡輪橫越航道的通過率，對于提升航道資源規劃和管理能力，以及優化航道交通資源配置具有重要意義．

1 橫越渡輪與直行船舶安全間距

1.1 停船視距

為保證船舶通航安全，在船舶周圍設置一個其他船舶不能進入的安全區域，這個安全區域稱之為該船的船舶領域．船舶領域的計算可以采用停船視距法，船舶停船視距模型見圖1．

圖1 停船視距模型

s=s0+s1+s2

(1)

式中：s為最小停船距離；s0為兩船間的安全距離，一般取1/4船長，即0.25l船；s1為駕駛員的反應距離；s2為船舶制動距離．船舶駕駛員的反應距離s1為駕駛員從發現危險到作出制動措施決定的這段反應時間內船舶航行的距離，計算公式為

s1=k0×s

(2)

式中：k0為反應距離和船舶間距之比，一般取42%．

對于船舶制動距離s2的計算主要考慮船舶制動過程中的作用力，在船舶制動過程中主要有兩種作用力，即船舶制動力和水流力，見圖2．內河船舶在實際制動過程中風力作用對船舶影響很小，可予以忽略．

圖2 船舶制動受力分析

f1f2

f1=P/v

(3)

f2=kv2

(4)

船舶制動時受到的合力F和制動時的加速度a為

F=f1+f2=p/v+kv2

(5)

(6)

船舶制動距離s2計算為

(7)

式中：f1為船舶制動力；f2為水流力；P為船舶功率；v為靜水速度；k為水流力系數，取2.84×104．

根據式(1)可得最小停船視距：

(8)

1.2 渡輪橫越航道時的安全間距

圖3為渡輪從碼頭O1～O2的橫越航道示意圖，O1為孩溪碼頭；O2為江心洲碼頭.渡輪橫越航道時須與直行船舶保持適當安全間距，渡輪縱向與直行船舶的安全間距用渡輪停船視距SA表示，橫向安全間距為直行船舶船舶領域．圖4為直行船舶與渡輪縱向安全距離，實線框為直行船舶的船舶領域的邊界，其他船舶均不可進入；虛線框為渡輪與直行船舶的碰撞危險緩沖區，渡輪橫越時不可進入此區域．但是在實際航行過程中，船舶能夠采取避碰行動，包括改變航向或者速度，因此實際的危險區域要小于理論危險區域．

圖3 渡輪橫越航道示意圖

圖4 直行船舶與渡輪縱向安全距離

2 基于遺傳算法的路徑規劃模型

2.1 初始化

1) 航道格柵化 本文通過格柵法建立渡輪通航環境模型，使可航區域與障礙區域都呈現在一張格柵圖上，易于使算法實現對路徑的搜索任務．

用0、1、2對航道與在航船舶進行動態格柵化處理．圖5為地圖格柵化示意圖．

圖5 地圖格柵化示意圖

假設直行船舶保持航向和初始速度不變，渡輪只改變航行方向，渡輪離泊為t0時刻，此時第k個直行船舶起始坐標為(Xk(t0),Yk(t0))，起始速度vk，渡輪軌跡每增加一個格柵，時間t和格柵地圖更新一次，ti時刻直行船舶位置為Ok(Xk(ti),Yk(ti))，則Xk(ti)=Xk(t0)+vkti，Yk(ti)=yk(t0)．

2) 種群初始化 遺傳算法求解最優路徑過程中，既要保證路徑的可行性，還要保證路徑的連續性．

ti、ti+1時刻航道內船舶分布見圖6，以ti+1時刻新格柵地圖為基礎，選取ti時刻渡輪位置周圍8個方向作為新格柵，并判斷此格柵是否為障礙格柵，是否已經在原路徑中，若是則刪除該格柵，若不是則將該格柵新增到路徑中．判斷兩個距離接近的格柵是否連續如式(9).

圖6 不同時刻航道船舶格柵地圖

δ=max{abs(xi+1-xi),abs(yi+1-yi)}

(9)

式中：xi、yi、xi+1、yi+1分別為兩個距離接近的格柵坐標；max為取最大值操作；abs為取絕對值操作．如果δ=1，則表明兩個距離接近的格柵pi和pi+1為連續路徑，否則表明為間斷路徑．

2.2 適應度函數

使用渡輪航行中的最短路徑作為評價指標，適應度函數用路徑長度的導數表示．即

(10)

式中：n為個體路徑中所含的格柵數目；L為個體路徑的長度大?。?/p>

2.3 遺傳操作

1) 遺傳算子 為順利完成種群初始化過程和迭代進化過程，初始種群中的所有個體都需要經歷選擇、交叉和變異操作，規劃出一條安全合理的航行路徑．

2) 選擇操作 將適應度值從小到大排序，按照優勝劣汰的原則保留適應度值高的個體進入到下一代．例如定義種群中前40%為強者，剩下60%為弱者，弱者中有0.3的比例存活，則這強者和弱者中存活的個體構成一個新的種群，進行下一步的交叉操作．

3) 交叉操作 交叉的方法有很多種，本文采用單點交叉．選擇相鄰兩個個體，兩個體間中路徑相同的點，在相同點中隨機選擇一個將該點之后的路徑進行交叉操作，得到兩條新路徑．

4) 變異操作 變異操作能夠增加種群多樣性，使算法更加具有普遍性．種群更新完畢后輸出結果．

3 實驗與結果分析

3.1 研究區域與數據選取

選取位于長江下游尹公洲航道的孩溪至江心洲汽渡作為研究目標，見圖7．

圖7 長江下游尹公洲孩溪至江心洲渡輪水域航道圖

根據AIS數據統計全天直行船舶中88%的船舶為3 000 t級以下的船舶，見表1．

表1 3 000 t級以下船舶船長及其比例

渡輪橫越航道時，當航道行駛過程沒有礙航船舶時渡輪一般以最短路徑航行，若有礙航船舶時，可從右側加速繞礙航船舶船艏或從左側繞礙航船舶船艉行駛．由圖8的尹公洲渡輪AIS數據軌跡圖也可以看出這一規律．

圖8 渡輪AIS軌跡圖

3.2 渡輪停船視距

船舶停船視距的計算主要通過根據船舶的船型數據和船舶航速，從而確定渡輪與直行船舶相互之間和的安全距離和危險緩沖區大?。藓降篮⑾两闹薅奢喆L61 m、寬13 m、吃水6.9 m，主機功率300 kW，船舶總噸位500．根據AIS數據統計渡輪在正常航行過程中平均航速為7.5 kn(3.8 m/s)，最高航速為10.4 kn(5.35 m/s)．基于式(8)，渡輪停船視距計算見表2．

3.3 地圖格柵化

1) 船舶領域格柵化處理 根據AIS數據分析，在內河中直行船舶船舶領域和船長的比值在2.5～3.5倍，船舶領域寬度和船長的比值在1.5～1.9．在統籌兼顧計算量和計算精度的基礎上，本次研究單位格柵為50 m×50 m．由于各區域大小只能為格柵大小的整數倍，船舶領域取平均值，長軸取為3倍船長，船舶領域短軸取1.6倍船長，渡輪與直行船舶中的危險緩沖區取1倍渡輪船長．其中渡輪占一個單位格柵，直行船舶格柵可取船長為40，60，80，100 m四種船型，以60 m船長船舶為例，船舶領域長軸為180 m，短軸為96 m，因此船舶領域格柵為4×2，渡輪危險緩沖區為4×1，見圖9．其中深灰色區域為直行船舶船舶領域格柵，淺灰色區域為渡輪與直行船舶間的危險緩沖區．

圖9 船長為60 m的直行船舶領域格柵圖

2) 航道格柵化處理 橫越渡輪平均航速為7.5 kn．假設航道中的直行船舶都沿直線勻速行駛，在渡輪航行開始到結束的時間內船舶，下行直行船舶平均可航行1.8 km，上行船舶船速小于下行船舶．航道地圖長度取3.6 km、寬度0.9 km，其中航道寬度為0.6 km，滿足模擬渡輪橫越航道的要求．渡輪橫越時，航道范圍內存在15條船舶，根據AIS數據可得到船舶的動態信息和靜態信息包括航向、船長、船寬、速度和位置等．根據航道環境和位置信息繪制渡輪橫越航道時的船舶分布圖，見圖10．圖中淺色區域為小型船舶上行推薦航道，深色區域為雙向通航的深水航道．根據表3統計的信息對t0時刻的航道地圖格柵初始化，見圖11．

圖10 渡輪橫越航道時船舶分布圖

表3 航道內船舶AIS數據信息統計表(部分)

圖11 t0時刻航道格柵圖

3.4 路徑規劃對比分析

為驗證遺傳算法應用于渡輪橫越航道路徑規劃的正確性和有效性, 在pycharm環境下對算法進行仿真實驗．交叉概率為0.6，變異概率為0.2，最大子代數為1 000．圖12為動態避障路徑規劃的仿真結果, 直行船舶是運動狀態，其中方塊深色部分表示船舶領域，淺灰色部分表示渡輪與直行船舶的移動安全區．通過遺傳算法對渡輪橫越路徑進行計算，得到橫越路徑后與渡輪實際橫越路徑進行比較．渡輪實際橫越軌跡和遺傳算法路徑軌跡圖，見圖13．

圖12 動態格柵路徑規劃結果

圖13 渡輪橫越航道規劃路徑與實際路徑對比圖

(11)

一般平均相對誤差在0%～15%內屬于合理范圍，計算得MRN=7.6%，在合理范圍內．因此遺傳算法用于渡輪橫越航道的路徑規劃是正確和有效的．

4 結 束 語

內河渡輪橫越航道時不能干擾航道內正常航行船舶，在航路選擇上既要考慮航行安全又要注重效率．本文以以長江下游典型渡區航段為例，通過停船視距理論計算橫越渡輪與直行船舶的安全間距及安全緩沖區，以船舶AIS交通流數據為基礎，分析航道通航環境和渡輪橫越規則，對船舶運動軌跡與航道圖進行動態格柵化處理，并基于遺傳算法對渡輪橫越航道的路徑集合進行選擇、交叉、變異操作．仿真實驗對比分析中，遺傳算法模型的交叉概率取0.6，變異概率取0.2，最大子代數為1 000，結合尹公洲孩溪至江心洲渡輪，對渡輪橫越航道進行路徑規劃，并與船舶AIS軌跡進行對比分析，平均相對誤差為7.6%，誤差在合理范圍內，實驗結果表明能夠為渡輪橫越航道時的航跡控制起到輔助支持作用，可優化內河渡輪航線．