基于改進蟻群算法的船舶多約束最優航線設計

陳立家+黃立文+崔梅

摘要：為提高船舶航線經濟性，基于電子海圖顯示與信息系統（electronic chart display and information system，ECDIS），分析影響航線設計的各種因素，建立航線設計網絡模型。將改進蟻群算法的基本原理應用于船舶航行路徑搜索中，提出一種多約束條件下航行綜合成本最低的最優航線生成算法。仿真試驗證明，該算法是可行的，且具有動態尋優的特點，將其應用于多約束條件下的最優航線設計是合理的。

關鍵詞： 電子海圖顯示與信息系統（ECDIS）； 多約束； 船舶航線設計； 蟻群算法

中圖分類號： U692.33 文獻標志碼： A

Abstract： In order to improve the economy of ship route， based on the electronic chart display and information system （ECDIS）， the various factors influencing route planning are analyzed， and a route planning network model is established. The basic principle of the improved ant colony algorithm is applied to ship path search. An optimal route generation algorithm under multiple constraints is proposed for the minimum integrated navigation cost. The simulation test shows that， the algorithm is feasible and of the characteristic of dynamic optimization， and it is reasonable to apply the algorithm to the optimal route planning under multiple constraints.

Key words： electronic chart display and information system （ECDIS）； multi-constraint； ship route planning； ant colony algorithm

0 引 言

隨著智能航海技術的發展，實時航路規劃已成為利用電子海圖顯示與信息系統（electronic chart display and information system，ECDIS）進行研究的最新方向之一。李源惠等[1]根據電子海圖數據庫特有的性質，結合礙航物的判別標準和船舶的航行狀態，提出了基于電子海圖的自動判別計劃航線可行性的方法。CHANG等[2]依靠柵格電子海圖平臺，對迷宮算法進行適當改進，提出了解決最短航線距離問題的方法。RAFAL[3]采用分析避碰和轉向條件的策略優化航線。葉清等[4]利用某個港口與多個港口之間的船舶交通網絡圖，提出了找到一條最佳航線的方法。王德春等[5]通過構建航運網絡圖，利用A*啟發式搜索算法，提出了找到船舶最佳航線的方法。此外，王科[6]依據Dijkstra算法的基本思想對軍事航線的最優化問題進行了研究。

蟻群算法具有很好的魯棒性，被廣泛地應用于求解船舶航行的最短路徑問題。聶皓冰等[7]引入空間數據索引結構來實現航行信息的快速檢索，提出了基于航行信息空間連通矩陣的改進蟻群算法。陳寶文[8]根據艦船路徑規劃的技術特點，提出了一種基于鄰域變異的改進微分進化算法。朱青[9]針對船舶航行環境的特點，采用MAKLINK法建立海洋環境模型，提出了基于蟻群算法的全局路線搜索模型。何立居等[10]基于蟻群算法進行了航線自動生成的研究，在電子海圖中通過案例證明了蟻群算法用于航線自動生成的可行性。然而，這些研究都主要集中在算法改良上，路徑選擇主要滿足路徑最短這一目標，即在一個約束條件下的最優路徑問題。

在水上交通中，在多約束條件下的最優航線設計問題是在給定的帶有多個約束的網絡拓撲結構中尋找一條或多條滿足限定條件的路徑的問題，其約束條件可以為水深、路徑長度、與障礙物距離等。本文以電子海圖為基礎，對多約束條件下船舶航行路徑最短問題進行研究。

1 航線設計問題描述

在多約束條件下船舶最優航線選擇是，某船舶在滿足給定的約束條件的情況下，在起始港口與目的港口之間找到一條成本最小或者達到特定的服務水平的航線。兩個港口之間有任意多條可供船舶航行的航線，它們經過不同的港口和錨地，同時存在多種約束和一些點、線、面的礙航物，這組成了一張航線網絡圖。在電子海圖中根據相關約束條件來確定礙航區，在起始港口與目的港口之間的可航區域內，按照一定間隔依次遍歷每一個水深點，若符合預先規定的約束條件要求，則將該航路點抽象為一個節點，同時將要經過的港口也當作節點抽象出來，節點之間的距離為廣義上的航行距離，這樣就抽象出一張帶權網絡圖[9，11]。

