考慮轉向限制的電子海圖最短距離航線自動生成方法

王濤，張立華，彭認燦，曹鴻博，3，姜林君3

（1.海軍大連艦艇學院 海洋測繪系，遼寧 大連 116018；2.海軍大連艦艇學院 海洋測繪工程軍隊重點實驗室，遼寧 大連116018；3.海軍出版社，天津300450）

考慮轉向限制的電子海圖最短距離航線自動生成方法

王濤1，2，張立華1，2，彭認燦1，2，曹鴻博1，2，3，姜林君3

（1.海軍大連艦艇學院 海洋測繪系，遼寧 大連 116018；2.海軍大連艦艇學院 海洋測繪工程軍隊重點實驗室，遼寧 大連116018；3.海軍出版社，天津300450）

針對當前航路二叉樹方法求解最短距離航線未考慮艦船轉向限制的問題，提出了一種顧及轉向限制的最短距離航線自動生成方法。通過判斷航線轉向操縱緩沖區(qū)是否與礙航區(qū)相交，測試航線的可轉向性；利用艦船轉向次數(shù)、轉向角度和轉向半徑，引入圓弧影響系數(shù)和回轉速降系數(shù)，構建轉向限制模型，實現(xiàn)了顧及轉向限制的最短距離航線自動生成。實驗結果表明：所提方法可排除當前最短距離航線生成方法中的不可行航線，優(yōu)化了航線的轉向次數(shù)和轉向角度。

電子海圖；礙航區(qū)；緩沖區(qū)；最短距離航線；轉向限制

Kimeyesw a onrdds turn angles of the shortest route can be optimized. :electronic navigational chart；obstacle areas；buffer zone；shortest route；turning restriction

電子航海圖（electronic navigational chart，ENC）已經(jīng)廣泛應用于海上航行，最優(yōu)航線設計是電子航海圖系統(tǒng)應用的重要內容［1-3］。最優(yōu)航線是在保證艦船航行安全的前提條件下，使航線達到某種指標上的最佳［4-6］。民用船只的航線通常較為固定［1］，但是在海上避難、搜救等應急行動以及軍事行動中，需要靈活多變地選擇航線［7］。近年來，最短距離航線設計成為眾多學者關注的問題。張立華等提出了矢量電子海圖平臺下的計算機智能設計航線方法［8］。在此基礎上，汪柱等提出了基于航路二叉樹的航線自動生成方法［9］。曹鴻博等對航路二叉樹方法進行了改進，采用礙航區(qū)路徑的遞歸搜索、繞行優(yōu)化以及動態(tài)求解等策略，實現(xiàn)了復雜礙航區(qū)的航線自動生成［10］。但是這些現(xiàn)有的方法在考慮航線距離最短時，仍忽視了一個很重要的問題，即艦船轉向對最短距離航線的影響。這種影響主要表現(xiàn)在兩個方面:1）得到的最短距離航線在實際中未必是真正可行的。現(xiàn)有的航路二叉樹方法所生成的最短距離航線，在繞行礙航區(qū)的轉向過程中，理想地采用直線路徑，未考慮艦船需要循圓弧線逐漸轉向的實際操縱，可能造成當前方法生成的航線在實際中無法真正安全航行。2）得到的航線未必是實際航行中最短的。當前方法僅理想地考慮直線距離上的最短，未有效顧及艦船轉向次數(shù)、角度等對航線的影響。實際上，轉向時會造成弧線航程增大，還可能引起船速降低，從而造成當前方法生成的最短距離航線在實際航行中未必是距離最短的。因此，研究顧及轉向限制的電子海圖最短距離航線自動生成具有理論和現(xiàn)實意義。

1　顧及轉向限制的最短距離航線自動生成

1.1不可轉向航線的排除

1.1.1艦船的圓弧轉向

艦船具有一定的旋回半徑和慣性，在循圓弧線連續(xù)不斷的完成每次轉向的過程中，弧線路徑已經(jīng)偏離原直線路徑，從而造成當前方法生成的最短距離航線在實際中并不一定能夠順利實施轉向［11-12］。如圖1所示。

圖1　艦船繞行礙航區(qū)轉向示意圖Fig.1 A sketch map of ship turning around obstacles

