船舶航線生成研究

李成海 劉杰 胡甚平 崔建輝

摘 要：基于減輕船舶駕駛航線繪制勞動強度，克服繪制過程中人為主觀因素影響的考慮，引進了蟻群計算法自動生成船舶航線研究問題。利用電子海圖、闡述更好信息、搜尋策略、劃分網絡、選取航線、不航航和算法流程的具體做法。案例驗證證明：船舶航線生成運用蟻群計算法具有準確和時效性。該研究實現了運用專家的搜尋策略思維下的船舶航行航線繪制的自動化，為制定船舶航線的高效、安全提供了理論依據。

關鍵詞：船舶航行；船舶航線生成；蟻群計算法；搜尋策略；計算法流程

中圖分類號：U697.3

文獻識別碼：A

0 引 言

船舶航行過程中航線繪制是最關鍵環節，繪制航線需要充分考慮海區季節性風浪影響、海區地理環境和海盜威脅等因素的影響，以經濟、安全和高效三大指標為研究對象，力爭達到航線生成最優。航線繪制受到時間，思維環境眾多因素影響，導致繪制的航線有缺失。

隨著電子海圖技術的開發和利用，實現了船舶航線的自動生成。目前關于船舶航行航線自動生成的研究有：吳澤亮[1] 運用Adadelta算法使蟻群算法具有更強的隨機性，提高了蟻群算法的性能。生成了一條距離最短且避開了礙航物的航線，而且。黨慶一[2] 運用蟻群算法搜尋產生初始種群，再利用遺傳計算法對各航線優化，獲取最優航線。張立華等[3]通過對海圖精度的定量分析，建立礙航物數據資料庫，在二叉樹計算法基礎上，運用改進R的航行窗口提高航線生成效率。呂錦濤等[4]在同樣的搜索效果前提下，運用航路堆棧航線生成法和當前的航路點，實時制定最優航線。王濤等[5]運用風、流作用的漂移量和航道富裕寬度，建立航道寬度計算模型，從而生成了考慮航道寬度的航行距離最短航線。張金水等[6]通過蟻群計算法和遺傳計算法相結合研究航行船舶航線生成辦法，在考慮了海圖信息離散化和蟻群搜索生成初始種群的基礎上，利用遺傳優化取得最優航線。

本研究為提高航線繪制的高效和安全目的，引入了蟻群計算法，方便船舶航行航線生成研究。

1 基于蟻群計算法的船舶航線生成研究

1.1 ?蟻群計算法

螞蟻從蟻窩對食品源的尋覓路徑各不相同，但最終會匯集于同一最短捷徑，這蟻群覓食路徑留下的外激素成為交互信息源，從而找到螞蟻覓食最佳路線。螞蟻計算法是基于螞蟻的自然功能設計的最佳決策方法，設某一數量的螞蟻，被設定的覓食規則獲取的最好路線[7-8]。

船舶航行航線生成，是依據季節性風浪影響、海區地理環境和人——機協調條件，搜尋的一條最經濟又安全的航行路線，這與蟻群計算法適用條件高度一致。利用船用電子海圖的海區信息功能，查找蟻群計算法信息生成所需要的航道寬度、海區水深、所經航區上的危險沉船及禁航區、管制區等信息，為蟻群計算提供便利[9]。因此，船舶航線生成引入蟻群計算法，完全可行。

1.2 ?設計海區柵格

設計海區柵格時需要充分考慮船舶航線生成的精準度和高效性。柵格設計的越密集，則生成的船舶航行航線越精準，缺點是計算量巨大[10]。本研究從計算航行區水域寬度，確立劃分船舶航行海區柵格的方法。