尋找從起始港口到目的港口的最短路徑問題[12-14]，可以轉化成在帶權網絡圖中對單源節點最短路徑問題的分析，故在航線網絡圖上尋找最短路徑問題就轉化為圖論中的最短路徑問題。節點、弧、權值三要素組成了帶權網絡圖。節點為航路點、港口、交叉點以及斷點；弧為兩節點間的有向弧段；權值為航段某個或者某些特性的量化值。因此，帶權航線網絡圖就轉化為一個帶權有向圖，并且權值的獲取是基于時間段的。假設網絡中有N個節點，船舶可通過第i個節點的時間段為[til，tir]，實際通過該節點的時刻為ti。這樣，節點就增加了時間約束：til≤ti≤tir（1≤i≤N）。設置約束函數Qi（ti）來體現這個時間約束對最優航線設計的影響：endprint

2 多元約束及其參數

按照航線影響因素的不同，有靜態權值和動態權值。靜態權值是用船舶航行距離衡量航線權重以達到最短距離的目標，動態權值是用經濟效益衡量航線權重以獲得航行時燃料消耗最少的目標。

航行費用E=E1+E2+E3，其中E1表示燃料消耗所產生的費用，E2表示航行時間價值所產生的費用（隱形的費用），E3表示航行過程中所繳納的費用。這很明顯地體現出一些經濟因素，比如將航行距離和航行時間都折算為費用。

航行質量指航線能滿足人們需求的程度。對影響航行質量的一切性能指標進行綜合評價，得到航線質量權值：M=σ1T+σ2D+σ3Q，σ1+σ2+σ3=1

（3）式中：T是船舶在航線上的平均行程時間；D是航行過程中所消耗的燃料；Q是航線的舒適度；σ1，σ2和σ3為權重因數，分別體現了T，D和Q在航線質量中所占的權重。

在多約束條件下的航線權值計算方法：根據水文氣象資料，得知在某時間段內船舶在可航區域各航段的海況信息、風浪信息和水深信息，以及船舶在風浪中的臨界速度。

V=1T+2W+3S， 1+2+3=1

（4）

式中：T是基于靜態因素的船舶在航線上的平均行程時間（=航程/基本航行速度）；W是關于風的信息值，包含風的大小和方向；S是關于浪的信息值；1，2和3分別表示T，W和S所占的權重。另外，當風浪超過一定級別時，船舶航速會發生變化，此時用確定好的臨界速度來計算T。

3 在多約束條件下最優航線設計算法

3.1 基本思想

本文提出一種在多約束條件下航行綜合成本最低的最優航線生成算法（an optimal route generation algorithm based on the minimum integrated navigation cost under multiple constraints，ORGA）。當兩港口之間有多條航線可供選擇時，可應用Dijkstra算法求得最短航線。根據各種環境因素對航線的影響，用改進的蟻群算法使生成的航線達到最優。改進的蟻群算法的基本思想為：（1）在每只螞蟻完成一遍搜索后，在信息素濃度更新之前，對所有螞蟻按照其所走過的路徑的長度由短到長進行排序；在信息素濃度更新時，對挑選出來的前h只螞蟻，適當增加其所走過的路徑的信息素量，對后面的m-h只螞蟻，適當減少其所走過的路徑的信息素量，這樣就拉開了優、劣螞蟻所走過的路徑之間的差距，從而提高找到最優路徑的速度。（2）為削弱上述策略引起的蟻群陷入早熟的局限，采用MMAX優化思想，將各路徑上的信息素濃度限制在[τmin，τmax]內，若某路徑上的信息素濃度超過這個范圍，則按就近原則將其設為τmin或τmax，這就避免了算法過早收斂并陷入局部最優解的問題，也避免了搜索過程中的停滯現象。（3）因為在ORGA中對路徑上的信息素濃度進行了人為控制，導致了各路徑上的信息素濃度兩級分化比較嚴重，所以將路徑上信息素的殘留系數設得較低。為有助于增加初始階段螞蟻的搜索能力，將各路徑上的信息素濃度初始值設為τmax。

3.2 算法實現

通過釋放人工螞蟻來創建基于螞蟻算法的網絡模型。

算法涉及的函數和變量如下：ηij=1/（dij（1+Rij（1+Wij）+Cij））

（5）式中：ηij為啟發函數；dij為相鄰兩節點間的距離；Rij為風浪狀況因子；Wij為天氣情況因子；Cij為海況因子。各因子都是非負的。對螞蟻k而言，該啟發函數表示它從節點i轉移到節點j的期望程度。各因子都是通過觀測得到的。