以當前方法生成的某一繞行礙航區(qū)O1的路徑Pi-1PiPi+1為例，航段Pi-1Pi和航段PiPi+1的航向改變量θ叫做轉向角［13］。根據(jù)轉向操縱理論［13］，艦船繞行礙航區(qū)O1由航段Pi-1Pi到航段PiPi+1時，無法沿直線直接突然轉向，通常需沿圓弧路徑連續(xù)、不斷地完成轉向，但已較大地脫離了原有的直線路徑Pi-1PiPi+1，造成穿越礙航區(qū)O1，從而使得直線路徑Pi-1PiPi+1在實際中并不真正可行。為保證航行安全，繞行的圓弧路徑應在礙航區(qū)O1的外側，為，但這樣在A、B點處的路徑仍是突然轉向的，仍無法真正沿航行。實際操縱中，通常應進行三次轉向才能繞行礙航區(qū)O1［13］:第1次轉向起點為C1，終點為D1，從直線航段Pi-1C1連續(xù)轉到較大弧線航段；第2次轉向起點為D1，終點為C2，沿較大弧線航段航行；第3次轉向起點為C2，終點為D2，從較大弧線航段逐漸轉回直線航段。這樣，艦船繞行礙航區(qū)O1的實際航行路徑為和D2Pi+1，與直線航段Pi-1PiPi+1在地理位置上發(fā)生較大的變化。這種變化的路徑仍可能會穿越礙航區(qū)（如圖2中的穿越礙航區(qū)O2），從而造成當前方法生成的航線Pi-1PiPi+1并不可行。因此，在最短距離航線生成中，必須排除當前方法中實際上并不真正可行的航線。

1.1.2轉向圓弧的確定及離散化處理

如圖2所示，在艦船的某次轉向過程中，為確定轉向時的弧線路徑和，只需計算圓心c2及點C1和D1、圓心c1及點D1和C2、圓心c3及點C2和D2的坐標。以圓心c1及點D1和C2的坐標求解為例（同理可求c2及C1和D1、c3及C2和D2的坐標），在以圓心c1（0，0）為原點、c1Pi為x軸正向的局部右手笛卡爾坐標系下，其計算公式如下

式中:r為定常旋回半徑，θ1（θ1∈（0，π］）為初始轉向角，可由下式計算:

圖2　轉向圓弧的確定Fig.2 Calculation of turning arc

在求c2、C1、D1和c3、C2、D2的坐標時，需先求第1次轉向時的轉向角θ2和第2次轉向時的轉向角θ3，θ2和θ3可由下式計算（第3次轉向時的轉向角大小與θ2相同）:

式中:由于∠Ac2E較小，可將其忽略?；喓螃?、θ3計算公式如下

為簡便，對航線轉向處的轉向圓弧進行離散化處理。如圖3所示，用A、P0、P1、P2、B這5個點的連線來逼近表示圓弧，內插采樣點（如P0）個數(shù)n根據(jù)圓心角α和采樣間隔Δα確定，公式如下

圖3　圓弧的離散化處理Fig.3 The discretization processing method of the circular arc

1.1.3航線可轉向性的判斷

如圖4所示，當前方法中，因障礙物位置的準確性、風（流、浪）等不確定性因素會影響航行安全［14-15］，已對障礙區(qū)（或物）的范圍進行了一定的擴充，稱為礙航物緩沖區(qū)［8］。然而在艦船航行的過程中，艦船的操縱誤差以及導航定位系統(tǒng)精度等因素（稱為操縱不確定性），還會對航行路徑造成一定的影響，這在艦船轉向時是必須考慮的［16-17］。由此引起轉向路徑的不確定性，采用轉向操縱緩沖區(qū)來表示。

對于給定的某一條計劃航線，其可轉向性N依賴于其轉向操縱緩沖區(qū)B，數(shù)學模型可表達為N（B）［18］。一條航線的轉向操縱緩沖區(qū)由一個或多個子轉向操縱緩沖區(qū)組成，B=｛B1，B2…，Bn1｝，Bi為某次轉向的子轉向操縱緩沖區(qū)（i=1，2…，n1，n1為航線的轉向次數(shù)）。若用1表示某次轉向可行，用 0表示不可行。整條航線的可轉向性N（B）由下式表達:

