基于Maklink圖和蟻群算法的航線規劃

陳 曉, 戴 冉, 陳昌源

(大連海事大學 航海學院， 遼寧 大連 116026)

2017-05-03

陳 曉(1993—)，男，山東煙臺人，碩士生，主要從事交通信息工程及控制、水上交通安全保障研究。

E-mail: chenxiao19930604@163.com

戴 冉(1964—),男,浙江杭州人,教授,碩士生導師,主要從事船舶性能測試技術、船舶模擬操縱技術、港口工程論證、天文航海等領域的研究。E-mail:dairan@163.com

1000-4653(2017)03-0009-05

基于Maklink圖和蟻群算法的航線規劃

陳 曉, 戴 冉, 陳昌源

(大連海事大學 航海學院， 遼寧 大連 116026)

為實現航線自動規劃設計，提出一種可行的計算方法，并對船舶實際運營中進行航線規劃時需注意的問題進行分析。以路徑最短為目標，建立以避開障礙物區域和危險區域、控制轉彎角度及減少轉向點數目等為約束條件的規劃模型。在建立模型過程中,采用Maklink圖和Dijkstra算法生成初始規劃路徑，采用蟻群算法對路徑作進一步的優化和調整，以滿足約束條件。試驗結果表明：與傳統的在紙質海圖上繪制航線及在電子海圖上手動輸入轉向點生成航線相比，通過智能算法生成航線具有耗時短、經濟可靠等優點。

船舶工程;航線自動規劃；Maklink圖；Dijkstra算法；蟻群算法

航線規劃是航?；顒又械闹匾h節，隨著電子海圖系統的廣泛應用，自動化的航線設計逐漸成為電子海圖系統應用中的重要內容。最優航線設計是指在進行航海活動之前，在考慮水深、障礙物及禁航區等因素的條件下，設計出一條安全的最短航線。但是，在進行海上避難、海上搜救等應急活動時，需更加靈活地選擇航線。因此，安全、可靠、快速的航線設計是現代航海的關鍵。[1]目前，航線規劃的方式主要有以下2種：

1) 通過查閱相關資料分析航行要求，在紙質海圖上選取轉向點，手工繪制航線。

2) 將選取的轉向點輸入到電子海圖顯示與信息系統(Electronic Chart Display and Information System,ECDIS)[2]中，生成相關航線，并利用電子海圖系統輔助分析航線的可行性。

隨著船舶智能化的推進，自動、快速繪制最短航線已成為目前急需解決的問題，而傳統的航線設計方式難以滿足當前的需求。因此，利用現有的電子海圖系統，通過對已有算法進行改進，快速規劃出一條安全、可靠的最短航線，對航?；顒又悄芑陌l展具有很好的促進作用。

這里利用Maklink圖論對海圖進行處理，生成無向網絡圖;通過蟻群算法對Dijkstra算法進行優化，自動搜索障礙物，并在保證安全的前提下自動生成最短計劃航線。

1 海圖模型建立

對于需規劃的海圖區域，不能直接使用海圖上的水深、障礙物及危險區域等信息,需對這些信息進行建模。通過建模將船舶航行區域轉換為Maklink圖，在Maklink圖的基礎上生成無向網絡圖，并進行下一步的路徑規劃研究。

1.1安全水深區的提取

準確計算出船舶可安全航行的水域是自動化航線設計的前提。提取安全等深線是ECDIS的一個重要功能，可根據船舶實際吃水確定安全水深區及危險水深區[3]，這里選擇在安全水深區進行自動航線規劃。

1.2Maklink圖論[4-6]

Maklink圖論是用來構造自由空間的一種方法，需預先定義凸多邊形，將空間分割成自由空間和障礙空間2部分，然后利用定義的基本形狀構造自由空間，最后將構造的自由空間表示成全局連通圖，在該圖上進行路徑規劃。

空間模型的構造方法為：定義障礙物為凸邊形，將任意2個障礙物之間不與障礙物相交的頂點的連線及障礙物頂點與邊界相交的線定義為Maklink線，取起點、終點及Maklink線的中點，三點相連構成的無向網絡圖即為可自由移動的路徑。

1.3無向網絡圖構建

