基于改進蟻群算法的船舶冰區航行路徑規劃

童幫裕, 胡堅堃

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

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

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

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

1 問題描述

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

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

2 模型建立

2.1 航行環境建立

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

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

圖1 航行環境示意

2.2 目標函數

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

2.2.1航線距離

(1)

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

2.2.2平均偏離距離

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

(2)

2.2.3流冰規避區域選擇

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

(3)

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

3 基于改進蟻群算法的路徑規劃

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

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

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

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

(4)

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

斥力勢場函數為

(5)

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

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

3.2 改進啟發信息的路徑選擇準則

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

(6)

(7)

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

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

(8)

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

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

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

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

(9)

(10)

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

(11)

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

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

(12)

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

3.4 算法步驟

改進的蟻群算法見圖2。

1) 建立航行環境的柵格模型，設置起始點、目標點、障礙區域和流冰規避航路點。

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

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

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

5) 判斷是否達到最大迭代次數，若是，則終止并輸出最優路徑，否則轉到步驟3)。

圖2 算法流程

4 仿真計算

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

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

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

a) 常規蟻群算法路徑

b) 改進的蟻群算法路徑

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

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

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

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

b) 改進的蟻群算法路徑

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

試驗證明：在冰量較大的復雜環境中，傳統蟻群算法規劃的路徑并不理想。本文改進蟻群算法的尋優能力強，在轉彎點個數、平均偏離距離和流冰規避上都有明顯的優勢。由此可見，改進蟻群算法能夠更好地滿足冰區航線需要。

5 結束語

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