考慮到外界因素影響，船舶航行路線，可為一個以設計的計劃航線為中心向左右外延一定寬度的帶區，稱為航行區水域寬度。航行區水域寬度由定位精度和外界條件所決定。在設定航行區水域寬度時，考慮到定位精度的影響，以3倍均方差取值作為航行區水域寬度比較合理，此時船舶航行于航行區水域寬度外的概率大于3‰。航行船舶用路標導航時，航行區水域寬度不小于0.05 n mile，但GPS導航時，航行區水域寬度小于0.03 n mile。基本寬度需要根據駕駛員的業務和當時海況等確定。

將船舶航行區寬度作為設計海圖柵格為單位，可使生成的航行航線保證船舶航行安全。對于狹窄航道，大多采用陸標導航方法航行，選用的航行區寬度需要航道寬度大于多倍船寬即可，具體寬度值需要根據航道的彎曲度、風流等情況確定[11-12]。

1.3 ?網柵信息

蟻群計算法依據網柵的信息集，搜尋的最優信息作為計算數據，網柵信息主要有，坐標系、航行狀態、信息源和發揮系數組成。

網柵信息結構組成：

structure information：

Longitude和latitude代表網柵的經度和緯度，當網柵設置完成，網柵的經緯度值則確定。航行狀態state，可航行性為real，不然為fake。網柵的初始情形為real，在搜尋過程中，部分或全部路線受阻，航行狀態state，可能由real演變成fake。

信息源ψ代表該處螞蟻通行指數，它是螞蟻搜尋策略的關鍵，各處初始值相等，當搜尋過程中擴散和懲罰發揮作用，螞蟻經過多處數值大，經過處少則數值小[13-14]。

發揮系數?代表螞蟻策略值，表示為不固定的到達目的地所需距離[15]。

1.4 ?搜尋方法

蟻群計算法的關鍵是搜尋，好的搜尋計算法，可使計算過程精準、高效，否則計算過程差錯頻出和遲緩。一種便捷的方法就是借鑒專家的研究成果，提高航線生成效率。

本研究依據蟻群計算中的MAX-MIN系統，一般計算法和混合算法，選用下列搜尋方法。

（1）向前搜尋方法

根據航線生成蟻群搜尋最優是關鍵這一思路，螞蟻在網柵內向前運動時，有如下規則：

①向前運動前方的柵格是可行性的；

②向前運動前方柵格相比目前位置到目的地距離小；

③當向前運動網柵滿足上述兩條件時，如有多個選項，可用加權法隨機選取。

加權法隨機選取：根據蟻群搜索過程，隨機選取輪盤法、最優化法隨機取值范圍，設定權重，再選取使用方法。這樣做的優點是擴大搜尋范圍，創造被選條件，減少搜尋阻斷可能，最優搜尋效率高。在設定權重時，輪盤法搜尋初始取值0.9，最優化法取值0.1，從而確保搜尋范圍，搜尋第二期權重值交換，提高收斂效率；蟻群搜尋過程中，輪盤法的權重為0.9-0.8×j/M，j代表迭代頻次，M代表迭代總次數。

輪盤法和最優化法各自計算向前運動前方柵格的付出代價值F（g）：

式中的α、β代表常數，可控制信息源ψ和發揮系數?的影響范圍，m代表可選的前方柵格數。

最簡捷高效的方法是選取值小的柵格作為運動前方柵格；輪盤法依據前方柵格格式的代價值，選取向前運動前方柵格。

當向前運動前方柵格選取后，當前柵格選進航行路線點表；向前運動前方柵格設置為目前位置。重復上述操作，直到蟻群搜尋到目標終點。

（2）向后搜尋方法

如果螞蟻某處的向前運動柵格全部為不可向前柵格時，須作向后搜尋過程。螞蟻搜尋路線，如圖1所示。

1.5 ?更新信息

更新信息是指，當每只螞蟻搜尋結束并最終到達目的地后；一蟻群生成最優的前行運動航路后。

更新信息內容有“擴散”和“激勵”。

更新信息的公式為：

（1）