首先對所選用海圖中的安全水深區內的海島、禁航區及危險區域等建立擴展的凸多邊形；然后以凸多邊形的各頂點為基礎構造Maklink圖；最后將起點、終點及Maklink線上的中點相連，構造出無向網絡圖，實現海圖模型的建立。

將電子海圖中顯示的危險區域及障礙物等轉換為凸包問題，利用Graham算法[7]生成凸多邊形，并在該凸多邊形的基礎上向外擴展h(見圖1)。將所擴展的區域定義為保護區，在路徑規劃過程中，即使沿著障礙物區域邊界尋找最短路徑，也能確保運動的船舶不與障礙物發生碰撞。

圖1 擴展保護區示意

在凸多邊形的基礎上，按照以下步驟[6]生成Maklink線，建立Maklink圖。

1) 將所有凸多邊形的頂點組合成集合D={d1,d2,d3,…,dn}，作頂點到邊界的垂線，將所有點兩兩相連，并按從短到長的順序排列，存儲在集合L中。

2) 選取集合L中的第1條線段。

3) 判斷所選線段是否與凸多邊形的邊界相交。若相交，則該線段不能作為Maklink線，放棄該線段并檢查集合L中的下一條線段，直到所檢查出的線段不與凸多邊形邊界相交，進入步驟4)。

4) 檢查該線段與凸多邊形的頂點產生的2個外角。若2個外角均<180°，則為最佳連接線，刪去該頂點的其他連接線，進入步驟7);若某個外角>180°，則將該連接線加入到該頂點的候選連接線中。

5) 檢查該頂點的所有候選連接線中是否存在外角>180°。若存在，則選擇集合L中的下一條線段，并返回步驟3)；若不存在，則進入步驟6)。

6) 刪除該頂點其他冗余的連接線。

7) 重復步驟1)～步驟6),直到完成所有頂點。

在構建完Maklink圖之后，選取所有Maklink線上的中點，連接相鄰中點、起點和終點，就構成無向網絡圖。

2 航線規劃數學建模

進行航線規劃的目的是避開障礙物，并使航行路徑最短。因此，結合實際操作需要，還應考慮船舶航向變化的大小及轉向點的多少等因素。這里對改變航向的角度、轉向點數量等進行約束，并建立相應的數學模型。假設所需規劃的航線的轉向點序列為(d1,d2,d3,…,dn), 建立數學模型

(1)

s.t.(di,di+1)∩Sj=φ,i=1,…,n,j=1,…,m

(2)

θ≤90°

(3)

h≥hmin

(4)

式(1)～式(4)中：式(1)表示所取轉向點間的距離最短，l為兩點間的距離；式(2)表示海圖中的障礙物區域，約束所取的轉向點不在障礙物內；式(3)表示航向改變的角度≤90°；式(4)表示對海圖中實際障礙物的擴展距離≥hmin。

3 路徑規劃

建立海圖模型，得到包含起點和終點的無向網絡圖，這里利用構造的無向網絡圖，依次進行初始航線規劃、蟻群算法優化及路徑調整。

3.1初始路徑規劃

利用Dijkstra算法[8]在無向網絡圖中選點，所選取的點與路徑的起點和終點構成次優路徑上的點。

Dijkstra算法的基本思想是按照路徑長度的增加順序尋找最短路徑，通過對路徑長度進行迭代得到從起點到終點的最短路徑。

設路徑的起點為S，終點為T，矩陣V存儲所有頂點，矩陣W存儲相鄰兩點間的距離，W[a,b]為a和b兩點間的距離。對于無向網絡圖中的每個頂點標號(dt,Pt)，dt表示從起點S到點t的距離，Pt表示從點S到點t的最短路徑的前一點。Dijkstra算法流程見圖2。

圖2 Dijkstra算法流程

圖3為Dijkstra規劃路徑，其中:虛線為Maklink線;黑細實線依次相連構成無向網絡圖;黑粗實線為通過Dijkstra算法生成的最短路徑,途經的路徑點為P1,P2,P3,P4。

3.2路徑優化

應用蟻群算法[9]對利用Dijkstra算法生成的初始路徑作進一步優化，所獲得的路徑為該Maklink圖中距離最短的路徑。

3.2.1解的表示形式

圖3 Dijkstra規劃路徑

Li上的其他點可表示為

hi∈[0,1],i=1,2,…,d

(5)

式(5)中:hi為比例參數;d為路徑上的節點數。