圖4　航線轉向操縱緩沖區(qū)生成示意圖Fig.4 A sketch map of constructing turning areas of a routing

判斷某次轉向的可轉向性，通過判斷其子轉向操縱緩沖區(qū)是否與礙航區(qū)相交來實現(xiàn)。設礙航區(qū)集合為O，對于某子轉向操縱緩沖區(qū)Bi，如果Bi∩｛O-O′｝=φ（O′為Bi對應的當前繞行礙航區(qū)，且O′∈O），則N（Bi）=1。

判斷各次轉向的可轉向性后，利用式（7）可解算整條航線的可轉向性。如果N（B）=0，則該航線不可轉向；如果N（B）=1，則該航線可轉向。

1.1.4航線轉向操縱緩沖區(qū)的生成

航線轉向操縱緩沖區(qū)的生成過程類同于求取線緩沖區(qū)，在建立緩沖區(qū)時，應先確定緩沖區(qū)的寬度（以下簡稱緩沖距）。計算航線轉向操縱緩沖區(qū)的緩沖距等同于利用艦船的轉向操縱誤差和導航定位誤差對實施轉向操縱時的航線誤差進行估計。令艦船的操縱誤差為σso，導航定位誤差為σnl，并假設以上各個過程是相互獨立的。根據(jù)誤差傳播定律求得緩沖距dbuffer算式如下

目前，線緩沖區(qū)生成算法主要有角平分線法、凸角圓弧法和線段基元疊置法［19-21］。角平分線法難以保證雙線的等寬性，異常情況多，不易完備地實現(xiàn)［19］；凸角圓弧法所生成的緩沖區(qū)邊界可能出現(xiàn)尖角和凹陷等失真現(xiàn)象，且修正過程復雜［20］。線段基元疊置法能夠有效克服前兩種方法的不足［21］，因此本文采用線段基元疊置法求航線轉向操縱緩沖區(qū)。

以圖4（a）為例，參照文獻［21］中緩沖區(qū)的生成方法，航線某次轉向的轉向操縱緩沖區(qū)生成步驟如下:1）利用式（1）～（5）計算本次轉向的轉向圓弧，并利用式（6）對轉向圓弧進行離散化處理，結果如圖4（a）中的虛線所示；2）根據(jù)式（8）計算轉向操縱緩沖區(qū)的緩沖距，并生成每一航段的基元緩沖區(qū)；3）將所有航段的基元緩沖區(qū)進行邏輯并運算，求出本次轉向的航線轉向操縱緩沖區(qū)。

但是，在上述的轉向操縱緩沖區(qū)生成方法中會出現(xiàn)一個問題，即所求得的航線轉向操縱緩沖區(qū)中存在不能夠航行的區(qū)域，也就是轉向操縱緩沖區(qū)與礙航區(qū)及其緩沖區(qū)的相交區(qū)域，轉向不可行。為此，實際航行中要想在此處成功實施轉向，還必須改變艦船轉向時原來設定的弧線路徑，使得航線轉向操縱緩沖區(qū)與礙航區(qū)及其緩沖區(qū)不相交，但這其中將涉及較為復雜的幾何運算，難以實現(xiàn)。本文采用一種等價的處理方法。如圖4（b）所示，先對原礙航區(qū)的緩沖區(qū)進一步進行擴充處理，以預留出用于艦船轉向的區(qū)域，再擴充的距離大小為dbuffer，從而使得轉向操縱緩沖區(qū)與礙航區(qū)及其緩沖區(qū)不相交，轉向可行。然后再采用上述的轉向操縱緩沖區(qū)生成步驟生成航線轉向操縱緩沖區(qū)。

1.2轉向增加航程的計算

若某條航線未顧及轉向限制的航程為S0，艦船轉向增加的航程為STP，則顧及轉向限制后的航程為S=S0+STP。假設航線的轉向次數(shù)為n，則考慮轉向限制后的航程可由下式計算:

