基于遺傳算法的渡輪橫越航道動(dòng)態(tài)路徑規(guī)劃研究

劉成勇 萬 一 王 新 陳蜀喆

(武漢理工大學(xué)航運(yùn)學(xué)院1) 武漢 430063) (湖北省內(nèi)河航運(yùn)技術(shù)重點(diǎn)實(shí)驗(yàn)室2) 武漢 430063)(長江引航中心3) 江陰 214400)

0 引 言

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

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

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

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

1.1 停船視距

為保證船舶通航安全，在船舶周圍設(shè)置一個(gè)其他船舶不能進(jìn)入的安全區(qū)域，這個(gè)安全區(qū)域稱之為該船的船舶領(lǐng)域．船舶領(lǐng)域的計(jì)算可以采用停船視距法，船舶停船視距模型見圖1．

圖1 停船視距模型

s=s0+s1+s2

(1)

式中：s為最小停船距離；s0為兩船間的安全距離，一般取1/4船長，即0.25l船；s1為駕駛員的反應(yīng)距離；s2為船舶制動(dòng)距離．船舶駕駛員的反應(yīng)距離s1為駕駛員從發(fā)現(xiàn)危險(xiǎn)到作出制動(dòng)措施決定的這段反應(yīng)時(shí)間內(nèi)船舶航行的距離，計(jì)算公式為

s1=k0×s

(2)

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

對于船舶制動(dòng)距離s2的計(jì)算主要考慮船舶制動(dòng)過程中的作用力，在船舶制動(dòng)過程中主要有兩種作用力，即船舶制動(dòng)力和水流力，見圖2．內(nèi)河船舶在實(shí)際制動(dòng)過程中風(fēng)力作用對船舶影響很小，可予以忽略．

圖2 船舶制動(dòng)受力分析

f1f2

f1=P/v

(3)

f2=kv2

(4)

船舶制動(dòng)時(shí)受到的合力F和制動(dòng)時(shí)的加速度a為

F=f1+f2=p/v+kv2

(5)

(6)

船舶制動(dòng)距離s2計(jì)算為

(7)

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

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

(8)

1.2 渡輪橫越航道時(shí)的安全間距

圖3為渡輪從碼頭O1～O2的橫越航道示意圖，O1為孩溪碼頭；O2為江心洲碼頭.渡輪橫越航道時(shí)須與直行船舶保持適當(dāng)安全間距，渡輪縱向與直行船舶的安全間距用渡輪停船視距SA表示，橫向安全間距為直行船舶船舶領(lǐng)域．圖4為直行船舶與渡輪縱向安全距離，實(shí)線框?yàn)橹毙写暗拇邦I(lǐng)域的邊界，其他船舶均不可進(jìn)入；虛線框?yàn)槎奢喤c直行船舶的碰撞危險(xiǎn)緩沖區(qū)，渡輪橫越時(shí)不可進(jìn)入此區(qū)域．但是在實(shí)際航行過程中，船舶能夠采取避碰行動(dòng)，包括改變航向或者速度，因此實(shí)際的危險(xiǎn)區(qū)域要小于理論危險(xiǎn)區(qū)域．

圖3 渡輪橫越航道示意圖

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

2 基于遺傳算法的路徑規(guī)劃模型

2.1 初始化

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

用0、1、2對航道與在航船舶進(jìn)行動(dòng)態(tài)格柵化處理．圖5為地圖格柵化示意圖．

圖5 地圖格柵化示意圖

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

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

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

圖6 不同時(shí)刻航道船舶格柵地圖

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

(9)

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

2.2 適應(yīng)度函數(shù)

使用渡輪航行中的最短路徑作為評價(jià)指標(biāo)，適應(yīng)度函數(shù)用路徑長度的導(dǎo)數(shù)表示．即

(10)

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

2.3 遺傳操作

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

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

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

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

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

3.1 研究區(qū)域與數(shù)據(jù)選取

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

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

