基于改進蟻群算法的船舶冰區(qū)航行路徑規(guī)劃

童幫裕, 胡堅堃

(上海海事大學 物流科學與工程研究院， 上海 201306)

隨著北極冰緣線面積逐年下降，部分海域已處于可航狀態(tài)，遠洋船隊在高緯冰區(qū)海域航行已成為可能，尤其是北極航道的開辟和“冰上絲綢之路”戰(zhàn)略的推動，利用冰區(qū)航道開展商業(yè)活動越來越頻繁。[1]但由于冰情復雜，船舶在冰區(qū)航行易受到海冰侵襲，導致碰擦、擱淺、受困等情況的發(fā)生，船舶和船上人員的安全受到很大威脅。[2]以往，船舶冰區(qū)航行路徑的選擇大多憑經(jīng)驗進行選擇，隨著近年來冰區(qū)航行頻率增加，為確保航行安全，維護船隊利益最大化，對冰區(qū)航線進行科學的規(guī)劃顯得尤為重要。

目前，對船舶路徑規(guī)劃尤其是特殊航區(qū)路徑規(guī)劃方面的研究相對較少。CHANG等[3]基于航行環(huán)境建立柵格海圖，利用迷宮算法使規(guī)劃的路徑能夠有效地規(guī)避障礙物。RAFAL[4]在船舶航線規(guī)劃模型中加入避障容差和轉(zhuǎn)彎次數(shù)，并設(shè)計具有線性時間和空間復雜度特征的算法。甘茂成[5]構(gòu)建起點與終點到障礙物之間公共切線組成的切線圖網(wǎng)絡模型，并采用Dijkstra算法規(guī)劃最短航線。李源惠等[6]設(shè)計出一種能夠快速判斷網(wǎng)格可航性的動態(tài)網(wǎng)格航線自生成法，規(guī)劃的航線能夠有效地規(guī)避障礙物。這些研究雖然能夠規(guī)劃出較好的路徑，但主要集中在對障礙物規(guī)避和最短路徑的尋找上，沒能考慮到特殊航區(qū)路徑規(guī)劃中的更多要求。

多種算法的結(jié)合實現(xiàn)算法性能提升是算法研究的主要方向。LIU等[7]利用人工勢場法中的勢場力重新構(gòu)造啟發(fā)信息，提出勢場蟻群算法，算法雖然收斂速度良好，但缺乏全局搜索能力，易出現(xiàn)停滯。莊曉東等[8]把人工勢場的路徑規(guī)劃結(jié)構(gòu)作為先驗知識初始化蟻群算法的參數(shù)，有效提高沒有先驗知識的優(yōu)化效率，但該算法結(jié)構(gòu)復雜，運算耗費時間長。劉雄等[9]為提高規(guī)劃路徑的平滑度，運用人工勢場法對蟻群算法的全局路徑節(jié)點進行平滑處理，但其重復規(guī)劃能力較差，結(jié)構(gòu)不穩(wěn)定。受蟻群算法和人工勢場法的啟示，本文設(shè)計一種新的蟻群算法。仿真結(jié)果表明該算法能夠有效滿足船舶冰區(qū)航行路徑規(guī)劃的需求。

1 問題描述

冰區(qū)航行是指船舶在穿過冰區(qū)或受到海冰威脅的高緯航線上航行。北極航道的西北航線和東北航線、北大西洋航線以及南極航線都是著名的冰區(qū)航線。[10]不同于一般海區(qū)，海冰對船舶航行的影響較大，船舶在冰區(qū)航行需要頻繁改變航向，操縱、航行定位和確保安全航行等都相當困難。[11]目前，雖然高緯已出現(xiàn)可供船舶航行的航道，但依然分布有大量的浮冰和薄冰帶，嚴重影響航行安全。