艦船轉向時，轉向角度是另外一個必須考慮的重要因素。一般而言，轉向角度越大，艦船的可操作性越差，相應增加的航程往往也越大。如圖5所示，以往計算航程時，直接求解直線距離（Pi-1Pi+ PiPi+1）作為本次轉向的航程，但這只是理想航程，并不是實際航行中的有效航程。在實際航行中，按照1.1.1節(jié)轉向操縱理論所述，進行三次轉向，轉向時艦船的航行路徑為和，則轉向增加的航程可由下式計算:

化簡后得

式中:r為定常旋回半徑，θ2為第一次轉向的轉向角，θ3為第二次轉向的轉向角。

圖5　轉向限制模型Fig.5 Turn penalty model

在實際轉向過程中，受人為因素、環(huán)境因素以及其他因素的影響，艦船的航行路徑可能會偏離轉向圓弧。為此，引入圓弧影響系數(shù)η來表示轉向過程中實際航行路徑與轉向圓弧路徑之間的偏差。

此外，艦船在轉向過程中還存在速降問題，從而造成航行時間的增加，為更具可比性，將增加的時間歸算成等效航程。通常以定?；剞D階段艦船的航速V與回轉開始時艦船直線航速V0之比來表征回轉速降特征，稱為回轉速降系數(shù)，其計算公式如下［22］

式中:K′為旋回性指數(shù)；CN為舵的法向力系數(shù)；θ為轉向角，rad。

2　實驗與分析

2.1不可轉向航線的排除

為了驗證所提算法的有效性，本文以文獻［22］中的艦船模型為實驗模型，分別選取比例尺為1∶250 000和1∶800 000的兩幅海圖進行了相關實驗，具體實驗參數(shù)見表1。設置安全水深為14.0 m，實驗結果如表2、圖6和圖7所示。

表1　實驗參數(shù)Table 1 Experimental parameters

表2　不可轉向航線的排除結果比對Table 2 Comparison of different methods for eliminating routes

圖6　海圖比例尺為1∶250 000Fig.6 A case of the chart scale is 1∶250 000

圖7　海圖比例尺為1∶800 000Fig.7 A case of the chart scale is 1∶800 000

從表2可以看出，未顧及轉向限制時，在兩幅海圖上分別生成8條和15條繞行航線。但在實際航行中，還需要考慮艦船操縱性能的限制，從而使得某些繞行航線無法真正實施，這些航線應當被排除掉，真正可行的航線總數(shù)從而會減少。

在圖6和圖7中，折線是分別采用未顧及和顧及轉向限制的方法為安全水深14.0 m的艦船自動生成的航線，圖中的細實線折線為所有可繞行礙航區(qū)的航線，粗實線折線為最短繞行航線。對比圖6（a）和圖6（b）可知，未顧及轉向限制的方法生成的最短距離航線ST（圖6（a）中的粗實線折線）在顧及轉向限制后（圖7（b）中的虛線折線），因在礙航區(qū) O3與 O4之間的虛線區(qū)域內無法實施轉向，所以在實際航行中并不真正可行。因此，未顧及轉向限制的方法生成的最短航線在實際中并不一定真正可行，而本文所提的顧及轉向限制的方法生成的最短航線才真正可行。

2.2顧及轉向限制的最短距離航線自動生成

為了進一步反映艦船轉向對航線距離的影響，繼續(xù)利用實驗 2.1節(jié)中的數(shù)據(jù)，將安全水深由14.0 m改為12.0 m，礙航區(qū)范圍由此變小，從而使得2.1節(jié)中所述兩種方法生成的最短距離航線在實際中都真正可行。分別計算兩種方法生成的最短航線的轉向次數(shù)、最大轉向角度和有效航程，實驗結果如表3、圖8和圖9所示。

從實驗結果可以看出，相比顧及轉向限制的方法，未顧及轉向限制的方法所生成的最短距離航線，其實際轉向次數(shù)相對較多，最大轉向角度相對較大，這會影響艦船轉向的可操縱性；同時，其有效航程也相對較大，并不是實際航行中的最短距離航線。而采用本文所提方法生成的最短距離航線，其轉向次數(shù)少，最大轉向角度小，在顧及轉向限制的情況下，實際航行的距離更短。

表3　最短距離航線自動生成結果比對Table 3 Comparison of different methods for the shortest distance routing