根據(jù)AIS數(shù)據(jù)統(tǒng)計(jì)全天直行船舶中88%的船舶為3 000 t級(jí)以下的船舶，見表1．

表1 3 000 t級(jí)以下船舶船長及其比例

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

圖8 渡輪AIS軌跡圖

3.2 渡輪停船視距

船舶停船視距的計(jì)算主要通過根據(jù)船舶的船型數(shù)據(jù)和船舶航速，從而確定渡輪與直行船舶相互之間和的安全距離和危險(xiǎn)緩沖區(qū)大小．尹公洲航道孩溪至江心洲渡輪船長61 m、寬13 m、吃水6.9 m，主機(jī)功率300 kW，船舶總噸位500．根據(jù)AIS數(shù)據(jù)統(tǒng)計(jì)渡輪在正常航行過程中平均航速為7.5 kn(3.8 m/s)，最高航速為10.4 kn(5.35 m/s)．基于式(8)，渡輪停船視距計(jì)算見表2．

3.3 地圖格柵化

1) 船舶領(lǐng)域格柵化處理 根據(jù)AIS數(shù)據(jù)分析，在內(nèi)河中直行船舶船舶領(lǐng)域和船長的比值在2.5～3.5倍，船舶領(lǐng)域?qū)挾群痛L的比值在1.5～1.9．在統(tǒng)籌兼顧計(jì)算量和計(jì)算精度的基礎(chǔ)上，本次研究單位格柵為50 m×50 m．由于各區(qū)域大小只能為格柵大小的整數(shù)倍，船舶領(lǐng)域取平均值，長軸取為3倍船長，船舶領(lǐng)域短軸取1.6倍船長，渡輪與直行船舶中的危險(xiǎn)緩沖區(qū)取1倍渡輪船長．其中渡輪占一個(gè)單位格柵，直行船舶格柵可取船長為40，60，80，100 m四種船型，以60 m船長船舶為例，船舶領(lǐng)域長軸為180 m，短軸為96 m，因此船舶領(lǐng)域格柵為4×2，渡輪危險(xiǎn)緩沖區(qū)為4×1，見圖9．其中深灰色區(qū)域?yàn)橹毙写按邦I(lǐng)域格柵，淺灰色區(qū)域?yàn)槎奢喤c直行船舶間的危險(xiǎn)緩沖區(qū)．

圖9 船長為60 m的直行船舶領(lǐng)域格柵圖

2) 航道格柵化處理 橫越渡輪平均航速為7.5 kn．假設(shè)航道中的直行船舶都沿直線勻速行駛，在渡輪航行開始到結(jié)束的時(shí)間內(nèi)船舶，下行直行船舶平均可航行1.8 km，上行船舶船速小于下行船舶．航道地圖長度取3.6 km、寬度0.9 km，其中航道寬度為0.6 km，滿足模擬渡輪橫越航道的要求．渡輪橫越時(shí)，航道范圍內(nèi)存在15條船舶，根據(jù)AIS數(shù)據(jù)可得到船舶的動(dòng)態(tài)信息和靜態(tài)信息包括航向、船長、船寬、速度和位置等．根據(jù)航道環(huán)境和位置信息繪制渡輪橫越航道時(shí)的船舶分布圖，見圖10．圖中淺色區(qū)域?yàn)樾⌒痛吧闲型扑]航道，深色區(qū)域?yàn)殡p向通航的深水航道．根據(jù)表3統(tǒng)計(jì)的信息對t0時(shí)刻的航道地圖格柵初始化，見圖11．

圖10 渡輪橫越航道時(shí)船舶分布圖

表3 航道內(nèi)船舶AIS數(shù)據(jù)信息統(tǒng)計(jì)表(部分)

圖11 t0時(shí)刻航道格柵圖

3.4 路徑規(guī)劃對比分析

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

圖12 動(dòng)態(tài)格柵路徑規(guī)劃結(jié)果

圖13 渡輪橫越航道規(guī)劃路徑與實(shí)際路徑對比圖

(11)

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

4 結(jié) 束 語

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