基于Maklink圖和蟻群算法的航線規(guī)劃

陳 曉, 戴 冉, 陳昌源

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

2017-05-03

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

E-mail: chenxiao19930604@163.com

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

1000-4653(2017)03-0009-05

基于Maklink圖和蟻群算法的航線規(guī)劃

陳 曉, 戴 冉, 陳昌源

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

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

船舶工程;航線自動(dòng)規(guī)劃；Maklink圖；Dijkstra算法；蟻群算法

航線規(guī)劃是航?；顒?dòng)中的重要環(huán)節(jié)，隨著電子海圖系統(tǒng)的廣泛應(yīng)用，自動(dòng)化的航線設(shè)計(jì)逐漸成為電子海圖系統(tǒng)應(yīng)用中的重要內(nèi)容。最優(yōu)航線設(shè)計(jì)是指在進(jìn)行航?；顒?dòng)之前，在考慮水深、障礙物及禁航區(qū)等因素的條件下，設(shè)計(jì)出一條安全的最短航線。但是，在進(jìn)行海上避難、海上搜救等應(yīng)急活動(dòng)時(shí)，需更加靈活地選擇航線。因此，安全、可靠、快速的航線設(shè)計(jì)是現(xiàn)代航海的關(guān)鍵。[1]目前，航線規(guī)劃的方式主要有以下2種：

1) 通過查閱相關(guān)資料分析航行要求，在紙質(zhì)海圖上選取轉(zhuǎn)向點(diǎn)，手工繪制航線。

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

隨著船舶智能化的推進(jìn)，自動(dòng)、快速繪制最短航線已成為目前急需解決的問題，而傳統(tǒng)的航線設(shè)計(jì)方式難以滿足當(dāng)前的需求。因此，利用現(xiàn)有的電子海圖系統(tǒng)，通過對(duì)已有算法進(jìn)行改進(jìn)，快速規(guī)劃出一條安全、可靠的最短航線，對(duì)航海活動(dòng)智能化的發(fā)展具有很好的促進(jìn)作用。

這里利用Maklink圖論對(duì)海圖進(jìn)行處理，生成無向網(wǎng)絡(luò)圖;通過蟻群算法對(duì)Dijkstra算法進(jìn)行優(yōu)化，自動(dòng)搜索障礙物，并在保證安全的前提下自動(dòng)生成最短計(jì)劃航線。

1 海圖模型建立

對(duì)于需規(guī)劃的海圖區(qū)域，不能直接使用海圖上的水深、障礙物及危險(xiǎn)區(qū)域等信息,需對(duì)這些信息進(jìn)行建模。通過建模將船舶航行區(qū)域轉(zhuǎn)換為Maklink圖，在Maklink圖的基礎(chǔ)上生成無向網(wǎng)絡(luò)圖，并進(jìn)行下一步的路徑規(guī)劃研究。

1.1安全水深區(qū)的提取

準(zhǔn)確計(jì)算出船舶可安全航行的水域是自動(dòng)化航線設(shè)計(jì)的前提。提取安全等深線是ECDIS的一個(gè)重要功能，可根據(jù)船舶實(shí)際吃水確定安全水深區(qū)及危險(xiǎn)水深區(qū)[3]，這里選擇在安全水深區(qū)進(jìn)行自動(dòng)航線規(guī)劃。

1.2Maklink圖論[4-6]

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

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

1.3無向網(wǎng)絡(luò)圖構(gòu)建

首先對(duì)所選用海圖中的安全水深區(qū)內(nèi)的海島、禁航區(qū)及危險(xiǎn)區(qū)域等建立擴(kuò)展的凸多邊形；然后以凸多邊形的各頂點(diǎn)為基礎(chǔ)構(gòu)造Maklink圖；最后將起點(diǎn)、終點(diǎn)及Maklink線上的中點(diǎn)相連，構(gòu)造出無向網(wǎng)絡(luò)圖，實(shí)現(xiàn)海圖模型的建立。

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

圖1 擴(kuò)展保護(hù)區(qū)示意

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

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

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

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

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

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

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