圖8　海圖比例尺為1∶250000Fig.8 A case of the chart scale is 1∶250000

圖9　海圖比例尺為1∶800 000Fig.9 A case of the chart scale is 1∶800 000

3　結論

通過理論分析及實驗比對，得結論如下:

1）所提方法通過判斷航線轉向操縱緩沖區(qū)是否與礙航區(qū)相交，能夠有效排除當前最短距離航線生成方法中的不可行航線，得到真正可行的最短距離航線。

2）所提方法在顧及轉向限制的條件后，進一步優(yōu)化了轉向次數(shù)和角度，也使實際航行的距離更短。

當然，轉向圓弧離散化處理中分段精度的不同會對結果產生一定的影響。另外，風、流等動態(tài)因素對艦船轉向操縱的影響，還有待于以后進一步研究。

［1］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.

［2］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）:27-42.

［3］ZHAO Yuxin，TANG Jiqiang，LI Gang，et al.Route design and automatic check in electronic chart display and information system［J］.Journal of marine science and application，2004，3（1）:33-36.

［4］王科.基于電子海圖的航線設計研究［D］.大連:海軍大連艦艇學院，2004:1-2. WANG Ke.A study for designing navigation route based on ECDIS［D］.Dalian:PLA Dalian Naval Academy，2004:1-2.

［5］謝興瀾.ECDIS中的航線設計與最優(yōu)航法［D］.大連:大連海事大學，2003:6-7. XIE Xinglan.Route planning&advanced navigation in ECDIS［D］.Dalian:Dalian Maritime University，2003:6-7.

［6］湯青慧.基于電子海圖的航線規(guī)劃方法研究［D］.青島:中國海洋大學，2011:8. TANG Qinghui.Research on route planning method based on electronic chart［D］.Qingdao:Ocean University of China，2011:8.

［7］芮震峰，應榮熔，李偉.基于直覺模糊數(shù)和相對貼近度軍事航線優(yōu)選［J］.艦船科學技術，2014，36（1）:144-157. RUI Zhenfeng，YING Rongrong，LI Wei.A methodology for military route selection using intuitionistic fuzzy numbers［J］. Ship science and technology，2014，36（1）:144-157.

［8］張立華，朱慶，張安民，等.一種智能的最短航線構建方法［J］.測繪學報，2008，37（1）:114-120. ZHANG Lihua，ZHU Qing，ZHANG Anmin，et al.An intelligent method for the shortest routing［J］.Acta geodaetica et cartographica sinica，2008，37（1）:114-120.

［9］汪柱，李樹軍，張立華，等.基于航路二叉樹的航線自動生成方法［J］.武漢大學學報:信息科學版，2010，35 （4）:407-410. WANG Zhu，LI Shujun，ZHANG Lihua，et al.A method for automatic routing based on route binary tree［J］.Geomatics and information science of Wuhan university，2010，35（4）: 407-410.

［10］曹鴻博，張立華，賈帥東，等.電子海圖最短距離航線自動生成的改進方法［J］.武漢大學學報:信息科學版，2011，36（9）:1107-1110.CAO Hongbo，ZHANG Lihua，JIA Shuaidong，et al.An improved method for automatically building shortest route based on electronic chart［J］.Geomatics and information science of Wuhan university，2011，36（9）:1107-1110.

［11］李源惠，孫少鵬，于衛(wèi)紅.電子海圖中計劃航線可行性的自動判別［J］.大連海事大學學報，2000，26（2）:40-43. LI Yuanhui，SUN Shaopeng，YU Weihong.Auto evaluation of the feasibility of planned sea route in ECDIS［J］.Journal of Dalian Maritime University，2000，26（2）:40-43.

［12］尹相達.考慮施舵過程的本船轉向避讓時雷達標繪方法研究［J］.中國水運，2011，11（7）:15-16.

［13］陸儒德.艦船操縱與避碰［M］.北京:海潮出版社，1993:34-40.

［14］BEKKER J F，SCHMID J P.Planning the safe transit of a ship through a mapped minefield［J］.Jorssa，2006，22 （1）:1-18.

［15］黨瑩.基于ECDIS大洋航線自動選擇優(yōu)化系統(tǒng)的研究及初步實現(xiàn)［D］.上海:上海海事大學，2006:9-18.