船舶航行路徑規(guī)劃是指在特定條件下找到一條從初始點到目標點的最優(yōu)路徑。船舶在冰區(qū)航行的路徑規(guī)劃除要尋找一條安全的避險路徑外，同時還要處理多個優(yōu)化目標，冰區(qū)路徑規(guī)劃實際上就是一個針對航路點、障礙物的非線性規(guī)劃尋優(yōu)問題。

2 模型建立

2.1 航行環(huán)境建立

船舶在一個有限區(qū)域內(nèi)的航行可視為船舶在二維平面上的運動。針對需要規(guī)劃航線的船舶，以S-57電子海圖為標準，在其航行的冰區(qū)內(nèi)建立柵格模型。為保證船舶與冰山等障礙物的安全距離，避免航線與海冰障礙區(qū)的重疊，對海冰柵格內(nèi)的障礙物進行膨化處理，即柵格內(nèi)只要存在障礙物即為海冰障礙物柵格。

船舶以網(wǎng)格為最小運動單位，航向均是前往下一個網(wǎng)格的中心點，航速保持不變，航程計算以網(wǎng)格中心點為準。按照船舶航行的安全航行范圍和轉(zhuǎn)向所需空間，將區(qū)域劃分為若干λx×λy的矩形網(wǎng)格。船舶在網(wǎng)格間移動次數(shù)為fn，表示船舶在第n次運動后占據(jù)的網(wǎng)格點，只要船舶所在的網(wǎng)格發(fā)生一次變化，則n+1，同理，n-1和n+1次的變動分別為fn-1和fn+1，且不重復，所以船舶航線F由航路點f1、f2、…、fN組成。定義f1為冰區(qū)航段的起始點q0，fk為冰區(qū)航段的終結(jié)點qf。當船舶在繞行海冰時，優(yōu)先選擇與海冰流動方向錯開的區(qū)域，稱在這類區(qū)域里的航路點為流冰規(guī)避航路點secn，整個矩形網(wǎng)格區(qū)域應覆蓋航段兩側(cè)海冰區(qū)域。對網(wǎng)格進行編號，沿橫軸方向由上向下依次編號，網(wǎng)格數(shù)量為15個×15個，網(wǎng)格編號依次為1、2、…、225，航行環(huán)境示意見圖1。

圖1 航行環(huán)境示意

2.2 目標函數(shù)

航行路徑規(guī)劃要在保證航行安全的同時考慮到航線距離、操作復雜程度和流冰規(guī)避。因此，綜合考慮船舶航行條件和船舶性能等因素，從航線距離、航線平均偏離度、流冰規(guī)避航路點選擇3個方面建立多目標規(guī)劃模型。

2.2.1航線距離

(1)

式(1)中:D(L)為航線距離；設(shè)第n次的航行路徑所穿越的網(wǎng)格中心點為fn(n=1,2,…,N);d(fn,fn+1) 為點fn到點fn+1的直線距離。

2.2.2平均偏離距離

由于冰區(qū)水道曲折，為降低船舶操作難度和保證路徑平滑度，加入規(guī)劃路徑與起始點和目標點間的直線段平均偏離距離比的指標為

(2)

2.2.3流冰規(guī)避區(qū)域選擇

海冰會隨著海浪、海風而不斷地在海域內(nèi)漂移，海冰運動方向受風與流作用的影響：北半球海冰移動方向偏于風向右方30°～40°；南半球則是在左方。[11]船舶通過冰區(qū)需要考慮到流冰的影響，所以航線對流冰的規(guī)避也是需要考慮的重要因素[12],即

(3)

式(3)中:k為一個0～1的變量，當fn∈secn時，k=1，否則k=0。

3 基于改進蟻群算法的路徑規(guī)劃

蟻群算法是模擬螞蟻通過信息素交流尋找最短路徑的智能算法。雖然蟻群算法具有先天性的圖上作業(yè)優(yōu)勢，但也存在初期路徑選擇盲目、易陷入局部最優(yōu)等問題。人工勢場法的算法結(jié)構(gòu)簡單，路徑搜索初期和后期差異較小，易同其他算法結(jié)合。本文結(jié)合兩種算法的特性，利用人工勢場法求得的初始路徑和節(jié)點間距離因素改進啟發(fā)信息，設(shè)計一種改進的蟻群算法。

