船舶航線生成研究

李成海 劉杰 胡甚平 崔建輝

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

關(guān)鍵詞：船舶航行；船舶航線生成；蟻群計(jì)算法；搜尋策略；計(jì)算法流程

中圖分類號：U697.3

文獻(xiàn)識別碼：A

0 引 言

船舶航行過程中航線繪制是最關(guān)鍵環(huán)節(jié)，繪制航線需要充分考慮海區(qū)季節(jié)性風(fēng)浪影響、海區(qū)地理環(huán)境和海盜威脅等因素的影響，以經(jīng)濟(jì)、安全和高效三大指標(biāo)為研究對象，力爭達(dá)到航線生成最優(yōu)。航線繪制受到時(shí)間，思維環(huán)境眾多因素影響，導(dǎo)致繪制的航線有缺失。

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

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

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

1.1 ?蟻群計(jì)算法

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

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

1.2 ?設(shè)計(jì)海區(qū)柵格

設(shè)計(jì)海區(qū)柵格時(shí)需要充分考慮船舶航線生成的精準(zhǔn)度和高效性。柵格設(shè)計(jì)的越密集，則生成的船舶航行航線越精準(zhǔn)，缺點(diǎn)是計(jì)算量巨大[10]。本研究從計(jì)算航行區(qū)水域?qū)挾?，確立劃分船舶航行海區(qū)柵格的方法。

考慮到外界因素影響，船舶航行路線，可為一個(gè)以設(shè)計(jì)的計(jì)劃航線為中心向左右外延一定寬度的帶區(qū)，稱為航行區(qū)水域?qū)挾?。航行區(qū)水域?qū)挾扔啥ㄎ痪群屯饨鐥l件所決定。在設(shè)定航行區(qū)水域?qū)挾葧r(shí)，考慮到定位精度的影響，以3倍均方差取值作為航行區(qū)水域?qū)挾缺容^合理，此時(shí)船舶航行于航行區(qū)水域?qū)挾韧獾母怕蚀笥?‰。航行船舶用路標(biāo)導(dǎo)航時(shí)，航行區(qū)水域?qū)挾炔恍∮?.05 n mile，但GPS導(dǎo)航時(shí)，航行區(qū)水域?qū)挾刃∮?.03 n mile?；緦挾刃枰鶕?jù)駕駛員的業(yè)務(wù)和當(dāng)時(shí)海況等確定。

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

1.3 ?網(wǎng)柵信息

蟻群計(jì)算法依據(jù)網(wǎng)柵的信息集，搜尋的最優(yōu)信息作為計(jì)算數(shù)據(jù)，網(wǎng)柵信息主要有，坐標(biāo)系、航行狀態(tài)、信息源和發(fā)揮系數(shù)組成。

網(wǎng)柵信息結(jié)構(gòu)組成：

structure information：

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

信息源ψ代表該處螞蟻通行指數(shù)，它是螞蟻搜尋策略的關(guān)鍵，各處初始值相等，當(dāng)搜尋過程中擴(kuò)散和懲罰發(fā)揮作用，螞蟻經(jīng)過多處數(shù)值大，經(jīng)過處少則數(shù)值小[13-14]。

發(fā)揮系數(shù)?代表螞蟻策略值，表示為不固定的到達(dá)目的地所需距離[15]。

1.4 ?搜尋方法

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

本研究依據(jù)蟻群計(jì)算中的MAX-MIN系統(tǒng)，一般計(jì)算法和混合算法，選用下列搜尋方法。

（1）向前搜尋方法

根據(jù)航線生成蟻群搜尋最優(yōu)是關(guān)鍵這一思路，螞蟻在網(wǎng)柵內(nèi)向前運(yùn)動(dòng)時(shí)，有如下規(guī)則：

①向前運(yùn)動(dòng)前方的柵格是可行性的；

②向前運(yùn)動(dòng)前方柵格相比目前位置到目的地距離?。?/p>

③當(dāng)向前運(yùn)動(dòng)網(wǎng)柵滿足上述兩條件時(shí)，如有多個(gè)選項(xiàng)，可用加權(quán)法隨機(jī)選取。

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

輪盤法和最優(yōu)化法各自計(jì)算向前運(yùn)動(dòng)前方柵格的付出代價(jià)值F（g）：

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

最簡捷高效的方法是選取值小的柵格作為運(yùn)動(dòng)前方柵格；輪盤法依據(jù)前方柵格格式的代價(jià)值，選取向前運(yùn)動(dòng)前方柵格。

當(dāng)向前運(yùn)動(dòng)前方柵格選取后，當(dāng)前柵格選進(jìn)航行路線點(diǎn)表；向前運(yùn)動(dòng)前方柵格設(shè)置為目前位置。重復(fù)上述操作，直到蟻群搜尋到目標(biāo)終點(diǎn)。

（2）向后搜尋方法

如果螞蟻某處的向前運(yùn)動(dòng)?xùn)鸥袢繛椴豢上蚯皷鸥駮r(shí)，須作向后搜尋過程。螞蟻搜尋路線，如圖1所示。

1.5 ?更新信息

更新信息是指，當(dāng)每只螞蟻搜尋結(jié)束并最終到達(dá)目的地后；一蟻群生成最優(yōu)的前行運(yùn)動(dòng)航路后。

更新信息內(nèi)容有“擴(kuò)散”和“激勵(lì)”。

更新信息的公式為：

（1）

式（1）中，ρ（1>ρ>0）代表控制信息增量參數(shù)，（1-ρ）ψ（e）使用網(wǎng)柵柵格e的信息被“擴(kuò)散”，這成為對全體柵格的操作；ρ[Δψ（e）]是給予向前運(yùn)動(dòng)?xùn)鸥竦摹凹?lì)”，只被允許對航路表中的柵格操作。T代表常數(shù)，T的大小表示每次激勵(lì)的程度。F（e）表示通過e柵格付出的代價(jià)。