7) 重復(fù)步驟1)～步驟6),直到完成所有頂點(diǎn)。

在構(gòu)建完Maklink圖之后，選取所有Maklink線上的中點(diǎn)，連接相鄰中點(diǎn)、起點(diǎn)和終點(diǎn)，就構(gòu)成無向網(wǎng)絡(luò)圖。

2 航線規(guī)劃數(shù)學(xué)建模

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

(1)

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

(2)

θ≤90°

(3)

h≥hmin

(4)

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

3 路徑規(guī)劃

建立海圖模型，得到包含起點(diǎn)和終點(diǎn)的無向網(wǎng)絡(luò)圖，這里利用構(gòu)造的無向網(wǎng)絡(luò)圖，依次進(jìn)行初始航線規(guī)劃、蟻群算法優(yōu)化及路徑調(diào)整。

3.1初始路徑規(guī)劃

利用Dijkstra算法[8]在無向網(wǎng)絡(luò)圖中選點(diǎn)，所選取的點(diǎn)與路徑的起點(diǎn)和終點(diǎn)構(gòu)成次優(yōu)路徑上的點(diǎn)。

Dijkstra算法的基本思想是按照路徑長度的增加順序?qū)ふ易疃搪窂剑ㄟ^對(duì)路徑長度進(jìn)行迭代得到從起點(diǎn)到終點(diǎn)的最短路徑。

設(shè)路徑的起點(diǎn)為S，終點(diǎn)為T，矩陣V存儲(chǔ)所有頂點(diǎn)，矩陣W存儲(chǔ)相鄰兩點(diǎn)間的距離，W[a,b]為a和b兩點(diǎn)間的距離。對(duì)于無向網(wǎng)絡(luò)圖中的每個(gè)頂點(diǎn)標(biāo)號(hào)(dt,Pt)，dt表示從起點(diǎn)S到點(diǎn)t的距離，Pt表示從點(diǎn)S到點(diǎn)t的最短路徑的前一點(diǎn)。Dijkstra算法流程見圖2。

圖2 Dijkstra算法流程

圖3為Dijkstra規(guī)劃路徑，其中:虛線為Maklink線;黑細(xì)實(shí)線依次相連構(gòu)成無向網(wǎng)絡(luò)圖;黑粗實(shí)線為通過Dijkstra算法生成的最短路徑,途經(jīng)的路徑點(diǎn)為P1,P2,P3,P4。

3.2路徑優(yōu)化

應(yīng)用蟻群算法[9]對(duì)利用Dijkstra算法生成的初始路徑作進(jìn)一步優(yōu)化，所獲得的路徑為該Maklink圖中距離最短的路徑。

3.2.1解的表示形式

圖3 Dijkstra規(guī)劃路徑

Li上的其他點(diǎn)可表示為

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

(5)

式(5)中:hi為比例參數(shù);d為路徑上的節(jié)點(diǎn)數(shù)。

根據(jù)不同的參數(shù)hi，可得到一條新的路徑，蟻群算法的解可表示hi，即利用Dijkstra算法得到的路徑點(diǎn)，調(diào)整每個(gè)點(diǎn)在Maklink線上的位置，找到一條距離最短的線。為保證算法的可解性，采用固定距離劃分法對(duì)Maklink線進(jìn)行劃分，設(shè)劃分長度為ω，每條Maklink線Li的劃分?jǐn)?shù)為

(6)

式(6)中:當(dāng)Int(Li/ω)為奇數(shù)時(shí)，Maklink線的中點(diǎn)也應(yīng)為一個(gè)分段點(diǎn)，故劃分?jǐn)?shù)應(yīng)為ci+1。由于每條Li都被ci等分，因此Li-1到Li共有ci+1個(gè)節(jié)點(diǎn)可選擇。

3.2.2節(jié)點(diǎn)的選擇方法

利用蟻群算法優(yōu)化路徑是指尋找參數(shù)集合(h1,h2,h3,…,hd)，從而得到距離最短時(shí)各節(jié)點(diǎn)的位置坐標(biāo)。假設(shè)螞蟻的數(shù)量為m，起點(diǎn)為S，終點(diǎn)為T，其循環(huán)的路徑為