τij（t）為t時刻在邊（i，j）上的信息素濃度；tij為船舶從i行駛到j的時間，用權值cij表示；tij，l=til+tij，tij，r=tir+tij；α為期望啟發因子，表示軌跡的相對重要度；β為能見度的相對重要度；ψ為時間約束因子，表示時間約束的相對重要度；q為一個取值范圍為[0，1]的變量，它決定選擇下一個城市的概率；q0為一個給定的[0，1]間的常數，其值越小表示螞蟻隨機選擇下一個節點的概率越大；Ak（k=1，2，…，m）為螞蟻k已走過的節點集合，即為禁忌表；m為螞蟻的數量；Bk為允許螞蟻k下一步選擇的節點集合；Q為每只螞蟻所持有的信息素總量；Lk為節點i與j之間的路徑長度。

3.3 算法具體步驟

ORGA的具體步驟如下：

步驟1 將各控制參數初始化：時間t=0；循環次數Nc=0；每條航段（i，j）的初始化信息素濃度τij（0）=τmax；最大循環次數為Nc，max；全局最優解為Lg。

步驟2 將m只螞蟻置于起點，建立候選節點列表M。

步驟3 對螞蟻k（k=1，2，…，m），在候選節點列表中找出其未走過的節點（M-Ak），并在這些節點中根據式（6）（狀態轉移規則）選擇該螞蟻訪問的下一個節點，直到所有的節點都被訪問為止。

步驟4 判斷已完成搜索的螞蟻數量是否為m，是則執行步驟5，否（即還有螞蟻未完成搜索）則返回步驟3，直到所有螞蟻都完成搜索為止。

步驟5 計算每只螞蟻的搜索路徑長度Lk（k=1，2，…，m），并且對螞蟻按照其所走過的路徑長度由短到長的順序進行排序。對于排名前h的螞蟻，設置本次路徑Llocal為本次最優路徑，Llocal=hk=1Lk，同時保存最優路徑表。

步驟6 對所有路徑上的信息素濃度按式（8）進行全局更新，在本次循環中對排名前h的螞蟻所經過的路徑上的信息素濃度按該螞蟻所在的名次進行增加。信息素濃度更新的同時，按照式（7）來優化替換，以便螞蟻產生新的搜索路線。

步驟7 將本次最優路徑Llocal與全局最優解Lg比較，較小的值存入Lg，并更新全局最優路徑表。endprint

步驟8 若每只螞蟻的路徑都收斂于同一條路徑，則算法結束。判斷Nc與Nc，max是否相等，若相等，則流程結束；否則，清空禁忌表Ak，轉至步驟3。4 算法檢驗

4.1 復雜度分析

假設航線網絡結構中有N個節點，采用傳統的Dijkstra算法，需要的時間為N（N-1）=N2-N，該算法的時間復雜度為O（N2）。ORGA是針對傳統Dijkstra算法搜索時間過長和基本的蟻群算法存在早熟和停滯現象而提出來的，它適當地改進蟻群算法，對一次循環完成后的所有螞蟻按照路徑長短排序，雖然增加了空間復雜度，但讓螞蟻能夠更快地找到最優路徑，從而提高了算法的執行效率。

4.2 收斂性分析

ORGA是以航線網絡圖為基礎，并以蟻群算法為基本思想的最優航線生成算法。Gutjahr W J已經在理論上對圖搜素螞蟻系統（graph-based ant system，GBAS）的收斂性進行了證明，在符合一些前提條件時，GBAS可以以接近于1的概率收斂于最優解，而ORGA也滿足GBAS的4個條件：

（1）經過仿真試驗并按照經驗，可以將參數α取值為1。

（2）設計航線時，一般從起點到終點的最優航線與從終點到起點的最優航線是不一致的，這是因為各種環境因素的影響等都不盡相同，并且還伴隨著順流逆流問題的存在，所以最優路徑也是唯一的。

（3）根據式（5），期望因子ηij>0。

（4）信息素濃度更新使用的是全局更新策略，只是對前h只螞蟻所走過的路徑適當增加額外的信息素量。

5 仿真試驗

5.1 仿真環境

實驗采用OpenCPNSDK，它是對OpenCPN進行封裝后，提供給電子海圖應用系統開發商進行二次開發的組件包，可提供COM組件和C+ +動態庫兩種形式封裝，支持WINDOWS，WINCE和LINUX平臺。利用OpenCPNSDK，用戶可開發出自己的支持S57和S52標準的電子海圖系統，并與雷達、AIS等系統結合，開發出多種船用或岸上應用系統。OpenCPNSDK可根據用戶的應用需求提供靈活的、有針對性的封裝，從而最大程度地幫助用戶增強系統功能，提高系統性能，縮短開發周期和減少開發成本。在Visual Studio 2008平臺下，基于組件包OpenCPNSDK采用VC+ +語言進行系統開發。