［16］BIJLSMA S J.A computational method in ship routing using the concept of limited manoeuvrability［J］.The Journal of Navigation，2004，57:357-369.

［17］鄭中義.船舶自動避碰決策系統(tǒng)的研究［D］.大連:大連海事大學，2000:23-25. ZHENG Zhongyi.Research on automatic decision-making system of vessel collision avoidance［D］.Dalian:Dalian Maritime University，2000:23-25.

［18］張立華，劉雁春，朱慶，等.基于動態(tài)水位的航線可行性分析方法［J］.武漢大學學報:信息科學版，2008，33 （9）:892-895. ZHANG Lihua，LIU Yanchun，ZHU Qing，et al.Analysis of feasibility of routing based on changing water levels［J］. Geomatics and information science of Wuhan university，2008，33（9）:892-895.

［19］吳華意，龔健雅，李德仁.緩沖曲線和邊約束的三角網(wǎng)輔助的緩沖區(qū)生成算法［J］.測繪學報，1999，28（4）: 355-359. WU Huayi，GONG Jianya，LI Deren.Buffer curve and buffer generation algorithm in aid of edge-constrained triangle network［J］.Acta geodaetica et cartographica sinica，1999，28（4）:355-359.

［20］李金山，方金云.基于平面掃描的雙線圓弧緩沖區(qū)生成算法［J］.計算機工程與應用，2007，43（23）:28-31. LI Jinshan，F(xiàn)ANG Jinyun.Algorithm for line buffering based on plane sweep technique［J］.Computer Engineering and Applications，2007，43（23）:28-31.

［21］朱熀，艾廷華，王洪.基于條帶掃描思想的線目標緩沖區(qū)快速構建［J］.測繪學報，2006，35（2）:171-176. ZHU Huang，AI Tinghua，WANG Hong.The buffer construction of line object based on the geometric scan idea ［J］.Acta geodaetica et cartographica sinica，2006，35 （2）:171-176.

［22］李宗波，張顯庫，賈云.船舶轉向過程中速度下降問題的研究［J］.航海技術，2008（3）:2-4.

本文引用格式：

王濤，張立華，彭認燦，等.考慮轉向限制的電子海圖最短距離航線自動生成方法［J］.哈爾濱工程大學學報，2016，37（7）:923-929.

WANG Tao，ZHANG Lihua，PENG Rencan，et al.Automatic generation of the shortest route of an electronic navigational chart considering turning restrictions［J］.Journal of Harbin Engineering University，2016，37（7）:923-929.

Automatic generation of the shortest route of an electronic navigational chart considering turning restrictions

WANG Tao1，2，ZHANG Lihua1，2，PENG Rencan1，2，CAO Hongbo1，2，3，JIANG Linjun3
（1.Department of Hydrography and Cartography，Dalian Naval Academy，Dalian 116018，China；2.Key Laboratory of Hydrographic Surveying and Mapping of PLA，Dalian Naval Academy，Dalian 116018，China；3.Navy Press，Tianjin 300450，China）

Aiming at the shortage of the shortest route generated by the existing binary tree method without considering a ship＇s turn restrictions，we propose a method for automatically generating the shortest route by considering turning restrictions.By determining whether the turn steering areas of sea routes intersect with obstacle areas，we tested the turning aspects of sea routes.We established a turning restriction model by considering turn times，turn angles，turn radii，arc coefficients，and coefficients for the slowdown effect and determined the shortest route by analyzing the turning restrictions.Experimental results demonstrate that sea routes generated by the existing shortest route method in which turns cannot be executed can be eliminated by the new proposed method and that the turn t

10.11990/jheu.201503059

P229

A

1006-7043（2016）07-923-07

2015-03-18.網(wǎng)絡出版日期：2016-05-19.

國家自然科學基金項目（41471380，41171349）；國家高技術研究發(fā)展計劃項目（2012AA12A406）.

王濤（1987-），男，博士研究生；張立華（1973-），男，教授，博士生導師.

張立華，E-mail:zlhua@163.com.

網(wǎng)絡出版地址：http：//www.cnki.net/kcms/detail/23.1390.u.20160519.0901.002.html