根據不同的參數hi，可得到一條新的路徑，蟻群算法的解可表示hi，即利用Dijkstra算法得到的路徑點，調整每個點在Maklink線上的位置，找到一條距離最短的線。為保證算法的可解性，采用固定距離劃分法對Maklink線進行劃分，設劃分長度為ω，每條Maklink線Li的劃分數為

(6)

式(6)中:當Int(Li/ω)為奇數時，Maklink線的中點也應為一個分段點，故劃分數應為ci+1。由于每條Li都被ci等分，因此Li-1到Li共有ci+1個節點可選擇。

3.2.2節點的選擇方法

利用蟻群算法優化路徑是指尋找參數集合(h1,h2,h3,…,hd)，從而得到距離最短時各節點的位置坐標。假設螞蟻的數量為m，起點為S，終點為T，其循環的路徑為

S→n1j→n2j→…→ndj→T

(7)

式(7)中:ndj為第d條Maklink線上的第j個等分點。每只螞蟻在選擇下一條Maklink線上的等分點時采用的方法為

(8)

式(8)中:I為Maklink線上等分點的集合；i為選擇的Maklink線；q為[0,1]內的隨機數;q0為[0,1]內的可調參數，為信息素選擇閾值；ηi,k為啟發值；τi,k為信息素；β為啟發值重要程度因子，其值越大，表示啟發值在轉移過程中的作用越大。J的計算方法為：首先計算當前Maklink線上的節點i到下一條Maklink線j的選擇概率Pi,j;然后采用輪盤賭法[10]選取下一個節點。Pi,j的計算式為

(9)

3.2.3信息素的更新原則

信息素的更新包括信息素的實時更新和信息素的路徑更新，其中實時更新為每只螞蟻在選擇節點后都需對該節點的信息素進行更新，更新公式為

τi,j=(1-ρ)τi,j+τ0ρ

(10)

式(10)中:τ0為信息素的初始值；ρ為[0,1]內的可調參數，表示信息素的揮發程度。

在第1次迭代完成之后，所有螞蟻走完從點S到點T的路徑，從中選取距離最短的一條，更新該路徑上所有點的信息素,更新公式為

(11)

式(11)中:L*為所選擇路徑的長度；ρ為[0,1]內的可調參數，表示信息素的揮發程度。

3.3路徑調整

應用蟻群算法優化之后，可得到一條基于Maklink圖的最短路徑，該路徑可滿足式(1)、式(2)及式(4)的約束，但由于Maklink線的緣故，該優化后的航線通過幾條Maklink線就有幾個轉向點，并不能滿足航海中轉向點的設置應盡可能少的實際需求。同時，未必能滿足式(3)的約束。因此，需對優化后的路徑作進一步的調整，從而滿足上述要求。

調整的思路為:取優化后的路徑點，采用回溯的方式，按照從終點T到起點S的方向，將獲得的路徑點回溯一遍，在保證點與點之間相連的線段不穿過障礙物的前提下，盡可能地裁彎取直，這樣既可減少轉向點，又能控制轉向角度不會過大。具體調整流程[4]見圖4。

圖4 路徑調整流程

4 算法模擬

以從電子海圖系統中截取的海圖(見圖5，其中白色為島嶼)為例，利用MATLAB軟件對截圖中的障礙物進行凸多邊形化，并完成Maklink圖構建，構造無線網絡圖，運用算法得到優化后的路徑及轉向點。

圖5 電子海圖截圖

圖6為利用MATLAB軟件對電子海圖進行處理得到的模型，其中:S和T分別為需規劃航線的起點和終點;黑色多邊形為對海圖中的島嶼進行擴展后生成的凸多邊形。

圖6 MATLAB模型

圖7為對MATLAB建立的模型進行Maklink圖化，其中:虛線為Maklink線;黑實線為相鄰Maklink線的中點相連得到的無向網絡圖。

圖7 Maklink圖和無向網絡圖

在無向網絡圖中，首先利用Dijkstra算法規劃出次優路徑，然后利用蟻群算法對該次優路徑進行優化，最后通過裁彎取直過濾掉冗雜的轉向點，得到最短路徑(見圖8)。圖8中:黑色粗實線為利用Dijkstra算法得到的次優路徑;灰色點劃線為利用蟻群算法得到的最優路徑;黑色點線為裁彎取直后得到的路線。優化后得到的最優路徑轉向點分別為:29°52′48″N，129°48′00″E；29°54′36″N，129°54′00″E。該最短航線的長度為40.808 1 n mile。