3.1 人工勢場法求解初始路徑

人工勢場法的基本思想是通過目標點引力場和障礙物斥力場共同作用來搜索出一條無碰撞的最優(yōu)路徑。其定義如下：

假設(shè)船舶當前所在位置X=(x,y)，目標點位置Xg=(xg,yg)，則引力勢場函數(shù)為

(4)

式(4)中：φ為大于零的引力場因子；X為船舶位置向量;Xg為目標點位置向量。

斥力勢場函數(shù)為

(5)

式(5)中：φ為大于零的斥力場因子；R為船舶到冰山的距離；Rmax為冰山的最大影響范圍。

船舶在引力和斥力的共同影響下，向目標點方向運動并最終到達目標點。

3.2 改進啟發(fā)信息的路徑選擇準則

傳統(tǒng)的蟻群算法中，在t時刻螞蟻k由節(jié)點i選擇下一個節(jié)點j是根據(jù)初始信息素τij(t)和啟發(fā)信息ηij(t)的大小進行判斷的，路徑選擇準則如下：

(6)

(7)

式(6)和式(7)中：α和β分別為信息素重要程度和啟發(fā)函數(shù)重要程度的因子，反映出信息素濃度和啟發(fā)信息對螞蟻下一步轉(zhuǎn)移所起的作用強度；djg為待選節(jié)點j到目標點g的直線距離；allowk={0,1,2,…,n-1}為螞蟻K待選節(jié)點。

針對傳統(tǒng)蟻群算法獲取第一條路徑時更容易選擇距目標點近的節(jié)點的情況，用人工勢場法獲得的初始路徑和節(jié)點距離因素改進啟發(fā)信息，建立新的路徑選擇準則。同時，引入信息遞減系數(shù)υ來降低啟發(fā)信息的影響。新的啟發(fā)函數(shù)為

(8)

式(8)中：dij為節(jié)點i到節(jié)點j的直線距離；Ljg為采用人工勢場法求得的節(jié)點j到節(jié)點g的距離；Nc為當前迭代次數(shù)；Nmax為最大迭代次數(shù)；υ為啟發(fā)信息遞減系數(shù)，且υ>1。

3.3 帶有路徑評價的信息素更新機制

在蟻群算法中，螞蟻在完成一次迭代后，會對路徑(i,j)上的信息量調(diào)整，調(diào)整如下：

τij(t+n)=(1-ρ)τij(t)+Δτ(t)

(9)

(10)

式(9)～式(10)中:τij(t+n)為t+n時刻路徑(i,j)上的信息量；ρ為信息素揮發(fā)系數(shù)；1-ρ為信息素殘留因子；τij(t)為本次循環(huán)中路徑(i,j)上的信息素增量。

(11)

選用ant-cycle system模型，Q為一個常數(shù)即信息素強度；ω為路徑評價函數(shù)，根據(jù)路徑評價結(jié)果對信息素進行更新。評價函數(shù)為

ω=ω1L+ω2T+ω3K

(12)

式(12)中:L為路徑長度；T為平均偏離距離；K為航行上流冰規(guī)避航路點選擇次數(shù)。ω1、ω2、ω3分別為路徑長度、平均偏離距離、流冰規(guī)避航路點選擇的權(quán)重。

3.4 算法步驟

改進的蟻群算法見圖2。

1) 建立航行環(huán)境的柵格模型，設(shè)置起始點、目標點、障礙區(qū)域和流冰規(guī)避航路點。