經(jīng)更新信息后，沒有螞蟻出沒的柵格，因?yàn)椤皵U(kuò)散”作用，信息強(qiáng)度逐漸減弱，對螞蟻的吸引力減小，螞蟻經(jīng)常出沒的柵格，因?yàn)椤凹?lì)”作用，信息強(qiáng)度逐漸增強(qiáng)，對螞蟻的吸引力增大。

1.6 ?優(yōu)選航線

優(yōu)選航線是所有蟻群或一代蟻群搜尋結(jié)束后，生成的最優(yōu)蟻群和最優(yōu)的航行路線。

優(yōu)選航行路線的標(biāo)準(zhǔn)：船舶航經(jīng)的路線使之付出最小的代價(jià)。船舶航經(jīng)路線付出的代價(jià)包括應(yīng)對航行風(fēng)險(xiǎn)WG和經(jīng)濟(jì)效益的損失We。

應(yīng)對船舶航行風(fēng)險(xiǎn)WG包括礙航物、海盜襲擊和航道限制等。

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

礙航物導(dǎo)致航行船舶付出的代價(jià)：

（2）

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

航道限制導(dǎo)致船舶付出的代價(jià)：

（3）

式（3）中，DC代表系數(shù)，m代表航行路線轉(zhuǎn)向點(diǎn)數(shù)，Cgfkr代表航路點(diǎn)水深，Ce代表航行安全水深，Cvbpk代表船舶吃水。

1.7 ?計(jì)劃航線的處理

基于網(wǎng)柵柵格劃分的蟻群計(jì)算法設(shè)計(jì)的船舶航行路線，呈現(xiàn)齒形形狀，需要取直處理，才能成為真正的設(shè)計(jì)航線。

取直處理原則：

（1）船舶航行經(jīng)過海區(qū)的水深須滿足船舶吃水的要求，且大于船舶航行的安全水深。

（2）船舶航行經(jīng)過海區(qū)船位與礙航物的距離須大于危險(xiǎn)半徑，且大于船舶航行的安全距離。

（3）航線上盡量減少轉(zhuǎn)向點(diǎn)，且要求航程最短。

根據(jù)取直處理原則，采用以下步驟進(jìn)行計(jì)劃航線處理：

（1）航線的目的地設(shè)置為標(biāo)準(zhǔn)點(diǎn)；

（2）沿著航線從起始航點(diǎn)到目的地標(biāo)準(zhǔn)點(diǎn)逐個(gè)檢查，并各轉(zhuǎn)向點(diǎn)連成直線，然后連線向兩側(cè)擴(kuò)大航行范圍形成航行區(qū)帶，檢查航行區(qū)帶是否與礙航物危險(xiǎn)半徑或不滿足要求的淺水區(qū)有交匯點(diǎn)，如果有交集，須如下處理：記下該交匯點(diǎn)，以此交匯點(diǎn)作為標(biāo)準(zhǔn)點(diǎn)，重復(fù)（2）步驟，直到符合要求。

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

2 船舶航行計(jì)劃航線自動(dòng)生成的蟻群計(jì)算法程序

船舶航行計(jì)劃航線自動(dòng)生成的蟻群計(jì)算法程序，見表3。

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

在船舶航行計(jì)劃航線自動(dòng)生成進(jìn)程中，在優(yōu)化搜尋的前提條件下，形成多條可航行路線，從已產(chǎn)生的NXM條可航行路線中選取最經(jīng)濟(jì)最短的航行路線。

船舶航行計(jì)劃航線自動(dòng)生成的計(jì)算法范例，如圖3所示。

根據(jù)蟻群計(jì)算法思路和程序，運(yùn)用vc++6.0編程程序，使蟻群計(jì)算法船舶航行計(jì)劃航線自動(dòng)生成成為事實(shí)。圖4為黃海北部，隨意選取的船舶航線路線起始點(diǎn)和目的地，利用蟻群計(jì)算法自動(dòng)生成的船舶航行路線范例。

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

3 結(jié)束語

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

參考文獻(xiàn)

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

[2] 黨慶一.數(shù)據(jù)驅(qū)動(dòng)的艦船航線生成算法[J].艦船科學(xué)技術(shù)，2019，41（02）：7-9.

[3] 張立華，戴澤源，賈帥東.融合多幅海圖的航線自動(dòng)生成改進(jìn)方法[J].哈爾濱工程大學(xué)學(xué)報(bào)，2019，40（06）：1090-1097.

[4] 呂錦濤，劉志強(qiáng)，王娜.基于航路堆棧的航線自動(dòng)生成方法[J].計(jì)算機(jī)應(yīng)用，2018，38（S1）：16-19.

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

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

[7] 李啟華，李曉陽，吳國華.蟻群搜索與遺傳優(yōu)化結(jié)合的航線自動(dòng)生成[J].廣州航海學(xué)院學(xué)報(bào)，2014，22（04）：11-14.

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

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

[10] 李冉. 基于AIS數(shù)據(jù)的內(nèi)河船舶習(xí)慣航線生成研究[D].大連海事大學(xué)，2019.

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

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

[13] 馬升麾. 基于AIS數(shù)據(jù)的航線生成[D].大連海事大學(xué)，2017.

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

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

基金項(xiàng)目： 1.國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（3.1）2021YFC2801000，北極航道通信導(dǎo)航保障技術(shù)研究與系統(tǒng)開發(fā)。

2.國家重點(diǎn)研發(fā)計(jì)劃項(xiàng)目（4.2）2019YFB1600602，在航船舶安全風(fēng)險(xiǎn)辨識與防控平臺。

作者簡介：

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