圖8 規劃路徑圖

將利用MATLAB軟件模擬得到的轉向點輸入到電子海圖中，最終得到的規劃航線見圖9。圖9中:黑色的實線為航線;點1和點4分別為起點S及終點T;點2和點3為起點與終點間的轉向點。

圖9 航線生成示例

5 結束語

本文依次從場景建模、航路初始規劃和航路優化及調整等3個階段進行船舶航線規劃研究。首先對獲取的海圖信息進行建模，生成含有安全區的凸多邊形;其次利用Maklink圖和Dijkstra算法獲得初始規劃路徑;隨后采取蟻群算法對路徑進行進一步優化;最后在蟻群算法的基礎上對已優化航路進行

調整，裁彎取直，刪除冗雜轉向點，從而滿足約束條件。

由仿真試驗可知，本文采取的方法可快速實現航線規劃，生成可行航線，并能滿足轉向點角度及轉向點數量等方面的要求。與傳統的手動進行航線規劃相比，本文采用的航線規劃方法不僅能減輕船員的勞動強度，而且能考慮多方面因素，避免手動規劃航線時可能產生的考慮不周的問題。但是,本文僅研究海圖中存在的固定障礙區及危險區，并未考慮周邊船舶及天氣的影響，這些因素將在今后作進一步的研究。

[1] 張立華,朱慶,劉雁春,等. 電子海圖平臺下的航線自動設計方法[J]. 大連海事大學學報,2007,33(3):109-112.

[2] 賈傳熒,史國友,賈銀山,等. 基于電子海圖的船舶動態監控系統設計與實現[J]. 大連海事大學學報,2002,28(3):20-22.

[3] 胡江強,曹玉墀,李國帥,等. 談ECDIS中的安全等深線問題[J]. 世界海運,2016(2):29-32.

[4] 王飛,王紅勇. 基于Maklink圖和遺傳算法的改航路徑規劃方法研究[J]. 交通運輸系統工程與信息,2014,14(5):154-160.

[5] 朱青. 基于蟻群算法的船舶航線設計方法的研究[D].哈爾濱:哈爾濱工程大學,2011.

[6] HABIB M K, ASAMA H. Efficient Method to Generate Collision Free Paths for an Autonomous Mobile Robot Based on New Free Space Structuring Approach[C]// IEEE/RSJ International Workshop on Intelligent Robots and Systems 91 Intelligence for Mechanical Systems, Proceedings, 1991:563-567.

[7] 吳文周,李利番,王結臣. 平面點集凸包Graham算法的改進[J]. 測繪科學,2010,35(6):123-125.

[8] 劉建美,馬壽峰,馬帥奇. 基于改進的Dijkstra算法的動態最短路計算方法[J]. 系統工程理論與實踐,2011,31(6):1153-1157.

[9] HLAING Z C S S, KHINE M A. Solving Traveling Salesman Problem by Using Improved Ant Colony Optimization Algorithm[J]. International Journal of Information and Education Technology,2011,1(5):404-409.

[10] 李永林,葉春明,劉長平. 輪盤賭選擇自適應和聲搜索算法[J]. 計算機應用研究,2014,31(6):1665-1668.

NavigationRoutePlanningwithMaklinkGraphandAntColonyAlgorithm

CHENXiao,DAIRan,CHENChangyuan

(School of Navigation, Dalian Maritime University, Dalian 116026, China)

An automatic method to optimize ship routeing is proposed. The practical details which should be taken into consideration in navigation route planning are analyzed. The programming model for minimizing total route length under constraints is developed which takes obstacle areas, dangerous areas and the limitations in the turning angle and turning point number into account. The Maklink graph and Dijkstra algorithm are used to establish the preliminary route scheme. The ant colony algorithm is applied to optimize the route. The as-short-as possible route is obtained after further adjustment according to the constraints. The test results demonstrate that the proposed method has considerable advantages over traditional methods and electronic chart methods in terms of efficiency, fuel consumption and safety.

ship engineering; an automatic method； Maklink graph； Dijkstra algorithm； ant colony algorithm

U692.3+1

A