2) 設(shè)置螞蟻數(shù)量m、最大迭代次數(shù)Nmax、信息素重要程度a、啟發(fā)函數(shù)重要程度β、信息素濃度Q、啟發(fā)信息遞減系數(shù)υ、信息素揮發(fā)系數(shù)ρ、路徑長度權(quán)重ω1、平均偏離距離權(quán)重ω2、流冰規(guī)避航路點選擇權(quán)重ω3等相關(guān)參數(shù)。

3) 用人工勢場法求得初始路徑和節(jié)點距離信息Ljg，并根據(jù)改進的螞蟻路徑選擇準則選擇下一步路徑點。

4) 若螞蟻到達目標，則結(jié)束本輪循環(huán)，按照信息素更新機制更新信息素。

5) 判斷是否達到最大迭代次數(shù)，若是，則終止并輸出最優(yōu)路徑，否則轉(zhuǎn)到步驟3)。

圖2 算法流程

4 仿真計算

冰區(qū)航行需要對航行海域內(nèi)的冰情充分掌握。夏季，海冰不斷的裂解和漂移形成可通航水域。船舶的通行情況主要受冰量影響，即海冰密集度。通常海冰覆蓋在60%以下即為可通航。[13]選取冰量為30%和50%的海域，采用本文的改進蟻群算法試驗航行路徑規(guī)劃的效果，并與傳統(tǒng)蟻群算法進行對比。

選取的某冰區(qū)海域面積為9 km×9 km，考慮到航行安全和船舶轉(zhuǎn)彎占用面積等因素，將其劃分為300 m×300 m的網(wǎng)格，建立起30個×30個的環(huán)境柵格。采用MATLAB進行計算。設(shè)參數(shù)：m=45、Nmax=150、Q=15、α=1、β=15、ρ=0.95、υ=4、ω1=8、ω2=6、ω3=3，并設(shè)置海冰障礙物左側(cè)為流冰規(guī)避區(qū)域。分別在海冰覆蓋率為30%和50%的海域模型中進行20次試驗選取最優(yōu)路線。

1) 海冰覆蓋率為30%時，得到的最優(yōu)路徑見圖3，兩種算法的相關(guān)性能指標比較見表1。

a) 常規(guī)蟻群算法路徑

b) 改進的蟻群算法路徑

表1 海冰覆蓋率為30%情況下兩種算法性能指標比較

試驗證明:在海冰覆蓋率為30%時，兩種算法都能較快收斂并得到最優(yōu)路徑，雖然改進蟻群算法的路徑長度較長，但轉(zhuǎn)彎點較少、平均偏離距離較短，更多地經(jīng)過流冰規(guī)避區(qū)域，船舶航行操作相對簡單、安全。

2) 海冰覆蓋率為50%時，得到的最優(yōu)路徑見圖4，兩種算法的相關(guān)性能指標比較見表2。

a) 海冰常規(guī)蟻群算法路徑

b) 改進的蟻群算法路徑

表2 海冰覆蓋率為50%情況下兩種算法性能指標比較

試驗證明：在冰量較大的復雜環(huán)境中，傳統(tǒng)蟻群算法規(guī)劃的路徑并不理想。本文改進蟻群算法的尋優(yōu)能力強，在轉(zhuǎn)彎點個數(shù)、平均偏離距離和流冰規(guī)避上都有明顯的優(yōu)勢。由此可見，改進蟻群算法能夠更好地滿足冰區(qū)航線需要。

5 結(jié)束語

本文針對冰區(qū)船舶航行路徑規(guī)劃的特點，充分考慮到船舶路徑規(guī)劃的經(jīng)濟性、操作性、安全性。應用本文方法獲得的路徑要優(yōu)于傳統(tǒng)蟻群算法的路徑，且簡單可行。本文研究也存有不足之處，具體表現(xiàn)在：環(huán)境模型中沒能考慮到冰山的動態(tài)可變性，沒能考慮到狹窄環(huán)境中與其他船舶的避讓，以及缺乏對船舶航速等方面的考慮，這些也是未來對船舶冰區(qū)航行所需要研究的方向。