式（1）中，ρ（1>ρ>0）代表控制信息增量參數，（1-ρ）ψ（e）使用網柵柵格e的信息被“擴散”，這成為對全體柵格的操作；ρ[Δψ（e）]是給予向前運動柵格的“激勵”，只被允許對航路表中的柵格操作。T代表常數，T的大小表示每次激勵的程度。F（e）表示通過e柵格付出的代價。

經更新信息后，沒有螞蟻出沒的柵格，因為“擴散”作用，信息強度逐漸減弱，對螞蟻的吸引力減小，螞蟻經常出沒的柵格，因為“激勵”作用，信息強度逐漸增強，對螞蟻的吸引力增大。

1.6 ?優選航線

優選航線是所有蟻群或一代蟻群搜尋結束后，生成的最優蟻群和最優的航行路線。

優選航行路線的標準：船舶航經的路線使之付出最小的代價。船舶航經路線付出的代價包括應對航行風險WG和經濟效益的損失We。

應對船舶航行風險WG包括礙航物、海盜襲擊和航道限制等。

經濟效益損失We包括因繞航造成航時的延長和耗油總量的增加。本研究將經濟效益損失簡化為航行路程的函數：WG=DG/C。C代表船舶航行距離，DG代表系數。

礙航物導致航行船舶付出的代價：

（2）

式（2）中，DB代表系數，m代表航線上的礙航物總數，Cf代表航線距離礙航物的最小距離，CebP代表船舶航行所需的安全距離，Vc代表礙航物的半徑。

航道限制導致船舶付出的代價：

（3）

式（3）中，DC代表系數，m代表航行路線轉向點數，Cgfkr代表航路點水深，Ce代表航行安全水深，Cvbpk代表船舶吃水。

1.7 ?計劃航線的處理

基于網柵柵格劃分的蟻群計算法設計的船舶航行路線，呈現齒形形狀，需要取直處理，才能成為真正的設計航線。

取直處理原則：

（1）船舶航行經過海區的水深須滿足船舶吃水的要求，且大于船舶航行的安全水深。

（2）船舶航行經過海區船位與礙航物的距離須大于危險半徑，且大于船舶航行的安全距離。

（3）航線上盡量減少轉向點，且要求航程最短。

根據取直處理原則，采用以下步驟進行計劃航線處理：

（1）航線的目的地設置為標準點；

（2）沿著航線從起始航點到目的地標準點逐個檢查，并各轉向點連成直線，然后連線向兩側擴大航行范圍形成航行區帶，檢查航行區帶是否與礙航物危險半徑或不滿足要求的淺水區有交匯點，如果有交集，須如下處理：記下該交匯點，以此交匯點作為標準點，重復（2）步驟，直到符合要求。

（3）設計航線的起始點和目的地終點與步驟（2）記錄的交匯點處理后形成的新點的連線，就成為一條取直的計劃航線。取直過程如圖2所示。

2 船舶航行計劃航線自動生成的蟻群計算法程序

船舶航行計劃航線自動生成的蟻群計算法程序，見表3。

網柵柵格初始信息源ψ，都設置為0.5，發揮系數?依據網柵柵格到目的地終點距離Cj大小來確定，?j=10/Dj j開始的可航行狀態，根據電子匯圖提供的水深和等深線信息資料，運用高端模型（digital、evaluation、model，DEM）對圖上各點水深量進行計算，看其水深值是否符合要求，選取real還是fake。

在船舶航行計劃航線自動生成進程中，在優化搜尋的前提條件下，形成多條可航行路線，從已產生的NXM條可航行路線中選取最經濟最短的航行路線。

船舶航行計劃航線自動生成的計算法范例，如圖3所示。

根據蟻群計算法思路和程序，運用vc++6.0編程程序，使蟻群計算法船舶航行計劃航線自動生成成為事實。圖4為黃海北部，隨意選取的船舶航線路線起始點和目的地，利用蟻群計算法自動生成的船舶航行路線范例。