5.2 結果

Dijkstra算法中兩節點之間的權值大小按照式（4）進行設置，設定1=0.4，2=0.3，3=0.3。ORGA中的各參數設置如下：α=1，β=5，ρ=0.2，m=60，w=m/2。式（5）中：dij和Rij范圍均為[0，10]；Wij的范圍為[0，5]（陰晴用0表示；小雨或小雪在[0.1，0.2）內取值；中雨或中雪在[0.2，0.5）內取值；大雨或大雪在[0.5，1）內取值；暴風雨在[1，3）內取值；大霧在[3，5]內取值）；Cij，海況正常用0表示，有暴浪致使不能航行的情況用∞表示。以下是航行起點為寧波-舟山港蝦峙門的進口燈船，終點為金塘港，航線規劃經過蝦峙門航道和螺頭航道，使用Dijkstra算法和ORGA生成的最短距離航線分別見圖1和2。圖1中所得最優航線的里程為45.6 n mile，轉向點數為18；圖2中所得最優航線的里程為42.8 n mile，轉向點數為6。

由試驗可知：ORGA克服了Dijkstra算法對復雜礙航區處理不完備的問題，進一步優化了航線繞行礙航區的策略；ORGA耗時2.450 s，而Dijkstra算法耗時4.556 s，故ORGA相對Dijkstra算法在時間上有明顯優勢。

6 結束語

分析了各種環境因素對航線設計的影響，簡述了各種影響因素的來源和確定方法，提出了在電子海圖顯示與信息系統（ECDIS）中以航行綜合成本最低為目標的航線設計算法。重點討論了基于電子海圖的最優航線算法的設計，并且對所提出的算法進行了仿真試驗分析，達到了預期的效果。

參考文獻：

[1] 李源惠， 孫少鵬. 電子海圖中計劃航線可行性的自動判別[J]. 大連海事大學學報， 2000， 26（2）： 40-43.

[2] CHANG K Y， JAN G E， PARBERRY I. A method for searching optimal routes with collision avoidance on raster charts[J]. The Journal of Navigation， 2003， 56（3）： 371-384.

[3] RAFAL S. A new method of ship routing on raster grids， with turn penalties and collision avoidance[J]. The Journal of Navigation， 2006， 59（1）： 371-384.

[4] 葉清， 郁振偉. 改進最短路徑算法在最佳航線選擇中的應用[J]. 中國航海， 2003， 55（2）： 15-17.

[5] 王德春， 陳利敏， 張孝芳. 基于A*算法的艦船最佳選擇[J]. 青島大學學報（自然科學版）， 2005， 18（4）： 10-13.

[6] 王科. 基于電子海圖的航線設計研究[D]. 大連： 海軍大連艦艇學院， 2004.

[7] 聶皓冰， 王勝正， 胡志武， 等. 航線動態優化算法在海上搜救中的應用[J]. 上海海事大學學報， 2011， 32（4）： 1-6.

[8] 陳寶文. 蟻群優化算法在車輛路徑問題中的應用研究[D]. 哈爾濱： 哈爾濱工業大學， 2009.

[9] 朱青. 基于蟻群算法的船舶航行設計方法的研究[D]. 哈爾濱： 哈爾濱工程大學， 2011.

[10] 何立居， 李啟華. 基于蟻群算法的航線自動生成研究[J]. 中國航海， 2009， 32（3）： 71-75.

[11] BIJLSMA S J. On the applications of the principle of optimal evolution in ship routing[J]. Journal of the Institute of Navigation， 2004， 51（2）： 93-100.

[12] 馬榮貴， 崔華， 薛世焦. 改進蟻群算法的多約束質量最優路徑選擇[J]. 西安電子科技大學學報（自然科學版）， 2016， 43（3）： 185-189.

[13] 湯青慧， 唐旭， 崔曉暉. 基于動態通達網絡模型的最優航程規劃方法[J]. 武漢大學學報（信息科學版）， 2015， 40（4）： 521-526.

[14] 李松江， 張異， 龔躍.基于蟻群算法的智能交通最優路徑研究[J]. 長春理工大學學報（自然科學版）， 2015， 38（4）： 122-126.

（編輯 趙勉）endprint