S→n1j→n2j→…→ndj→T

(7)

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

(8)

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

(9)

3.2.3信息素的更新原則

信息素的更新包括信息素的實(shí)時(shí)更新和信息素的路徑更新，其中實(shí)時(shí)更新為每只螞蟻在選擇節(jié)點(diǎn)后都需對(duì)該節(jié)點(diǎn)的信息素進(jìn)行更新，更新公式為

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

(10)

式(10)中:τ0為信息素的初始值；ρ為[0,1]內(nèi)的可調(diào)參數(shù)，表示信息素的揮發(fā)程度。

在第1次迭代完成之后，所有螞蟻?zhàn)咄陱狞c(diǎn)S到點(diǎn)T的路徑，從中選取距離最短的一條，更新該路徑上所有點(diǎn)的信息素,更新公式為

(11)

式(11)中:L*為所選擇路徑的長度；ρ為[0,1]內(nèi)的可調(diào)參數(shù)，表示信息素的揮發(fā)程度。

3.3路徑調(diào)整

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

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

圖4 路徑調(diào)整流程

4 算法模擬

以從電子海圖系統(tǒng)中截取的海圖(見圖5，其中白色為島嶼)為例，利用MATLAB軟件對(duì)截圖中的障礙物進(jìn)行凸多邊形化，并完成Maklink圖構(gòu)建，構(gòu)造無線網(wǎng)絡(luò)圖，運(yùn)用算法得到優(yōu)化后的路徑及轉(zhuǎn)向點(diǎn)。

圖5 電子海圖截圖

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

圖6 MATLAB模型

圖7為對(duì)MATLAB建立的模型進(jìn)行Maklink圖化，其中:虛線為Maklink線;黑實(shí)線為相鄰Maklink線的中點(diǎn)相連得到的無向網(wǎng)絡(luò)圖。

圖7 Maklink圖和無向網(wǎng)絡(luò)圖

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

圖8 規(guī)劃路徑圖

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

圖9 航線生成示例

5 結(jié)束語

本文依次從場(chǎng)景建模、航路初始規(guī)劃和航路優(yōu)化及調(diào)整等3個(gè)階段進(jìn)行船舶航線規(guī)劃研究。首先對(duì)獲取的海圖信息進(jìn)行建模，生成含有安全區(qū)的凸多邊形;其次利用Maklink圖和Dijkstra算法獲得初始規(guī)劃路徑;隨后采取蟻群算法對(duì)路徑進(jìn)行進(jìn)一步優(yōu)化;最后在蟻群算法的基礎(chǔ)上對(duì)已優(yōu)化航路進(jìn)行

調(diào)整，裁彎取直，刪除冗雜轉(zhuǎn)向點(diǎn)，從而滿足約束條件。

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

[1] 張立華,朱慶,劉雁春,等. 電子海圖平臺(tái)下的航線自動(dòng)設(shè)計(jì)方法[J]. 大連海事大學(xué)學(xué)報(bào),2007,33(3):109-112.

[2] 賈傳熒,史國友,賈銀山,等. 基于電子海圖的船舶動(dòng)態(tài)監(jiān)控系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J]. 大連海事大學(xué)學(xué)報(bào),2002,28(3):20-22.

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

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

[5] 朱青. 基于蟻群算法的船舶航線設(shè)計(jì)方法的研究[D].哈爾濱:哈爾濱工程大學(xué),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] 吳文周,李利番,王結(jié)臣. 平面點(diǎn)集凸包Graham算法的改進(jìn)[J]. 測(cè)繪科學(xué),2010,35(6):123-125.

[8] 劉建美,馬壽峰,馬帥奇. 基于改進(jìn)的Dijkstra算法的動(dòng)態(tài)最短路計(jì)算方法[J]. 系統(tǒng)工程理論與實(shí)踐,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] 李永林,葉春明,劉長平. 輪盤賭選擇自適應(yīng)和聲搜索算法[J]. 計(jì)算機(jī)應(yīng)用研究,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