海區搜尋范圍為10×7 n mile，船舶航行區帶設定為0.2 n mile，每群螞蟻數設定為10，迭代總次數設定為100，圖4中圓圈為設定的礙航物危險范圍，利用P4 2.8G計算機運作，航線生成時間小于1 s。圖4中齒形線為蟻群計算法自動生產的最初優化船舶航行路線，粗線為去之后的船舶航行計劃航線。圖4中最初優化航線齒形曲折，是蟻群中螞蟻數較少導致的，增大蟻群中螞蟻數，同時增加迭代次數，將產生最優效果。取直后的船舶航行路線和人工繪制的航行路線基本相同。

3 結束語

通過圖4的范例，進一步表明蟻群計算法對于自動生成船舶航行線路具有可行性。這不僅能減輕船舶駕駛員繁重的工作，同時提高了生成船舶航行線路的效率，同時不超過1 s。這條航行線路綜合考慮了影響船舶航行安全的各種因素，克服了人工繪制航行路線用時長，且常因考慮不周全導致不是最優化航行路線的難題，最大的優點是廣采專家思路，在搜尋過程中體現，使生成的船舶航行路線更具專家思路，從而該航行線路最優。

參考文獻

[1] 吳澤亮.基于蟻群算法的航線自動生成方法[J].艦船科學技術，2019，41（14）：43-45.

[2] 黨慶一.數據驅動的艦船航線生成算法[J].艦船科學技術，2019，41（02）：7-9.

[3] 張立華，戴澤源，賈帥東.融合多幅海圖的航線自動生成改進方法[J].哈爾濱工程大學學報，2019，40（06）：1090-1097.

[4] 呂錦濤，劉志強，王娜.基于航路堆棧的航線自動生成方法[J].計算機應用，2018，38（S1）：16-19.

[5] 王濤，張立華，彭認燦，曹鴻博，姜林君.顧及航道寬度的最短距離航線自動生成方法[J].海洋測繪，2016，36（03）：29-31+36.

[6] 張金水，何立居，李啟華，李曉陽，吳國華.蟻群算法和遺傳算法結合的航線生成[J].中國航海，2015，38（02）：9-12+17.

[7] 李啟華，李曉陽，吳國華.蟻群搜索與遺傳優化結合的航線自動生成[J].廣州航海學院學報，2014，22（04）：11-14.

[8] 張浩，張梅彩，陳建華.最短時間航線自動生成的改進方法[J].海洋測繪，2014，34（04）：47-49+54.

[9] 張樹凱，劉正江，蔡垚，史國友，梁偉珍.無人船艇航線自動生成研究現狀及展望[J].中國航海，2019，42（03）：6-11.

[10] 李冉. 基于AIS數據的內河船舶習慣航線生成研究[D].大連海事大學，2019.

[11] 張海妮.基于蟻群優化算法的無人船艇航線自動生成及路徑規劃[J].艦船電子工程，2019，39（03）：46-49+97.

[12] 劉高磊，張鋒，呂建，趙延鵬，黃富程.一種利用AIS數據挖掘的航線生成方法[J].中國水運（下半月），2018，18（12）：61-63.

[13] 馬升麾. 基于AIS數據的航線生成[D].大連海事大學，2017.

[14] 王濤，張立華，彭認燦，曹鴻博，姜林君.考慮轉向限制的電子海圖最短距離航線自動生成方法[J].哈爾濱工程大學學報，2016，37（07）：923-929.

[15] 張浩，張梅彩，陳建華.最短時間航線自動生成的改進方法[J].海洋測繪，2014，34（04）：47-49+54.

基金項目： 1.國家重點研發計劃項目（3.1）2021YFC2801000，北極航道通信導航保障技術研究與系統開發。

2.國家重點研發計劃項目（4.2）2019YFB1600602，在航船舶安全風險辨識與防控平臺。

作者簡介：

李成海，正高級船長，副教授，主要研究方向：海上航行安，（E-mail）LICHENGHAI@163.com